Skip to content

Latest commit

 

History

History
177 lines (163 loc) · 8.33 KB

4C.md

File metadata and controls

177 lines (163 loc) · 8.33 KB
Raw

弱AVL树

　　AVL树的约束条件比较强，以至于删除节点时所需结构变换次数达O(logN)，劣于红黑树（实际使用中AVL树整体性能不逊于未做平衡因子压缩的红黑树）。为了弥补这点遗憾，发展出了约束弱化的AVL树变种。

type node[T constraints.Ordered] struct {
    diff   [2]uint8    //与子树的高度差
    key    T
    parent *node[T]
    kids   [2]*node[T]
}

弱AVL树节点分别记录与两个子节点的逻辑高度差，并要求满足如下三则约束：

  • nil的高度为-1
  • 当节点为叶节点（子节点皆为nil）时，高度必须为0
  • 节点和子节点的高度差为1或2

对比AVL树可以发现，约束弱化后放松了如下两个点：

  • 非叶节点和nil之间的高度差可以为2
  • 非叶节点可以和左右子节点的高度差皆为2（AVL树的平衡因子只能表示12、11、21三种情况）

存在意义

　　显然，AVL树本身满足弱AVL树的约束，另外也可以证明弱AVL树能转成红黑树（请查阅相关文献，此处不展开），故弱AVL树是一种介乎于AVL树和红黑树之间的数据结构。

插入与再平衡

----------------LL型---------------    -----------------LR型----------------
|    X0 - P      |       X        |    |      X0 - P     |        Z        |
|   / \    \     |      / \       |    |     / \    \    |      /   \      |
| Y1   \    \    |    Y1   P1     |    |    /   Z1   \   |    X1     P1    |
|       \    \   |        /  \    |    |   /   /  \   \  |   /  \   /  \   |
|        Z2   S2 |      Z1    S1  |    | Y2   a    b  S2 | Y1    a b    S1 |

弱AVL树的插入和AVL树相似，差别在于再平衡过程，其中平衡因子的调整并没有那么直观。

func (tr *Tree[T]) rebalanceAfterInsert(P *node[T], trace uint64) {
    for {
        Xside := trace & 1
        Sside := 1 - Xside
        if P.diff[Xside]--; P.diff[Xside] > 0 { break } //无修正中止
        super, root := P.parent, (*node[T])(nil)
        if P.diff[Sside] == 1 {
            P.diff[Xside], P.diff[Sside] = 1, 2
            if P = super; P == nil { break }
            trace >>= 1
            continue                                    //回溯修正高度
        }
        if X := P.kids[Xside]; X.diff[Xside] == 1 {
            P.kids[Xside] = P.Hook(X.kids[Sside])
            X.kids[Sside] = X.hook(P)
            P.diff[Xside], P.diff[Sside], X.diff[Sside] = 1, 1, 1
            root = X                                    //LL(RR)
        } else {
            Z := X.kids[Sside]
            X.kids[Sside], P.kids[Xside] = X.Hook(Z.kids[Xside]), P.Hook(Z.kids[Sside])
            Z.kids[Xside], Z.kids[Sside] = Z.hook(X), Z.hook(P)
            X.diff[Sside], P.diff[Xside] = Z.diff[Xside], Z.diff[Sside]
            X.diff[Xside], P.diff[Sside] = 1, 1
            Z.diff[Xside], Z.diff[Sside] = 1, 1
            root = Z                                    //LR(RL)
        }
        if super == nil {
            tr.root = super.hook(root)
        } else {
            super.kids[(trace>>1)&1] = super.hook(root)
        }
        break
}   }

删除与再平衡

----------------LL型----------------    ----------------LR型----------------
|       P        |       S         |    |       P        |        Z        |
|      / \       |      / \        |    |      / \       |       / \       |
|    S1   \      |     /   \       |    |     S1  \      |      /   \      |
|   /  \   \     |    /     P1+    |    |    / \   \     |     /     \     |
| Y1    \   \    |  Y2     /  \    |    |   /   Z1  \    |    S2      P2   |
|       Z?   \   |       Z?    \   |    |  /   / \   \   |   /  \    / \   |
|             X3 |             X2- |    | Y2  a   b   X3 |  Y1   a  b   X1 |

删除过程略为复杂，不过全程只需要一次结构变换，比红黑树还要少。

