0
4

分享

平衡二叉树

08月09日 收藏 0 评论 4 java开发

平衡二叉树

转载声明：文章来源 https://blog.csdn.net/isunbin/article/details/81707606

一、AVL树简介

AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。

平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

一棵AVL树有如下必要条件：

条件一：它必须是二叉查找树。

条件二：每个节点的左子树和右子树的高度差至多为1。

图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。

右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。

左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；

右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。

AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。

如果我们需要查找的集合本身没有顺序，在频繁查找的同时也经常的插入和删除，AVL树是不错的选择。

不平衡的二叉查找树在查找时的效率是很低的，因此，AVL如何维护二叉树的平衡是我们的学习重点。

二、AVL树相关概念

1. 平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。

在图二右边的AVL树上：

节点50的左子树高度为3，右子树高度为2，BF= 3-2 = 1；

节点45的左子树高度为2，右子树高度为1，BF= 2-1 = 1；

节点46的左子树高度为0，右子树高度为0，BF= 0-0 = 0；

节点65的左子树高度为0，右子树高度为1，BF= 0-1 = -1；

对于平衡二叉树，BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围，则需要对树进行调整。

2. 最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树.。

在图三中，左边二叉树的节点45的BF = 1，插入节点43后，节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点，因此以节点45为根的子树为最小不平衡子树。

三、AVL树的平衡调整

定义平衡二叉树节点结构：

typedef struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
}BTNode;

整个实现过程是通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。分为LL型、RR型、LR型和RL型4种类型，各调整方法如下(下面用A表示最低不平衡结点)：

1. LL型调整：

由于在A的左孩子(L)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1增至2。

下面图1是LL型的最简单形式。

显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B顺时针旋转一样。

