平衡二叉树

平衡二叉树（Balanced Binary Tree），又称AVL树

定义

空树，或者任一结点左、右子树高度差的绝对值不超过1，即 |BF(T)|≤1

“平衡因子”（Balance Factor，简称BF）： BF(T)=hL−hR ，其中 hL 和 hR 分别为 T 的左、右子树的高度

特性

设 nh 是高度为 h 的平衡二叉树的最小结点数，有： nh=nh−1+nh−2+1 nh=Fh+2−1,h≥0 ， Fh 为斐波那契函数给定结点数为 n 的AVL树的查找效率是 O(logn2) ，最大高度是 logn2

平衡二叉树的调整

在插入结点时，导致某个结点不平衡，把这个结点称为发现者，插入结点称为麻烦结点

RR插入

麻烦结点在发现者右子树的右边，需要RR旋转（右单旋）

LL插入

麻烦结点在发现者左子树的左边，需要LL旋转（左单旋）

LR插入

麻烦结点在发现者左子树的右边，需要LR旋转

RL插入

麻烦结点在发现者右子树的左边，需要RL旋转

注意：有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子