WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
AVL 树 - 数据结构
AVL 树,是一种平衡的二叉搜索树。由于各种算法教材上对 AVL 的介绍十分冗长,造成了很多人对 AVL 树复杂、不实用的印象。但实际上,AVL 树的原理简单,实现也并不复杂。 ## 性质 1. 空二叉树是一个 AVL 树 2. 如果 T 是一棵 AVL 树,那么其左右子树也是 AVL 树,并且 $|h(ls) - h(rs)| \leq 1$ ,h 是其左右子树的高度 3. 树高为 $O(\log n)$ 平衡因子:右子树高度 - 左子树高度 **树高的证明** 设 $f_n$ 为高度为 $n$ 的 AVL 树所包含的最少节点数,则有 $$ f_n= \begin{cases} 1&(n=1)\\\\ 2&(n=2)\\\\ f_{n-1}+f_{n-2}+1& (n>2) \end{cases} $$ 显然 $\\{f_n+1\\}$ 是一个斐波那契数列。众所周知,斐波那契数列是以指数的速度增长的,因此 AVL 树的高度为 $O(\log n)$ 。 ## 插入结点 与 BST(二叉搜索树)中类似,先进行一次失败的查找来确定插入的位置,插入节点后根据平衡因子来决定是否需要调整。 ## 删除结点 删除和 BST 类似,将结点与后继交换后再删除。 删除会导致树高以及平衡因子变化,这时需要沿着被删除结点到根的路径来调整这种变化。 ## 平衡的维护 插入或删除节点后,可能会造成 AVL 树的性质 2 被破坏。因此,需要沿着从被插入/删除的节点到根的路径对树进行维护。如果对于某一个节点,性质 2 不再满足,由于我们只插入/删除了一个节点,对树高的影响不超过 1,因此该节点的平衡因子的绝对值至多为 2。由于对称性,我们在此只讨论左子树的高度比右子树大 2 的情况,即下图中 $h(B)-h(E)=2$ 。此时,还需要根据 $h(A)$ 和 $h(C)$ 的大小关系分两种情况讨论。需要注意的是,由于我们是自底向上维护平衡的,因此对节点 D 的所有后代来说,性质 2 仍然是被满足的。 ![](../images/avl1.jpg) ### $h(A)\geq h(C)$ 设 $h(E)=x$ ,则有 $$ \begin{cases} h(B)=x+2\\\\ h(A)=x+1\\\\ x\leq h(C)\leq x+1 \end{cases} $$ 其中 $h(C)\geq x$ 是由于节点 B 满足性质 2,因此 $h(C)$ 和 $h(A)$ 的差不会超过 1。此时我们对节点 D 进行一次右旋操作(旋转操作与其它类型的平衡二叉搜索树相同),如下图所示。 ![](../images/avl2.jpg) 显然节点 A、C、E 的高度不发生变化,并且有 $$ \begin{cases} 0\leq h(C)-h(E)\leq 1\\\\ x+1\leq h'(D)=\max(h(C),h(E))+1=h(C)+1\leq x+2\\\\ 0\leq h'(D)-h(A)\leq 1 \end{cases} $$ 因此旋转后的节点 B 和 D 也满足性质 2。 ### $h(A)
= h[rs[ls[p]]] Right-Rotate(p) else Left-Rotate(ls[p]) Right-Rotate(p) else if h[ls[p]] - h[rs[p]] == -2 if h[ls[rs[p]]] <= h[rs[rs[p]]] Left-Rotate(p) else Right-Rotate(rs[p]) Left-Rotate(p) ``` 与其他平衡二叉搜索树相同,AVL 树中节点的高度、子树大小等信息需要在旋转时进行维护。 ## 其他操作 AVL 树的其他操作(Predecessor、Successor、Select、Rank 等)与普通的二叉搜索树相同。 ## 其他资料 在 [AVL Tree Visualization](https://www.cs.usfca.edu/~galles/visualization/AVLtree.html) 可以观察 AVL 树维护平衡的过程。