数据结构与算法平衡二叉树和红黑树

二叉搜索树

大的在右边，小的在左边

缺点：无限插入一边元素，一直小，一直大，造成树的深度高，退化成链表

平衡二叉树—AVL 树

左右子树的高度差不超过 1(平衡因子)

1. 可以是空树。
2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

旋转

平衡的调整共有四种情况：分别为 LL,LR,RR,RL。

下面我们通过不断插入数据来说明几种不同的旋转方式:

• 左旋

• 右旋

例子

红黑树—RBT

Java8 中红黑树、数据库索引、TreeMap、TreeSet，时间复杂度 O(lgN)

自平衡二叉查找树

• 根节点必须黑色
• 叶子节点是黑色
• 父子不能同为红色
• 从任意节点出发，达到叶子节点经过的黑色节点数量一致

隐藏性质：

• 左右子树高度查最多为两倍

插入时默认插入红色，空的节点默认视为黑色 (叶子节点)

修复规则：

根据插入情况应用处理策略调整，直到满足性质

• 旋转
• 变色

插入情况

1. 被插入节点是根节点

   处理：直接把其涂黑

2. 被插入节点父节点是黑色

   处理：直接插入，什么都不需要做

3. 被插入节点父节点是红色

   处理：这种情况我们分为下面三种 Case，需要进行调整

• Case1：当前节点父节点和叔叔节点都是红色

  1. 将父节点设置为黑色
  2. 将叔叔节点设置为黑色
  3. 将祖父节点设置为红色
  4. 将祖父节点设置为当前节点，即继续对当前节点进行操作

• Case2：当前节点父节点是红色，叔叔节点是黑色，且当前节点是父节点的左孩子

  1. 将父节点设置为黑色
  2. 将祖父节点设置为红色
  3. 以祖父节点为支点进行右旋

• Case3：当前节点父节点是红色，叔叔节点是黑色，且当前节点是父节点的右孩子

  1. 当前结点的父结点做为新的当前结点
  2. 以父节点为支点左旋
  3. 得到 Case2

例子：

此时 4 节点处于 Case1，执行处理

此时当前节点为 7，处于 Case3，执行处理

此时当前节点为 2，处于 Case2，执行处理

得到满足性质的红黑树

参考博文：

平衡二叉树：https://zhuanlan.zhihu.com/p/…

红黑树：https://www.jianshu.com/p/e13…

https://github.com/julycoding…