多叉树与红黑树

引言

时间复杂度分析

树的插入,删除,查找的时间复杂度与树的高度成正比: O(高度) == O(最大层数 - 1) ,最符合需求的就是完全二叉树,来看下完全二叉树的最大高度:

完全二叉树

完全二叉树除最后一层,每层结点数:1, 2, 4,…, 2k-1
最后一层:1~2(L-1)
完全二叉树的结点数 n :

n >= 1+2+4+8+…+2L-2 + 1

n <= 1+2+4+8+…+2L-2 + 2L-1

利用等比数列求和公式:

image

L 的范围是 [log2(n+1), (log2n) +1]。完全二叉树的层数 <= (log2n) +1 ,其高度小于等于 log2n

二叉查找树会出现树的高度过高,从而导致各个操作的效率下降,比如下图只有右孩子的树(退化成了链表):

二叉树结构 (9)

为避免这种情况,一般选用平衡二叉查找树:红黑树。

什么是平衡二叉查找树?

平衡二叉树:任意节点左右子树的高度差 <= 1:

  • 完全二叉树
  • 满二叉树
  • 一些非完全二叉树

平衡二叉树:

平衡二叉树

非平衡二叉树

非平衡二叉树

早期的 AVL 树是平衡二叉树 + 查找 = 平衡二叉查找树

但为了实际应用,后续的树都没遵从平衡树的定义(比如红黑树),只要树的高度不比 log2n 大很多,都符合定义。

红黑树

红黑树的英文是 Red-Black Tree,简称 R-B Tree。

  • 根节点是黑色。
  • 叶子节点是黑色的空节点(为了简化代码,本章节可以不考虑)
  • 每个红色结点的两个子结点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色结点)
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点

二叉树结构

为什么红黑树的高度可以稳定地趋近 log2n ?

将红色节点删除,变成下图(四叉树),由于每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点,于是四叉树可以转换成完全二叉树,于是仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度还要小

把红色节点加回去,由于红色节点不能相邻(红色数量 ~= 黑色数量)。红黑树的高度近似 2log2n。

平衡树比较

  • Treap(树堆)、Splay Tree(伸展树)无法避免时间复杂度的退化

  • AVL 树是一高度平衡的二叉树,查找效率非常高,但是为了维持高度平衡,每次插入、删除都要做调整

  • 红黑树做到了近似平衡,维护平衡的成本比 AVL 树低

1 Like