乐趣区

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

二叉搜索树

大的在右边,小的在左边

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

平衡二叉树—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…

退出移动版