(39)王道数据结构-平衡二叉树

基本概念

平衡二叉树，简称平衡树(AVL树)–树上任一结点的左子树和右子树的高度之差不超过1。

平衡因子： 左树树高-右树树高
1.平衡二叉树结点的平衡因子的值只可能是-1、0或1
2.只要有任一结点的平衡因子绝对值大于1就不是平衡二叉树

代码结构

//平衡二叉树结点
typedef struct AVLNode {
    int key;        //数据域
    int balance;   //平衡因子
    struct AVLNode *lchild, *rchild; 
}AVLNode, *AVLTree;

最小不平衡子树

查找路径上的所有结点都有可能受到影响。从插入点往回找到第一个不平衡结点，调整以该结点为根的子树，插入结点之后调整的对象都是最小不平衡树。

在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。

调整最小不平衡子树A

LL:

在A的左孩子的左子树中插入导致不平衡
调整:
A的左孩子结点右上旋

RR:

在A的右孩子的右子树中插入导致不平衡
调整:
A的右孩子结点左上旋

LR:

在A的左孩子中的右子树插入导致不平衡
调整:
A的左孩子的右孩子 先左上旋再右上旋

RL:

在A的右孩子的左子树中插入导致不平衡
调整:
A的右孩子的左孩子 先右上旋后左上旋

左孩子右上旋

实现f向下旋转，p向上旋转；其中f是爹，p为孩子，gf为f他爹
1.f->lchild = p->rchild;
2.p->rchild = f;
3.gf->lchild/rchild = p;

右孩子左上旋

实现f向下旋转，p向上旋转；其中f是爹，p为孩子，gf是f他爹
1.f->rchild = p->rchild;
2.p->lchild = f;
3.gf->lchild/rchild = p;