AVL树

✍ dations ◷ 2024-09-20 17:43:28 #树结构

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 $O(\log {n})$ 个节点被旋转，而每次AVL旋转耗费固定的时间，所以删除处理在整体上耗费O(log ) 时间。

可以像普通二叉查找树一样的进行，所以耗费O(log )时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。（这是与伸展树搜索相对立的，它会因为搜索而变更树结构。）

假设平衡因子是左子树的高度减去右子树的高度所得到的值，又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先节点），则失去平衡后进行的规律可归纳为下列四种情况：

在平衡的二叉排序树BBST (Balancing Binary Search Tree)上插入一个新的数据元素e的递归算法可描述如下：

AVL树的调平（Erlang的实现）

 1 balance(null) -> null; 2 balance({null, _, null}=Tree) -> Tree; 3 balance({Left, Value, Right}=Tree) -> 4 	Diff = count(Left)-count(Right), 5 	if (Diff < 2) and (Diff > -2)	->	{balance(Left), Value, balance(Right)}; 6 	   (Diff > 1)				->	balance(rotate_right(Tree)); 7 	   (Diff< -1)				->	balance(rotate_left(Tree)); 8 	   true					->	exit('This is impossible!') 9 	end.10 11 rotate_right({Left, Value, Right}) ->12 	merge_max(Left, {null, Value, Right}).13 14 rotate_left({Left, Value, Right}) ->15 	merge_min(Right, {Left, Value, null}).16 17 merge_min({null, Value, Right}, Tree2) ->18 	{Tree2, Value, Right};19 merge_min({Left, _, _}, Tree2) ->20 	merge_min(Left, Tree2).21 22 merge_max({Left , Value, null}, Tree2) ->23 	{Left, Value, Tree2};24 merge_max({_, _, Right}, Tree2) ->25 	merge_max(Right, Tree2).

AVL节点数计算

高度为h的AVL树，总节点数N最多 $2^{h}-1$ $2^h -1$ ；最少节点数 $N_{h}$ $N_h$ 如以斐波那契数列可以用数学归纳法证明：
$N_{h}$ $N_h$ = $F_{h+2}$ $F_{h+2}$ - 1 ( $F_{h+2}$ $F_{h+2}$ 是斐波那契数列的第h+2项，根据斐波那契多项式得来)。
即:
$N_{0}$ $N_{0}$ = 0 (表示AVL Tree高度为0的节点总数)
$N_{1}$ $N_{1}$ = 1 (表示AVL Tree高度为1的节点总数)
$N_{2}$ $N_{2}$ = 2 (表示AVL Tree高度为2的节点总数)
$N_{h}$ $N_h$ = $N_{h-1}$ $N_{h-1}$ + $N_{h-2}$ $N_{h-2}$ + 1 (表示AVL Tree高度为h的节点总数)
换句话说，当节点数为N时，高度h最多为 $log_{\Phi }({\sqrt {5}}*(N+1))-2$ $log_{\Phi} ( \sqrt{5} *(N+1)) -2$ 。

AVL树

AVL节点数计算

相关