数据结构与算法 平衡二叉树（AVL树）

AVL树是一种特殊的二叉查找树。

二叉查找树：

⼆叉排序树(Binary Sort Tree),⼜称为⼆叉查找树. 它或者是⼀颗空树.或者是⼀颗
具有下列性质的⼆叉树;
若它的左⼦树不空,则左⼦树上所有结点的值均⼩于它的根结构的值;
若它的右⼦树不空,则右⼦树上的所有结点的值均⼤于它的根结点的值;
它的左右⼦树也分别是⼆叉排序树;

二叉排序树

//二叉树的二叉链表结点结构定义
//结点结构
typedef  struct BiTNode
{
    //结点数据
    int data;
    //左右孩子指针
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

相关计算如下

//1.二叉排序树--查找
/*
 递归查找二叉排序树T中,是否存在key;
 指针f指向T的双亲,器初始值为NULL;
 若查找成功,则指针p指向该数据元素的结点,并且返回TRUE;
 若指针p指向查找路径上访问的最后一个结点则返回FALSE;
 */
Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){
   
    if (!T)    /*  查找不成功 */
    {
        *p = f;
        return FALSE;
    }
    else if (key==T->data) /*  查找成功 */
    {
        *p = T;
        return TRUE;
    }
    else if (key<T->data)
        return SearchBST(T->lchild, key, T, p);  /*  在左子树中继续查找 */
    else
        return SearchBST(T->rchild, key, T, p);  /*  在右子树中继续查找 */
}

//2.二叉排序树-插入
/*  当二叉排序树T中不存在关键字等于key的数据元素时， */
/*  插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key) {
    
    BiTree p,s;
    //1.查找插入的值是否存在二叉树中;查找失败则->
    if (!SearchBST(*T, key, NULL, &p)) {
        
        //2.初始化结点s,并将key赋值给s,将s的左右孩子结点暂时设置为NULL
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        
        //3.
        if (!p) {
            //如果p为空,则将s作为二叉树新的根结点;
            *T = s;
        }else if(key < p->data){
            //如果key<p->data,则将s插入为左孩子;
            p->lchild = s;
        }else
            //如果key>p->data,则将s插入为右孩子;
            p->rchild = s;
        
        return  TRUE;
    }
    
    return FALSE;
}

//3.从二叉排序树中删除结点p,并重接它的左或者右子树;
Status Delete(BiTree *p){
    
    BiTree temp,s;
    
    
    if((*p)->rchild == NULL){
       
        //情况1: 如果当前删除的结点,右子树为空.那么则只需要重新连接它的左子树;
        //①将结点p临时存储到temp中;
        temp = *p;
        //②将p指向到p的左子树上;
        *p = (*p)->lchild;
        //③释放需要删除的temp结点;
        free(temp);
        
    }else if((*p)->lchild == NULL){
        
        //情况2:如果当前删除的结点,左子树为空.那么则只需要重新连接它的右子树;
        //①将结点p存储到temp中;
        temp = *p;
        //②将p指向到p的右子树上;
        *p = (*p)->rchild;
        //③释放需要删除的temp结点
        free(temp);
    }else{
        
        //情况③:删除的当前结点的左右子树均不为空;
       
        //①将结点p存储到临时变量temp, 并且让结点s指向p的左子树
        temp = *p;
        s = (*p)->lchild;
      
        //②将s指针,向右到尽头(目的是找到待删结点的前驱)
        //-在待删除的结点的左子树中,从右边找到直接前驱
        //-使用`temp`保存好直接前驱的双亲结点
        while (s->rchild) {
            temp = s;
            s = s->rchild;
        }
        
        //③将要删除的结点p数据赋值成s->data;
        (*p)->data = s->data;
        
        //④重连子树
        //-如果temp 不等于p,则将S->lchild 赋值给temp->rchild
        //-如果temp 等于p,则将S->lchild 赋值给temp->lchild
        if(temp != *p)
            temp->rchild = s->lchild;
        else
            temp->lchild = s->lchild;
        
        //⑤删除s指向的结点; free(s)
        free(s);
    }
    
    return  TRUE;
}

//4.查找结点,并将其在二叉排序中删除;
/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{
    //不存在关键字等于key的数据元素
    if(!*T)
        return FALSE;
    else
    {
        //找到关键字等于key的数据元素
        if (key==(*T)->data)
            return Delete(T);
        else if (key<(*T)->data)
            //关键字key小于当前结点,则缩小查找范围到它的左子树;
            return DeleteBST(&(*T)->lchild,key);
        else
            //关键字key大于当前结点,则缩小查找范围到它的右子树;
            return DeleteBST(&(*T)->rchild,key);
        
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 二叉排序树(Binary Sort Tree)!\n");
    int i;
    int a[10]={62,88,58,47,35,73,51,99,37,93};
    BiTree T=NULL;
    
    for(i=0;i<10;i++)
    {
        InsertBST(&T, a[i]);
    }
    
    BiTree p;
    int statusValue = SearchBST(T, 99, NULL, &p);
    printf("查找%d是否成功:%d (1->YES/0->NO)\n",p->data,statusValue);
   
    
    statusValue = DeleteBST(&T,93);
    printf("二叉排序树删除93是否成功:%d (1->YES/0->NO)\n",statusValue);
    statusValue = DeleteBST(&T,47);
    printf("二叉排序树删除47是否成功:%d (1->YES/0->NO)\n",statusValue);
    statusValue = DeleteBST(&T,12);
    printf("二叉排序树删除12是否成功:%d (1->YES/0->NO)\n",statusValue);
    
    
    statusValue = SearchBST(T, 93, NULL, &p);
    printf("查找%d是否成功:%d (1->YES/0->NO)\n",93,statusValue);
    
    statusValue = SearchBST(T, 47, NULL, &p);
    printf("查找%d是否成功:%d (1->YES/0->NO)\n",47,statusValue);
    
    statusValue = SearchBST(T, 99, NULL, &p);
    printf("查找%d是否成功:%d (1->YES/0->NO)\n",99,statusValue);
    
    printf("\n");
    return 0;
}

普通的排序二叉树存在一个问题：
如果需要进行排序的数组本身就是有序的，那么二叉排序树就会变成链表，那么他的时间复杂度就会变成O(n);
这个时候就需要AVL树（平衡二叉树）来解决这个问题;

AVL树：

平衡⼆叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree),是⼀种⼆叉排序树.其中每⼀个结点的左⼦树和右⼦树的⾼度差⾄多等于1.
两位俄罗斯数学家 G.M.Adelson - Velskii 和 E.M.Landis 共同发明的⼀种解决平衡⼆叉树的算法. 也称为AVL树
⾼度平衡: 意思是说,要么它是⼀颗空树,要么它的左⼦树和右⼦树都是平衡⼆叉
树. 且左⼦树和右⼦树的深度之差的绝对值不超过1; 我们将⼆叉树上结点的左
⼦树深度减去右⼦树深度的值称为平衡因⼦BF(Balance Factr)

最小平衡树：
距离插⼊点最近的,且平衡因⼦的绝对值⼤于1的结点为根的⼦树,我们称为最⼩不平衡⼦树

最小平衡树