1. 梗概:

一种特殊的排序二叉树
1. 规定每个结点的两个子树高度差不能大于1

2. 相关概念:

2.1. 平衡因子

左子树高度-右子树高度

3. 保持排序二叉树平衡的思想

发生失衡的主要情况是: 插入一个新的树, 造成树失衡
1. 故主要针对插入操作调整排序二叉树, 使其恢复平衡
调整失衡的方法:
1. 如果失衡结点左子树较深(平衡因子大于1)
  1. 先做完两个特殊处理后
  2. 右旋失衡结点及其左孩子:
    1. 把失衡结点(本来为根)右旋下去, 代替新根原来的右子树
    2. 把左孩子右旋上去, 取代失衡结点成为新的根
    3. 图解:
      1. child::
2. 如果失衡结点右子树深(平衡因子小于-1)
  1. 先做完两个特殊处理后
  2. 左旋失衡结点及其右孩子:
    1. 把失衡结点(本来为根)左旋下去, 代替新根原来的左子树
    2. 把右孩子左旋上去, 取代失衡结点成为新的根
3. 两个特殊处理:
  1. 把新根(失衡结点的左孩子或右孩子)的平衡因子变成与失衡结点同号
    1. -1(右子树较深)左旋变为正数
    2. 1(左子树较深)右旋变为负数
  2. 把新根原来的左子树或右子树作为失衡结点的子树
    1. 因为新根的左子树或右子树将会被失衡结点代替
    2. 如果是左旋, 则失衡结点的右子树就有空位
      1. 把新根的左子树放到失衡结点的右子树
        
        新根左⇒旧根右
    3. 如果是右旋, 则失衡结点的左子树就有空位
      1. 把新根的右子树放到失衡结点的左子树
        
        新根右⇒旧根左

4. 在c语言中的实现

4.1. 定义

比普通排序二叉树多存储一个深度信息, 方便计算平衡因子

typedef struct AVLNode
{
    KeyType key;
    int depth;
    struct AVLNode *LChild, *RChild;
} AVLNode, *AVLTree;

4.2. 插入操作

梗概:

使用递归的两个原因:
1. 方便回溯访问路径上结点, 然后更新这些结点的深度信息
2. 方便回溯访问路径上的结点, 这样就可以从深到浅检查结点是否失衡
插入完成后, 都要更新插入路径上所有结点的高度记录
如果插入后还进行了旋转, 则每次旋转都要更新两个结点的深度信息:
1. 失衡结点
2. 新根结点
每次旋转完都要更新失衡结点的双亲结点或整棵树的指针, 让其指向新根
1. 因此需要传递双亲结点和整棵树的指针代码:

void renewDepth(AVLTree root){
    int depthL=root->LChild?root->LChild->depth:0;
    int depthR=root->RChild?root->RChild->depth:0;
    root->depth=(depthL>depthR?depthL:depthR)+1;
}
 
char calcBalance(AVLTree root){
    int depthL=root->LChild?root->LChild->depth:0;
    int depthR=root->RChild?root->RChild->depth:0;
    return depthL-depthR;
};
 
void right_rotate(AVLTree node,AVLNode* parent,AVLTree* tree){
    //node为失衡的结点,parent为其双,tree指向整棵树的根
    AVLTree son;
    /*失衡结点的左孩子将作为新的根*/
    son=node->LChild;
    /*新根的右子树并入原根的左空位*/
    node->LChild=son->RChild;
    /*以原根为新的右子树*/
    son->RChild=node;
    /*更新父节点*/
    if (parent!=NULL)
        if (parent->LChild==node)
            parent->LChild=son;
        else parent->RChild=son;
    /*更新整棵树的根*/
    else *tree=son;
    //更新旧根与新根的高度信息
    renewDepth(node);
    renewDepth(son);
}
 
void left_rotate(AVLTree node,AVLNode* parent,AVLTree* tree){
    //node为失衡的结点,parent为其双,tree指向整棵树的根
    AVLTree son;
    /*失衡结点的右孩子将作为新的根*/
    son=node->RChild;
    /*新根的右子树并入原根的右空位*/
    node->RChild=son->LChild;
    /*以原根为新的左子树*/
    son->LChild=node;
    /*更新父节点*/
    if (parent!=NULL)
        if (parent->LChild==node)
            parent->LChild=son;
        else parent->RChild=son;
    /*更新整棵树的根*/
    else *tree=son;
    //更新旧根与新根的高度信息
    renewDepth(node);
    renewDepth(son);
}
 
void Insert(AVLTree *root, AVLNode *parent,KeyType key){
    /*初始化树并插入*/
    if(!*root){
        *root=(AVLNode*)calloc(1, sizeof(AVLNode));
        (*root)->key=key;
        (*root)->depth=1;
        (*root)->LChild=(*root)->RChild=NULL;
    }
    /*如果说插入的数据小于根节点，往左边递归插入*/
    else if (key < (*root)->key)
        if ((*root)->LChild)
            Insert(&((*root)->LChild),*root, key);
        /*递归出口*/
        else{
            (*root)->LChild = (AVLNode *)calloc(1, sizeof(AVLNode));
            (*root)->LChild->key=key;
            (*root)->LChild->depth=1;
            (*root)->LChild->LChild=(*root)->LChild->RChild=NULL;
        }
    //如果说插入的数据大于根节点，往右边递归插入
    else
        if ((*root)->RChild)
            Insert(&(*root)->RChild,*root, key);
        /*递归出口*/
        else{
            (*root)->RChild = (AVLNode *)calloc(1, sizeof(AVLNode));
            (*root)->RChild->key=key;
            (*root)->RChild->depth=1;
            (*root)->RChild->LChild=(*root)->RChild->RChild=NULL;
        }
    /*每遍递归都要执行以下代码*/
    /* 左子树高，应该右旋*/
    if (calcBalance(*root) >= 2){
        /* 左孩子的右子树高，先左旋*/
        if (calcBalance((*root)->LChild) == -1)
            left_rotate((*root)->LChild,*root,root);
        right_rotate(*root,parent,root);
    }
    /* 右子树高，左旋*/
    else if (calcBalance(*root) <= -2){
        /* 右孩子的左子树高，先右旋*/
        if (calcBalance((*root)->RChild) == 1)
            right_rotate((*root)->RChild,*root,root);
        left_rotate(*root,parent,root);
    }
    /*递归更新所有路径上结点的深度*/
    else renewDepth(*root);
}

🪴qql1's digital garden

探索

平衡排序二叉树

1. 梗概:

2. 相关概念:

2.1. 平衡因子

3. 保持排序二叉树平衡的思想

4. 在c语言中的实现

4.1. 定义

4.2. 插入操作

关系图谱

目录

反向链接