从二叉排序树到红黑树

二叉排序树

二叉排序树是一种比较简单的数据结构,即某个节点左边的节点都是比较小的节点,右边的节点都是比较大的节点,并且某一个节点的左右子树都是一颗二叉排序树。利用树的结构特性可以提高查找元素的效率。

但是二叉排序树无法面对一种最坏情况,当树是一颗单支树,这样的树虽然也满足二叉排序树的定义,但是和普通的数组也没有区别了。

所有我们需要一定的策略来保证二叉排序树的结构,提高二叉排序树的查找效率,这就引入了平衡二叉排序树。

平衡二叉树

平衡二叉排序树之于普通的二叉排序树有一个额外的要求就是,任意节点的左右子树的高度之差不能超过1。这样可以避免二叉树成为单支树的最坏情况,还能保证查找某个元素时的时间复杂度基本在\(O(nlogn)\)量级。

但是平衡二叉树也存在一个问题,就是当平衡二叉树的插入和删除操作比较多的时候,维持树平衡时涉及到节点的旋转操作会带来比较大的开销,进而导致这种数据结构的效率降低。因为插入或者删除元素破坏了原来二叉树的结构,可能破坏平衡性条件,因此需要相应的调整措施来保证其符合平衡二叉树的定义。

红黑树

红黑树也是为了避免出现单支树的情况,即为了提高二叉排序树的查找效率。同时也为了改善平衡二叉排序树中的插入和删除操作频繁而导致开销过大的情况。

因此红黑树也有一些规则对二叉排序树的结构进行约束(就像AVL中左右子树高度差不能超过1的约束),首先红黑树定义了一些内容如节点的颜色(红或者黑),外部节点(空树,黑色的),黑边(连向黑色节点的边),黑长度(两个节点中黑边数量),黑高度(任意节点到该节点的黑长度) ,黑深度(根节点到该节点的黑长度),在以上定义下,一颗红黑树要满足如下的约束:

  • 根节点是黑色的
  • 红节点没有红孩子(孩子节点只能是黑色的)
  • 任意一个节点u到外部节点的黑高度相同

可以通过数学证明(证明有空再补上),具有n个节点的红黑树的高度至多为\(2nlog(n+1)\).这样也就是说在红黑树中查找元素的时间复杂度为 \(O(2nlog(n+1)=O(nlogn)\) ,虽然时间复杂度比AVL高,但是数量级和AVL相同。

同时红黑树由于其特殊的约束条件以及对应的元素插入和删除策略,使得调整二叉树结构使其满足约束时的额外开销比较小。因此在实际应用中红黑树的应用很广泛。

红黑树的插入和删除操作策略比较复杂,并且情况也比较多,网上也有很多相应的技术博客进行了介绍,这里简单总结一下,供温习是快速回想起来。

插入元素

  • 插入时插红节点,若插入为根节点则直接改成黑色。
  • 如果父亲节点是黑色,插入成功。
  • 如果父亲节点和叔叔节点都是红色,则父亲叔叔变黑,爷爷变红,并且将爷爷作为新插入节点,向上继续调整。
  • 如果父亲红叔叔黑,则存在一次旋转和两次旋转的问题。

删除元素

  • 删除非叶子节点时,首先将该元素替换成右子树的最小值,然后删除最小值的那个节点。
  • p父亲 s兄弟 l兄弟做孩子 r 兄弟右孩子
  • 分为5种情况(当删除为父亲的左孩子)
    • pslr全黑,s变红,继续向上调整
    • l为红…….
    • p 为红…….
    • r 为红…….
    • s 为红…….
    • 当删除为父亲的右孩子,对称地查看 r p l s

发表评论

电子邮件地址不会被公开。 必填项已用*标注