数据结构与算法—-搜索二叉树与跳表

搜索二叉树(Binary Search Tree)：

特性：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；

说明：

1. 搜索二叉树一定要说明以什么标准来排序
2. 经典的搜索二叉树，树上没有重复的用来排序的key值
3. 如果有重复节点的需求，可以在一个节点内部增加数据项

搜索二叉树查询key(查询某个key存在还是不存在):

1. 如果当前节点的value==key，返回true
2. 如果当前节点的value<key，当前节点向左移动
3. 如果当前节点的value>key，当前节点向右移动
4. 如果当前节点变成null，返回false

搜索二叉树插入新的key:

和查询过程一样，但当前节点滑到空的时候，就插入在这里

搜索二叉树删除key:

1. 先找到key所在的节点
2. 如果该节点没有左孩子、没有右孩子，直接删除即可
3. 如果该节点有左孩子、没有右孩子，直接用左孩子顶替该节点
4. 如果该节点没有左孩子、有右孩子，直接用右孩子顶替该节点
5. 如果该节点有左孩子、有右孩子，用该节点后继节点(右孩子的最左节点)顶替该节点

基础的搜索二叉树缺点：

1. 基础的搜索二叉树，添加、删除时候不照顾平衡性

2. 数据状况很差时（最差时呈一条链），性能就很差

左旋、右旋

基础的二叉树可以通过左旋、右旋动作维持平衡

AVL树、SB树与红黑树

共性：

1. 都是搜索二叉树，都具有平衡性(AVL树depth平衡，SB树size平衡)
2. 插入、删除、查询（一切查询）与搜索二叉树相同
3. 平衡调整使用的基本动作都只有左旋、右旋
4. 插入、删除时，从最底层被影响到的节点开始，对往上路径的节点做平衡性检查
5. 因为只对一条向上路径的每个节点做O(1)的检查和调整，所以可以做到O(logN)

不同：

1. 平衡性的约束不同
   AVL树最严格、SB树稍宽松、红黑树最宽松
2. 插入、删除和搜索二叉树一样，但是额外，做各自的平衡性调整。各自的平衡性调整所使用的动作都是左旋或者右旋

AVL树：

1. 最严格的平衡性，任何节点左树高度和右树高度差不超过1
2. 往上沿途检查每个节点时，都去检查四种违规情况：LL、RR、LR、RL
3. 不同情况对应平衡动作：
   LL（做一次右旋）、RR（做一次左旋）、LR和RL（利用旋转让底层那个上到顶部）

SB树(Size Balanced Tree)：

1. 让每一个叔叔节点为头的数，节点个数都不少于其任何一个侄子节点。
2. 也是从底层被影响节点开始向上做路径每个节点检查
3. 与AVL树非常像，也是四种违规类型：LL、RR、LR、RL
4. 不同情况对应平衡动作：
   LL（做一次右旋）、RR（做一次左旋）、LR和RL（利用旋转让底层那个上到顶部）
5. 与AVL树不同的是，每轮经过调整后，谁的孩子发生变化了，谁就再查(递归)

SB树在使用时候的改进：

1. 删除时可以不用检查，把平衡性的调整放在插入的时候，因为这种只要变就递归的特性，别的树没有
2. 可以在节点上封装别的数据项，来增加功能

红黑树：

1. 平衡性规定非常诡异
   • 每个节点非红即黑
   • 整棵树的头节点和叶子节点都是黑的
   • 红色节点的子节点不能为红
   • 任意一个节点到其下所有叶子节点的链中黑色节点要一样多
   • 整棵树最长的链为黑红交替，最短的链为全黑，但最长的链长度不会超过最短链的2倍
2. 平衡性调整最为复杂
   • 13种违规类型：增加节点5种；删除节点8种
3. 优点在于每次插入删除扰动较好，但是在今天看来这个优势也极其微弱了，贪图扰动小的话，B+树、2-3-4树可能更好
   • 频繁写入IO的情况对扰动性要求很高，但是有硬盘上实现的B树和B+树

跳表

• 结构上和搜索二叉树无关

• 利用随机概率分布来使得高层索引可以无视数据规律，做到整体性能优良

  • 传统跳表没有固定层级，新增节点有几层全靠roll骰子决定

• 思想是所有有序表中最先进的

• 结构简单，就是多级单链表

---

• ← Previous Post
• Next Post →

---

---