树与二叉树 | 平衡二叉树

AVL树简介

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

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

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

  1.  条件一：它必须是二叉查找树。
  2. 条件二：每个节点的左子树和右子树的高度差至多为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树的平衡调整

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

1. LL型调整：

  • LL型调整的一般形式如下图2所示，表示在A的左孩子B的左子树BL(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将A的左孩子B提升为新的根结点；②将原来的根结点A降为B的右孩子；③各子树按大小关系连接(BL和AR不变，BR调整为A的左子树)。

                                                                                                      图2  一般形式的LL型调整

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

1 typedef struct Node
2 {
3     int key;
4     struct Node *left;
5     struct Node *right;
6     int height;
7 }BTNode;

1.2代码实现：

 1 BTNode *ll_rotate(BTNode *y)
 2 {
 3     BTNode *x = y->left;
 4     y->left = x->right;
 5     x->right = y;   
 6  
 7     y->height = max(height(y->left), height(y->right)) + 1;
 8     x->height = max(height(x->left), height(x->right)) + 1;
 9  
10     return x;
11 }

RR型调整：

  • 由于在A的右孩子(R)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图3是RR型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转一样。

  • RR型调整的一般形式如下图4所示，表示在A的右孩子B的右子树BR(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将A的右孩子B提升为新的根结点；②将原来的根结点A降为B的左孩子；③各子树按大小关系连接(AL和BR不变，BL调整为A的右子树)。

                                                                        图4  一般形式的RR型调整

2.1 代码实现：

 1 BTNode *rr_rotate(struct Node *y)
 2 {
 3     BTNode *x = y->right;
 4     y->right = x->left;
 5     x->left = y;
 6     
 7  
 8     y->height = max(height(y->left), height(y->right)) + 1;
 9     x->height = max(height(x->left), height(x->right)) + 1;
10  
11     return x;
12 }

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);
}

RL型调整

  • 由于在A的右孩子(R)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图7是RL型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

                                                                                  图7  最简单的RL型调整

  • RL型调整的一般形式如下图8所示，表示在A的右孩子B的左子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将B的左孩子C提升为新的根结点；②将原来的根结点A降为C的左孩子；③各子树按大小关系连接(AL和BR不变，CL和CR分别调整为A的右子树和B的左子树)

                                                                         图8  一般形式的RL型调整

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所示。

                                                                         图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所示。

                                                                                           图六

插入操作完整代码

代码示例

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3  
  4 typedef struct Node
  5 {
  6     int key;
  7     struct Node *left;
  8     struct Node *right;
  9     int height;
 10 }BTNode;
 11  
 12 int max(int a, int b);
 13  
 14  
 15 int height(struct Node *N)
 16 {
 17     if (N == NULL)
 18         return 0;
 19     return N->height;
 20 }
 21  
 22 int max(int a, int b)
 23 {
 24     return (a > b) ? a : b;
 25 }
 26  
 27 BTNode* newNode(int key)  /创建一个节点
 28 {
 29     struct Node* node = (BTNode*)malloc(sizeof(struct Node));
 30     node->key = key;
 31     node->left = NULL;
 32     node->right = NULL;
 33     node->height = 1;
 34     return(node);
 35 }
 36  
 37 BTNode* ll_rotate(BTNode* y)
 38 {
 39     BTNode *x = y->left;
 40     y->left = x->right;
 41     x->right = y;
 42  
 43     y->height = max(height(y->left), height(y->right)) + 1;
 44     x->height = max(height(x->left), height(x->right)) + 1;
 45  
 46     return x;
 47 }
 48  
 49 BTNode* rr_rotate(BTNode* y)
 50 {
 51     BTNode *x = y->right;
 52     y->right = x->left;
 53     x->left = y;
 54  
 55     y->height = max(height(y->left), height(y->right)) + 1;
 56     x->height = max(height(x->left), height(x->right)) + 1;
 57  
 58     return x;
 59 }
 60  
 61 int getBalance(BTNode* N)
 62 {
 63     if (N == NULL)
 64         return 0;
 65     return height(N->left) - height(N->right);
 66 }
 67  
 68 BTNode* insert(BTNode* node, int key)
 69 {
 70  
 71     if (node == NULL)
 72         return newNode(key);
 73  
 74     if (key < node->key)
 75         node->left = insert(node->left, key);
 76     else if (key > node->key)
 77         node->right = insert(node->right, key);
 78     else
 79         return node;
 80  
 81     node->height = 1 + max(height(node->left), height(node->right));
 82  
 83  
 84     int balance = getBalance(node);
 85  
 86  
 87  
 88     if (balance > 1 && key < node->left->key) //LL型
 89         return ll_rotate(node);
 90  
 91  
 92     if (balance < -1 && key > node->right->key)     //RR型
 93         return rr_rotate(node);
 94  
 95  
 96     if (balance > 1 && key > node->left->key)     //LR型
 97     {
 98         node->left = rr_rotate(node->left);
 99         return ll_rotate(node);
100     }
101  
102     if (balance < -1 && key < node->right->key)     //RL型
103     {
104         node->right = ll_rotate(node->right);
105         return rr_rotate(node);
106     }
107  
108     return node;
109 }
110  
111  
112 void preOrder(struct Node *root)
113 {
114     if (root != NULL)
115     {
116         printf("%d ", root->key);
117         preOrder(root->left);
118         preOrder(root->right);
119     }
120 }
121  
122 int main()
123 {
124     BTNode *root = NULL;
125  
126     root = insert(root, 2);
127     root = insert(root, 1);
128     root = insert(root, 0);
129     root = insert(root, 3);
130     root = insert(root, 4);
131     root = insert(root, 4);
132     root = insert(root, 5);
133     root = insert(root, 6);
134     root = insert(root, 9);
135     root = insert(root, 8);
136     root = insert(root, 7);
137  
138     printf("前序遍历：");
139     preOrder(root);
140     return 0;
141 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/sunbines/p/9728464.html