一、定义(AVL树)
平衡二叉树定义(AVL):
要么它是一颗空树，或者具有以下性质的二叉排序树:它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1.
左边不是二叉排序树
左边45结点左右深度之差为2，大于1
二、平衡二叉树相关概念
平衡因子BF(Balance Factor):
将二叉树上结点的左子树高度减去右子树高度的值称为该结点的平衡因子BF(Balance Factor)。
也就是说，对于平衡二叉树，BF的取值范围为[-1,1]，如果发现某个结点的BF值不在此范围，则需要对树进行调整。
最小不平衡树
距离插入结点最近的，且平衡因子的绝对值大于1的结点的根的子树。
最小不平衡树
如图所示，左边二叉树的结点45的BF=1，而在插入43结点后，45结点的BF=2。结点45是距离插入结点43最近的BF不在[-1,1]范围内的结点，因此以结点45为根节点的子树为最小不平衡树。
三、平衡二叉树的平衡调整
定义
typedef enum Status{
success = 0,//成功
fail = 1//失败
}Status;
//二叉树结点定义
typedef struct BinaryTreeNode{
int val;//存储的值
struct BinaryTreeNode *lChild,*rChild;//左右孩子
int height;//深度
}BinaryTreeNode,*BinaryTree;
实现过程就是通过在一棵平衡二叉树中一次插入结点(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应调整。分为LL型、RR型、LR型和RL型四种类型，各调整方法如下(用A表示最低不平衡结点)。
1.LL型调整
LL型调整
在A的左孩子的左孩子上插入新节点，使得A的BF从1增到2，按照大小关系，结点B应作为新的根节点，其余两个结点分别作为左右孩子结点才能平衡，A结点就好像是绕结点B顺时针旋转一样。
具体算法步骤如下:
① 将A的左孩子B提升为新的根节点
② 将原来的根节点A降为B的右孩子
③ 各子树按照大小关系连接(BL和AR不变，BR调整为A的左子树)
image
/// LL型旋转
/// @param node 原根节点
void ll_rotate(BinaryTree *node){
BinaryTree A = *node;
//取出B结点作为新的根节点
BinaryTree B = A->lChild;
//B的右子树作为A的左子树(因为B这边都是比A小，所以只能为左子树)
A->lChild = B->rChild;
//B的右子树为A
B->rChild = A;
A->height = max(height(A->lChild), height(A->rChild)) + 1;
B->height = max(height(B->lChild), height(B->rChild)) + 1;
*node = B;
}
2.RR型调整
RR型调整
在A的右孩子B的右孩子上插入新结点C，使得A的平衡因子BF从-1变为-2，按照大小关系，结点B应作为新的根节点，其余两个结点分别作为左右孩子结点才能平衡，A结点就好像是绕B逆时针旋转一样。
具体算法步骤如下：
① 将A的右孩子B提升为新的根节点
② 将原来的根节点A降为B的左孩子
③ 各子树按照大小关系(AL和BR不变，将BL调整为A的右子树)
image
/// rr型旋转
/// @param node 原根节点
void rr_rotate(BinaryTree *node){
BinaryTree A = *node;
//取出B结点作为新的根节点
BinaryTree B = A->rChild;
//B的左子树作为A的右子树(因为B这边都是比A大，所以只能为右子树)
A->rChild = B->lChild;
//A作为B的左子树
B->lChild = A;
A->height = max(height(A->lChild), height(A->rChild)) + 1;
B->height = max(height(B->lChild), height(B->rChild)) + 1;
*node = B;
}
3.LR型调整
LR型调整
在A的左孩子B的右孩子上插入新节点C，使得A的BF从1增大为2，按照大小关系，结点C应该作为新的根节点，其余两个结点分别作为左右孩子结点才能平衡。
算法步骤如下:
① 将B的右孩子C提升为新的根节点
② 将原来的根节点A降为C的右孩子，B降为C的左孩子
③ 各子树按照大小关系连接(BL和AR不变，CL和CR分别调整为B的右子树和A的左子树)
image
/// lr型旋转
/// @param node 原根节点
void lr_rotate(BinaryTree *node){
//先对B进行rr转换，接着再来一次ll转换
rr_rotate(&((*node)->lChild));
ll_rotate(node);
}
4.RL型调整
RL型调整
在A的右孩子B的左子树上插入新节点C，此时A的BF由-1变为-2，按照大小关系，结点C应作为新的根节点，其余两个结点分别作为左右孩子结点才能平衡。
算法步骤如下:
① 将B的左孩子C提升为新的根节点
② 将原来的根节点A降为C的左孩子，B降为C的右孩子
③ 各子树按大小关系连接(AL和BR不变，CL和CR分别调整为A的左子树和B的右子树)
image
/// rl型转换
/// @param node 原根节点
void rl_rotate(BinaryTree *node){
//先对B进行ll型转换，接着再来一次rr型转换
ll_rotate(&((*node)->rChild));
rr_rotate(node);
}
四、插入代码实现
BalanceBinaryTree.h中
#ifndef BalanceBinaryTree_h
#define BalanceBinaryTree_h
#include <stdio.h>
#include <stdlib.h>
typedef enum Status{
success = 0,//成功
fail = 1//失败
}Status;
//二叉树结点定义
typedef struct BinaryTreeNode{
int val;//存储的值
struct BinaryTreeNode *lChild,*rChild;//左右孩子
int height;//深度
}BinaryTreeNode,*BinaryTree;
Status insertVAL(BinaryTree *T,int key);
void preOrder(BinaryTree T);
#endif
BalanceBinaryTree.c中
#include "BalanceBinaryTree.h"
/// 返回高度
/// @param node 树结点
int height(BinaryTree node){
if (node == NULL) {
return 0;
}
return node->height;
}
int max(int x, int y){
return (x > y) ? x : y;
}
/// 生成一个新的结点
/// @param key 结点的值
BinaryTree newNode(int key){
BinaryTree node = (BinaryTree)malloc(sizeof(BinaryTreeNode));
node->val = key;
node->lChild = node->rChild = 0;
node->height = 1;
return node;
}
/// LL型旋转
/// @param node 原根节点
void ll_rotate(BinaryTree *node){
BinaryTree A = *node;
//取出B结点作为新的根节点
BinaryTree B = A->lChild;
//B的右子树作为A的左子树(因为B这边都是比A小，所以只能为左子树)
A->lChild = B->rChild;
//B的右子树为A
B->rChild = A;
A->height = max(height(A->lChild), height(A->rChild)) + 1;
B->height = max(height(B->lChild), height(B->rChild)) + 1;
*node = B;
}
/// rr型旋转
/// @param node 原根节点
void rr_rotate(BinaryTree *node){
BinaryTree A = *node;
//取出B结点作为新的根节点
BinaryTree B = A->rChild;
//B的左子树作为A的右子树(因为B这边都是比A大，所以只能为右子树)
A->rChild = B->lChild;
//A作为B的左子树
B->lChild = A;
A->height = max(height(A->lChild), height(A->rChild)) + 1;
B->height = max(height(B->lChild), height(B->rChild)) + 1;
*node = B;
}
/// lr型旋转
/// @param node 原根节点
void lr_rotate(BinaryTree *node){
//先对B进行rr转换，接着再来一次ll转换
rr_rotate(&((*node)->lChild));
ll_rotate(node);
}
/// rl型转换
/// @param node 原根节点
void rl_rotate(BinaryTree *node){
//先对B进行ll型转换，接着再来一次rr型转换
ll_rotate(&((*node)->rChild));
rr_rotate(node);
}
/// 获取结点的平衡因子
/// @param node 结点
int getBF(BinaryTree node){
if (!node) {
return 0;
}
return height(node->lChild) - height(node->rChild);
}
Status insertVAL(BinaryTree *T,int key){
if (!*T) {
//空树，直接新建一个结点
*T = newNode(key);
return success;
}
if (key < (*T)->val) {
//如果比结点的值小，从左子树去找地方插入
insertVAL(&((*T)->lChild), key);
} else if (key > (*T)->val) {
//如果比结点的值大，从右子树去找地方插入
insertVAL(&((*T)->rChild), key);
} else {
//相等因为没有插入新结点，所以直接返回
// return fail;
}
(*T)->height = 1 + max(height((*T)->lChild), height((*T)->rChild));
int bf = getBF(*T);
printf("%d,key:%d bf:%d\n",(*T)->val,key,bf);
if (bf > 1 && key < (*T)->lChild->val) {
//ll型
ll_rotate(T);
} else if (bf < -1 && key > (*T)->rChild->val){
//rr型
rr_rotate(T);
} else if (bf > 1 && key > (*T)->lChild->val){
//lr型
lr_rotate(T);
} else if (bf < -1 && key < (*T)->rChild->val){
//rl型
rl_rotate(T);
}
return success;
}
void preOrder(BinaryTree T){
if (!T) {
return;
}
printf("%d ",T->val);
preOrder(T->lChild);
preOrder(T->rChild);
}
我们进行测试,在main.c中：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BalanceBinaryTree.h"
int main(int argc, const char * argv[]) {
BinaryTree T = NULL;
int arr[] = {2,10,3,5,6,1,7,9};
for (int i = 0; i < 8; i++) {
insertVAL(&T, arr[i]);
}
//前序遍历
preOrder(T);
return 0;
}
/*
打印结果:
2,key:10 bf:-1
10,key:3 bf:1
2,key:3 bf:-2
10,key:5 bf:1
3,key:5 bf:-1
5,key:6 bf:-1
10,key:6 bf:2
3,key:6 bf:-1
2,key:1 bf:1
3,key:1 bf:0
10,key:7 bf:1
6,key:7 bf:-1
3,key:7 bf:-1
7,key:9 bf:-1
10,key:9 bf:2
6,key:9 bf:-1
3,key:9 bf:-1
3 2 1 6 5 9 7 10 Program ended with exit code: 0
*/
参考自:
平衡二叉树
网友评论