LL型调整的一般形式如下图2所示，表示在A的左孩子B的左子树BL(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。

这种情况调整如下：

①将A的左孩子B提升为新的根结点；
②将原来的根结点A降为B的右孩子；
③各子树按大小关系连接(BL和AR不变，BR调整为A的左子树)。

代码实现：

BTNode *ll_rotate(BTNode *y)
{
    BTNode *x = y->left;
    y->left = x->right;
    x->right = y;   
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}

2. RR型调整：

由于在A的右孩子(R)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。

图3是RR型的最简单形式。

显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转一样。

RR型调整的一般形式如下图4所示，表示在A的右孩子B的右子树BR(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。

这种情况调整如下：

1、将A的右孩子B提升为新的根结点；
2、将原来的根结点A降为B的左孩子
3、各子树按大小关系连接(AL和BR不变，BL调整为A的右子树)。

代码实现：

BTNode *rr_rotate(struct Node *y)
{
    BTNode *x = y->right;
    y->right = x->left;
    x->left = y;
    
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}

3. LR型调整

由于在A的左孩子(L)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1变为2。

图5是LR型的最简单形式。

显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

LR型调整的一般形式如下图6所示，表示在A的左孩子B的右子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。

这种情况调整如下：

①将B的左孩子C提升为新的根结点；
②将原来的根结点A降为C的右孩子；
③各子树按大小关系连接(BL和AR不变，CL和CR分别调整为B的右子树和A的左子树)。

3.1 代码实现：

BTNode* lr_rotate(BTNode* y)
{
    BTNode* x = y->left;
    y->left = rr_rotate(x);
    return ll_rotate(y);
}

4. RL型调整：

由于在A的右孩子(R)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。

图7是RL型的最简单形式。

显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

RL型调整的一般形式如下图8所示，表示在A的右孩子B的左子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。

这种情况调整如下：

①将B的左孩子C提升为新的根结点；
②将原来的根结点A降为C的左孩子；
③各子树按大小关系连接(AL和BR不变，CL和CR分别调整为A的右子树和B的左子树)。

4.1 代码实现

Node* rl_rotate(Node* y)
{
    Node * x = y->right;
    y->right = ll_rotate(x);
    return rr_rotate(y);
}

平衡二叉树实现的实例

选取一组数据分别为2，1，0，3，4，5，6，9，8，7的10个结点来构造平衡二叉树。

首先数据为2的结点作为根结点插入，接着插入1，仍是平衡的，再插入0是，2的平衡因子变为2，此时出现了不平衡，因此需要进行调整，最低不平衡结点为2，属于LL型，调整过程如图1所示。

接着插入3，是平衡的，再插入4，此时出现了不平衡，结点 1 和 2 的平衡因子都为 -2，结点2为最低不平衡结点，属于RR型，调整过程如图2所示

接着插入5，此时结点 1 的平衡因子为 -2，导致不平衡，结点1为最低不平衡结点，属于RR型，调整如图3所示。

接着插入6，此时结点4的平衡因子为 -2，导致不平衡，结点4为最低不平衡结点，属于RR型，调整如图4所示。

接着插入9，是平衡的，再插入8，此时结点 3、5、6 的平衡因子都为 -2，导致不平衡，结点6为最低不平衡结点，属于RL型，调整如图5所示。

插入7，此时结点3、5的平衡因子为 -2，导致不平衡，最低不平衡结点为5，属于RL型，调整如图6所示。

插入操作完整代码：

#include
#include
 
typedef struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
}BTNode;
 
int max(int a, int b);
 
 
int height(struct Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
BTNode* newNode(int key)
{
    struct Node* node = (BTNode*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}
 
BTNode* ll_rotate(BTNode* y)
{
    BTNode *x = y->left;
    y->left = x->right;
    x->right = y;
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}
 
BTNode* rr_rotate(BTNode* y)
{
    BTNode *x = y->right;
    y->right = x->left;
    x->left = y;
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}
 
int getBalance(BTNode* N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
BTNode* insert(BTNode* node, int key)
{
 
    if (node == NULL)
        return newNode(key);
 
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;
 
    node->height = 1 + max(height(node->left), height(node->right));
 
 
    int balance = getBalance(node);
 
 
 
    if (balance > 1 && key < node->left->key) //LL型
        return ll_rotate(node);
 
 
    if (balance < -1 && key > node->right->key)     //RR型
        return rr_rotate(node);
 
 
    if (balance > 1 && key > node->left->key)     //LR型
    {
        node->left = rr_rotate(node->left);
        return ll_rotate(node);
    }
 
    if (balance < -1 && key < node->right->key)     //RL型
    {
        node->right = ll_rotate(node->right);
        return rr_rotate(node);
    }
 
    return node;
}
 
 
void preOrder(struct Node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}
 
int main()
{
    BTNode *root = NULL;
 
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 0);
    root = insert(root, 3);
    root = insert(root, 4);
    root = insert(root, 4);
    root = insert(root, 5);
    root = insert(root, 6);
    root = insert(root, 9);
    root = insert(root, 8);
    root = insert(root, 7);
 
    printf("前序遍历：");
    preOrder(root);
    return 0;
}

删除代码：

struct Node * minValueNode(BTNode* node)
{
    BTNode* current = node;
 
    while (current->left != NULL)
        current = current->left;
 
    return current;
}
 
BTNode* deleteNode(BTNode* root, int key)
{
 
    if (root == NULL)
        return root;
 
    if ( key < root->key )
        root->left = deleteNode(root->left, key);
 
    else if( key > root->key )
        root->right = deleteNode(root->right, key);
 
    else
    {
        if( (root->left == NULL) || (root->right == NULL) )
        {
            BTNode* temp = root->left ? root->left :  root->right;
 
            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else 
             *root = *temp; 
            free(temp);
        }
        else
        {
            BTNode* temp = minValueNode(root->right);
 
            root->key = temp->key;
 
            root->right = deleteNode(root->right, temp->key);
        }
    }
 
 
    if (root == NULL)
      return root;
 
    root->height = 1 + max(height(root->left), height(root->right));
 
    int balance = getBalance(root);
 
 
    if (balance > 1 && getBalance(root->left) >= 0) //LL型
        return ll_rotate(root);
 
 
    if (balance > 1 && getBalance(root->left) < 0) //LR型
    {
        root->left =  rr_rotate(root->left);
        return ll_rotate(root);
    }
 
    if (balance < -1 && getBalance(root->right) <= 0) //RR型
        return rr_rotate(root);
 
    if (balance < -1 && getBalance(root->right) > 0)  //Rl型
    {
        root->right = ll_rotate(root->right);
        return rr_rotate(root);
    }
 
    return root;
}

完整代码：

#include
#include
 
typedef struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
}BTNode;
 
int max(int a, int b);
 
 
int height(struct Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
BTNode* newNode(int key)
{
    struct Node* node = (BTNode*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}
 
BTNode* ll_rotate(BTNode* y)
{
    BTNode *x = y->left;
    y->left = x->right;
    x->right = y;
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}
 
BTNode* rr_rotate(BTNode* y)
{
    BTNode *x = y->right;
    y->right = x->left;
    x->left = y;
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}
 
int getBalance(BTNode* N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
BTNode* insert(BTNode* node, int key)
{
 
    if (node == NULL)
        return newNode(key);
 
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;
 
    node->height = 1 + max(height(node->left), height(node->right));
 
 
    int balance = getBalance(node);
 
 
 
    if (balance > 1 && key < node->left->key) //LL型
        return ll_rotate(node);
 
 
    if (balance < -1 && key > node->right->key)     //RR型
        return rr_rotate(node);
 
 
    if (balance > 1 && key > node->left->key)     //LR型
    {
        node->left = rr_rotate(node->left);
        return ll_rotate(node);
    }
 
    if (balance < -1 && key < node->right->key)     //RL型
    {
        node->right = ll_rotate(node->right);
        return rr_rotate(node);
    }
 
    return node;
}
 
 
BTNode * minValueNode(BTNode* node)
{
    BTNode* current = node;
 
    while (current->left != NULL)
        current = current->left;
 
    return current;
}
 
BTNode* deleteNode(BTNode* root, int key)
{
 
    if (root == NULL)
        return root;
 
    if (key < root->key)
        root->left = deleteNode(root->left, key);
 
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
 
    else
    {
        if ((root->left == NULL) || (root->right == NULL))
        {
            BTNode* temp = root->left ? root->left : root->right;
 
            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;
            free(temp);
        }
        else
        {
            BTNode* temp = minValueNode(root->right);
 
            root->key = temp->key;
 
            root->right = deleteNode(root->right, temp->key);
        }
    }
 
 
    if (root == NULL)
        return root;
 
    root->height = 1 + max(height(root->left), height(root->right));
 
    int balance = getBalance(root);
 
 
    if (balance > 1 && getBalance(root->left) >= 0) //LL型
        return ll_rotate(root);
 
 
    if (balance > 1 && getBalance(root->left) < 0) //LR型
    {
        root->left = rr_rotate(root->left);
        return ll_rotate(root);
    }
 
    if (balance < -1 && getBalance(root->right) <= 0) //RR型
        return rr_rotate(root);
 
    if (balance < -1 && getBalance(root->right) > 0)  //Rl型
    {
        root->right = ll_rotate(root->right);
        return rr_rotate(root);
    }
 
    return root;
}
 
 
void preOrder(struct Node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}
 
int main()
{
    BTNode *root = NULL;
 
    root = insert(root, 9);
    root = insert(root, 5);
    root = insert(root, 10);
    root = insert(root, 0);
    root = insert(root, 6);
    root = insert(root, 11);
    root = insert(root, -1);
    root = insert(root, 1);
    root = insert(root, 2);
    printf("前序遍历：\n");
    preOrder(root);
 
    /* The constructed AVL Tree would be
                     9
                    /  \
                   1    10
                 /  \     \
                0    5     11
               /    /  \
              -1   2    6
    */
    
    root = deleteNode(root, 10);
    /* The AVL Tree after deletion of 10
                       1
                     /   \
                    0     9
                  /     /  \
                -1     5     11
                     /  \
                    2    6
    */
    printf("\n");
    printf("前序遍历：\n");
    preOrder(root);
    return 0;
}

输出结果：

平衡二叉树 深度
C 4条回复 评论
冰冻三尺

大佬，能转载下吗？

发表于 2023-09-21 23:00:00
0 0
StanyChen

非常详细， 非常清晰， 代码测试可用。 教科书级别

发表于 2022-12-18 21:00:00
0 0
水杯

看完解析才知道应该是这样的思路

发表于 2022-08-03 21:00:00
0 0
雾岛残月

写的不错 共勉~，最近也在开始写博客。大佬们来翻牌啊！

发表于 2021-12-07 20:20:00
0 0
热门文章
【校招VIP】 SpringBoot之启动和配置
SpringBoot
小拿
220
【校招VIP】 Spring框架之bean
bean
小拿
230
课程推荐
SpingBoot核心注解的分类对比
379人学习
ThreadLocal到底用在什么场景？不说要线程池了
534人学习