数据结构-数

遍历

四种主要的遍历思想为：前中后指的是根节点遍历位置

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

层次遍历：只需按层次遍历即可

前序遍历：1 2 4 5 7 8 3 6

中序遍历：4 2 7 5 8 1 3 6

后序遍历：4 7 8 5 2 6 3 1

层次遍历：1 2 3 4 5 6 7 8

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。

AVL 树

对平衡要求严格，插入和删除操作后可能需要频繁进行旋转操作来恢复平衡，这在一定程度上增加了操作的时间开销。因此，对于插入和删除操作频繁的场景，AVL 树可能不是最优选择。

红黑树

红黑树是一种自平衡二叉查找树，典型的用途是实现关联数组。可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

　　性质1. 节点是红色或黑色。

　　性质2. 根是黑色。

　　性质3. 所有叶子都是黑色（叶子是NIL节点）。

　　性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

　　性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

　　下面是一个具体的红黑树的图例：

特性

红黑树并不像 AVL 树那样严格平衡，从根节点到叶子节点的最长路径不会超过最短路径的两倍。这种近似平衡使得红黑树在插入和删除操作后的调整相对简单，不需要像 AVL 树那样频繁地进行旋转操作。

B树

B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

B树作为一种多路搜索树（并不是二叉的）：

　　1) 定义任意非叶子结点最多只有M个儿子；且M>2；

　　2) 根结点的儿子数为[2, M]；

　　3) 除根结点以外的非叶子结点的儿子数为[M/2, M]；

　　4) 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

　　5) 非叶子结点的关键字个数=指向儿子的指针个数-1；

　　6) 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

　　7) 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

　　8) 所有叶子结点位于同一层；