光阴冢 赛博空间的自留地

AVL 树

红黑树

性质

  • 红黑性质

    1. 节点红或黑
    2. root 节点是黑的
    3. 每个叶节点是黑的
    4. 红节点的儿子都是黑的
    5. 对每个节点,从该节点到其子孙节点的所有路径上的包含相同的黑节点。
  • 好的查找树性质

    一棵有 $n$ 个内节点的红黑树的高度至多为 $2\log{(n+1)}$。

操作

  • 旋转

    旋转操作可以不改变二叉查找树的性质而对树进行调整,可以有左旋(逆时针)和右旋(顺时针)。 复杂度为 $O(1)$,因为全部都是指针的移动。

  • 插入

    先将红黑树当作是普通的二叉查找树进行插入,并着为红色,然后使用一个辅助函数进行调整:

    1. 首先确定红黑性质有哪些不能继续保持。(在这一点上,性质 1,3,5都是会成立的。) 当插入的 z 是根节点时,性质 2 被破坏。如果 z 的父节点是红色的,性质 4 被破坏。

    2. 之后对插入节点 z 进行迭代操作。分三种情况进行讨论。

  • 删除

    思想和插入类似,都是先按照普通二叉树进行,然后进行调整。但是情况多了一点更复杂。

AVL 树

之前经常听到 AVL 树,但是在书里面却是以练习题的形式出现的。

操作

  • Balance

    分四种情况,对单个节点直接最多两次旋转即可。

    然后再分情况对子树进行检验,如果改变了平衡因子的子树们的平衡因子都还是0,-1,1的话说明已经平衡,否则再进行平衡操作。