09-07 16:25 已编辑电子科技大学成都学院 Java 发布于四川

关注

数据结构-数

遍历

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

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

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

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

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

前序遍历：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 树那样频繁地进行旋转操作。

HashMap 中红黑树的节点来自链表的转化，而链表的形成是因为不同 key 发生了哈希碰撞（即 hashCode() 计算后得到的哈希值相同，或者哈希值不同但模运算后落在同一数组下标）。因此：

红黑树中可能存在哈希值相同的节点（哈希碰撞导致）。
红黑树中也可能存在哈希值不同的节点（例如：两个 key 哈希值不同，但模运算后落在同一数组下标，且链表长度达到阈值转为红黑树）。

哈希值相等时，比较 key 的实际内容（equals）

若相等 → 找到目标节点；
若不相等 → 进入「补充比较」（避免哈希碰撞导致的 key 无法区分）

补充比较（解决哈希碰撞且 equals 不等的情况）当哈希值相同且 equals 不等时

若 key 是 Comparable 接口的实现类 → 调用 compareTo 方法比较；
若不是 → 比较两个 key 的类名和内存地址（通过 System.identityHashCode）。

这套补充规则确保任意两个不同的 key 都能确定「大小关系」，从而明确左 / 右子树的方向。

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) 所有叶子结点位于同一层；

B+数

B+树是B树的变体，也是一种多路搜索树：

　　1) 其定义基本与B-树相同，除了：

　　2) 非叶子结点的子树指针与关键字个数相同；

　　3) 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

　　4) 为所有叶子结点增加一个链指针；

　　5) 所有关键字都在叶子结点出现；

跳表

1.2 跳表如何构建

当插入一个数据时，随机获得这个节点的高度(索引层数，有最大值)，没错，就是随机！每涨一层的概率为p，这个认为设置，一般为0.25或者0.5,这样层数越高的节点就越少（这种结构跟平衡树有点像）。

1.3 如何搜索

这里有两级索引，遍历找8过程：1-4-7-8。上级索引找到后一索引值比查找值大时索引下沉。

跳表中查找一个元素的时间复杂度为 O(3*logn)，省略常数即：O(logn)。

插入数据

调用randomLevel() 方法，该方法会随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），且该方法有 1/2 的概率返回 1、1/4 的概率返回 2、1/8的概率返回 3，以此类推。

randomLevel() 方法返回 2 的时候会建立一级索引。返回 3，表示需要建二级索引

用二级索引插入数据6，下沉到二级索引后，发现 6 比 1 大比 7 小，此时需要在二级索引中 1 和 7 之间加一个元素6 ，并从元素 1 继续下沉到一级索引。

下沉到一级索引后，发现 6 比 1 大比 4 大，所以往后查找，发现 6 比 4 大比 7 小，此时需要在一级索引中 4 和 7 之间加一个元素 6 ，并把二级索引的 6 指向一级索引的 6，最后，从元素 4 继续下沉到原始链表。下沉到原始链表后，就比较简单了，发现 4、5 比 6小，7比6大，所以将6插入到 5 和 7 之间即可，整个插入过程结束。

总结

跳表是可以实现二分查找的有序链表；
每个元素插入时随机生成它的level；
最底层包含所有的元素；
如果一个元素出现在level(x)，那么它肯定出现在x以下的level中；
每个索引节点包含两个指针，一个向下，一个向右；（笔记目前看过的各种跳表源码实现包括Redis 的zset 都没有向下的指针，那怎么从二级索引跳到一级索引呢？留个悬念，看源码吧，文末有跳表实现源码）
跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近；