func (tr *Tree[T]) rebalanceAfterRemove(P *node[T], trace uint64) {
    if P.kids[Left] == nil && P.kids[Right] == nil {
        P.diff[Left], P.diff[Right] = 1, 1      //叶节点需要特别处理
        if super := P.parent; super == nil {
            tr.root = super.Hook(P)
            return
        } else {
            P = super
            trace >>= 1
    }   }
    for {
        Xside := trace & 1
        Sside := 1 - Xside
        if P.diff[Xside]++; P.diff[Xside] == 2 {
            break                               //无修正中止
        }
        super, root := P.parent, (*node[T])(nil)
        if P.diff[Sside] == 2 {
            P.diff[Sside], P.diff[Xside] = 1, 2
            goto Lcascade                       //回溯修正高度case1
        }
        if S := P.kids[Sside]; S.diff[Sside] == 2 {
            if S.diff[Xside] == 2 {
                S.diff[Sside], S.diff[Xside], P.diff[Xside] = 1, 1, 2
                goto Lcascade                   //回溯修正高度case2
            }
            Z := S.kids[Xside]
            S.kids[Xside], P.kids[Sside] = S.Hook(Z.kids[Sside]), P.Hook(Z.kids[Xside])
            Z.kids[Sside], Z.kids[Xside] = Z.hook(S), Z.hook(P)
            S.diff[Xside], P.diff[Sside] = Z.diff[Sside], Z.diff[Xside]
            S.diff[Sside], P.diff[Xside] = 1, 1
            Z.diff[Sside], Z.diff[Xside] = 2, 2
            root = Z                            //LR(RL)
        } else {
            X, Z := P.kids[Xside], S.kids[Xside]
            S.kids[Xside] = S.hook(P)
            P.diff[Sside], S.diff[Xside] = S.diff[Xside], 1
            S.diff[Sside], P.diff[Xside] = 2, 2
            if Z == nil {
                P.kids[Sside] = nil
                if X == nil {                   //叶节点需要特别处理
                    S.diff[Xside], P.diff[Sside], P.diff[Xside] = 2, 1, 1
                }
            } else {
                P.kids[Sside] = P.hook(Z)
            }
            root = S                            //LL(RR)
        }
        if super == nil {
            tr.root = super.hook(root)
        } else {
            super.kids[(trace>>1)&1] = super.hook(root)
        }
        break
    Lcascade:
        if P = super; P == nil { break }
        trace >>= 1
}   }

性能评估

采用一轮插入+三分之二量删除+三分之二量有值查找+三分之一量无值查找的测试方法。

操作 SkipList B+ Tree RB-Tree AVL-Tree WAVL-Tree
Insert 24.65ms 12.59ms 19.71ms 20.92ms 19.66ms
Search 23.96ms 10.18ms 12.27ms 11.53ms 12.11ms
Remove 16.91ms 8.51ms 10.07ms 10.21ms 10.48ms

十万随机整数测试，B+树的插入性能有显著优势，二叉树三家各有千秋，跳跃链表全面落后。

操作 SkipList B+ Tree RB-Tree AVL-Tree WAVL-Tree
Insert 506.90ms 175.64ms 425.14ms 420.90ms 425.22ms
Search 560.65ms 147.18ms 287.62ms 278.46ms 286.28ms
Remove 421.95ms 119.71ms 316.01ms 287.45ms 294.77ms

百万随机整数测试，B+树全面碾压对手，跳跃链表继续落后。
AVL树凭借更好的平衡性小超红黑树，弱AVL树的表现介于AVL树和红黑树之间。

深入追踪

追踪千万节点树中节点的深度分布，可以看出AVL树确实比红黑树平衡度更好，不过优势区间不大。 追踪千万节点树插入后再平衡所需的回溯步数，红黑树大幅胜出，弱AVL树的表现接近于AVL树。 追踪千万节点树删除后再平衡所需的回溯步数，红黑树和弱AVL树的回溯步数集中在3步以内，AVL树则更平缓。

评估结论

　　跳跃链表在核心查找性能上和平衡树有较大差距，目前看不到逆袭的希望。
　　B+树在大数据量下是无可争议的性能王者，不过它并不属于二叉搜索树家族，具体将会在下一节介绍。
　　AVL树和红黑树之争由来已久，其实删除过程中结构调整次数对两者间胜负的影响微乎其微，决定胜负的更多是平衡性以及平衡因子的维护。从统计上看，红黑树的再平衡过程胜于AVL树，不过可能会抵不过平衡性上的劣势。

目录　上一节　下一节