§07 树状结构

AVL 树

自平衡的二叉搜索树：插入后任何节点的左右子树高度差不超过 1，失衡时通过左旋 / 右旋 / 双旋恢复平衡。查找、插入、删除都是 O(log n)。

AVL 树

第 01 / 19 步

AVL 树：按序列 10, 20, 30, 40, 50 逐个插入，保持左右子树高度差 ≤ 1。比较 0 · 交换 0

伪代码


				
					
					1
					// AVL 树：插入后维护平衡
				
			
				
					
					2
					procedure avlInsert(root, key)
				
			
				
					
					3
					  按 BST 规则插入新节点
				
			
				
					
					4
					  从新节点向上更新高度与平衡因子
				
			
				
					
					5
					  if 平衡因子 = 2 且 左左（LL）then 右旋
				
			
				
					
					6
					  if 平衡因子 = 2 且 左右（LR）then 先左旋后右旋
				
			
				
					
					7
					  if 平衡因子 = -2 且 右右（RR）then 左旋
				
			
				
					
					8
					  if 平衡因子 = -2 且 右左（RL）then 先右旋后左旋
				
			
				
					
					9
					end procedure

01 / 19

速度