平衡二叉树AVL
左右子树高度差的绝对值不超过1
当插入或删除导致不平衡时，调整最小不平衡数，即以插入路径上离插入结点最近的平衡因子大于1的结点作为根的子树
平衡二叉树LL与RR.PNG
平衡二叉树LR.PNG
平衡二叉树RL.PNG
注意：LR与RL时，新结点究竟是插在C的左子树上还是右子树上是不影响旋转过程的。
查找效率
含有n个结点的平衡二叉树的最大深度为O(log(2)n)，平均查找长度为O(log(2)n)
向上取整(log(2)(n+1))
高度为h的AVL树中，最少结点树为S(h)=S(h-1)+S(h-2)+1
S(0)=1 S(1)=2
typedef struct{
Comparable element;
AVLNode *left;
AVLNode *right;
int height; //以该结点为根的子树的高度，空树为-1.单节点为0
}
int GetH(AVLNode *t) const
{
return t==NULL?-1:t->height;
}
void insert(const Comparable &x, AVLNode *&t)
{
if(t==NULL)
t=new AVLNode(x, NULL, NULL);
else if(x<t->element){
insert(x, t->left);
if(GetH(t->left)-GetH(t->right)==2)
if(x<t->left->element)
rotateWithLeftChild(t); //LL
else
doubleWithLeftChild(t); //LR
}
else if(x>t->element){
insert(x, t->left);
if(GetH(t->left)-GetH(t->right)==2)
if(x>t->right->element)
rotateWithRightChild(t); //RR
else
doubleWithRightChild(t); //RL
}
t->height=max(GetH(t->left), GetH(t->right))+1;
}
//LL
void rotateWithLeftChild(AVLNode *&k2)
{
AVLNode *k1=k2->left;
k2->left=k1->right;
k1->right=k2;
k2->height=max(GetH(k2->left), GetH(k2->right))+1;
k1->height=max(GetH(k1->left), GetH(k1->right))+1;
k2=k1; //指向新根以更新父节点的孩子指针
}
//RR
void rotateWithRightChild(AVLNode *&k1)
{
AVLNode* k2=k1->right;
k1->right=k2->left;
k2->left=k1;
k2->height=max(GetH(k2->left), GetH(k2->right))+1;
k1->height=max(GetH(k1->left), GetH(k1->right))+1;
k1=k2;
}
//LR
void doubleWithLeftChild(AVLNode *&k3)
{
rotateWithRightChild(k3->left);
rotateWithLeftChild(k3);
}
