西维蜀黍

【Data Structure】平衡二叉查找树（Balanced Binary Search Tree）

背景

实际上，二叉查找树操作的运行时间与树的高度（Height）是有关系的。一个树的高度指的是从树的根开始所能到达的最长的路径长度。树的高度可被递归性地定义为：

如果节点没有子节点，则高度为 0；
如果节点只有一个子节点，则高度为该子节点的高度加 1；
如果节点有两个子节点，则高度为两个子节点中高度较高的加 1；

Posted by Wei on 2019-05-29, Last Modified on 2025-08-11

【Data Structure】二叉查找树（Binary Search Tree）

二叉查找树（Binary Search Tree，BST）

二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者一颗二叉树的任何节点均满足：

若节点的左子树不空，则左子树上所有节点的值均小于这个节点的值；
若节点的右子树不空，则右子树上所有节点的值均大于这个节点的值；
节点的左、右子树也分别为二叉查找树；
没有值相等的节点

Posted by Wei on 2019-05-29, Last Modified on 2025-08-11

【Data Structure】线索二叉树（Threaded Binary Tree）

线索二叉树（Threaded Binary Tree）

通过观察二叉链表，我们发现，不管二叉树的形态如何，空链域的个数总是多于非空链域的个数。准确的说，有n个结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。如下图所示。

Posted by Wei on 2019-05-28, Last Modified on 2025-08-11

【Data Structure】二叉树（Binary Tree）

二叉树（Binary Tree）

简单地理解，满足以下两个条件的树就是二叉树：

本身是有序树；
树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

Posted by Wei on 2019-05-27, Last Modified on 2025-08-11

【OpenWrt】OpenWrt的路由器ssh访问

上下文

在成功刷完OpenWrt固件到路由器后，可以直接通过Luci界面来配置root用户的密码（同时，这个密码也是OpenWrt路由器管理页面的账号密码，如下图）。

Posted by Wei on 2019-05-27, Last Modified on 2025-08-11

【Data Structure】广义表（Generalised List）

数组既可以存储不可再分的数据元素（如数字 5、字符 ‘a’），也可以继续存储数组（即 n 维数组）。

Posted by Wei on 2019-05-24, Last Modified on 2023-03-23

【Data Structure】矩阵

矩阵

数据结构中，提供针对某些特殊矩阵的压缩存储结构。

这里所说的特殊矩阵，主要分为以下两类：

含有大量相同数据元素的矩阵，比如对称矩阵；
含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵；

针对以上两类矩阵，数据结构的压缩存储思想是：矩阵中的相同数据元素（包括元素 0）只存储一个。

Posted by Wei on 2019-05-24, Last Modified on 2025-08-11

【Data Structure】树（Trees）

树（Tree）

上图(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说，和数据 B、C、D 有关系；对于数据 B 来说，和 E、F 有关系。这就是“一对多”的关系。

Posted by Wei on 2019-05-24, Last Modified on 2025-08-11

【Algorithm】字符串匹配算法 - 朴素的字符串匹配算法（Naive String Matching Algorithm）

模式匹配/ 字符串匹配算法

字符串匹配

字符串匹配问题的形式定义：

**文本（Text）**是一个长度为 n 的数组 T[1..n]；
**模式（Pattern）**是一个长度为 m 且 m≤n 的数组 P[1..m]；
T 和 P 中的元素都属于有限的字母表 Σ 表；
如果 0≤s≤n-m，并且 T[s+1..s+m] = P[1..m]，即对 1≤j≤m，有 T[s+j] = P[j]，则说模式 P 在文本 T 中出现且位移为 s，且称 s 是一个有效位移（Valid Shift）。

Posted by Wei on 2019-05-23, Last Modified on 2025-08-11

【Algorithm】字符串匹配算法 - KMP 算法

模式匹配/ 字符串匹配算法

字符串匹配

字符串匹配问题的形式定义：

**文本（Text）**是一个长度为 n 的数组 T[1..n]，在下文中，将其对应的字符串称之为"源字符串"；
**模式（Pattern）**是一个长度为 m 且 m≤n 的数组 P[1..m]，在下文中，将其对应的字符串称之为"模式字符串"；
T 和 P 中的元素都属于有限的字母表 Σ 表；
如果 0≤s≤n-m，并且 T[s+1..s+m] = P[1..m]，即对 1≤j≤m，有 T[s+j] = P[j]，则说模式 P 在文本 T 中出现且位移为 s，且称 s 是一个有效位移（Valid Shift）。

Posted by Wei on 2019-05-22, Last Modified on 2025-08-11