七浑彰、二叉樹(九)园细、平衡二叉樹

數(shù)據(jù)結(jié)構(gòu)目錄

一歪赢、定義(AVL樹)

平衡二叉樹定義(AVL):
要么它是一顆空樹，或者具有以下性質(zhì)的二叉排序樹:它的左子樹和右子樹都是平衡二叉樹导梆，且左子樹和右子樹的深度之差的絕對值不超過1.

左邊不是二叉排序樹

左邊45結(jié)點(diǎn)左右深度之差為2轨淌，大于1

二、平衡二叉樹相關(guān)概念

平衡因子BF(Balance Factor):
將二叉樹上結(jié)點(diǎn)的左子樹高度減去右子樹高度的值稱為該結(jié)點(diǎn)的平衡因子BF(Balance Factor)看尼。

也就是說递鹉，對于平衡二叉樹，BF的取值范圍為[-1,1]藏斩，如果發(fā)現(xiàn)某個(gè)結(jié)點(diǎn)的BF值不在此范圍躏结，則需要對樹進(jìn)行調(diào)整。

最小不平衡樹
距離插入結(jié)點(diǎn)最近的狰域，且平衡因子的絕對值大于1的結(jié)點(diǎn)的根的子樹媳拴。

最小不平衡樹

如圖所示黄橘，左邊二叉樹的結(jié)點(diǎn)45的BF=1，而在插入43結(jié)點(diǎn)后屈溉，45結(jié)點(diǎn)的BF=2塞关。結(jié)點(diǎn)45是距離插入結(jié)點(diǎn)43最近的BF不在[-1,1]范圍內(nèi)的結(jié)點(diǎn)，因此以結(jié)點(diǎn)45為根節(jié)點(diǎn)的子樹為最小不平衡樹子巾。

三帆赢、平衡二叉樹的平衡調(diào)整

定義

typedef enum Status{
    success = 0,//成功
    fail = 1//失敗
}Status;

//二叉樹結(jié)點(diǎn)定義
typedef struct BinaryTreeNode{
    int val;//存儲(chǔ)的值
    struct BinaryTreeNode *lChild,*rChild;//左右孩子
    int height;//深度
}BinaryTreeNode,*BinaryTree;

實(shí)現(xiàn)過程就是通過在一棵平衡二叉樹中一次插入結(jié)點(diǎn)(按照二叉排序樹的方式)，若出現(xiàn)不平衡线梗，則要根據(jù)新插入的結(jié)點(diǎn)與最低不平衡結(jié)點(diǎn)的位置關(guān)系進(jìn)行相應(yīng)調(diào)整椰于。分為LL型、RR型仪搔、LR型和RL型四種類型瘾婿，各調(diào)整方法如下(用A表示最低不平衡結(jié)點(diǎn))。

1.LL型調(diào)整

LL型調(diào)整

在A的左孩子的左孩子上插入新節(jié)點(diǎn)烤咧，使得A的BF從1增到2偏陪，按照大小關(guān)系，結(jié)點(diǎn)B應(yīng)作為新的根節(jié)點(diǎn)髓削，其余兩個(gè)結(jié)點(diǎn)分別作為左右孩子結(jié)點(diǎn)才能平衡竹挡，A結(jié)點(diǎn)就好像是繞結(jié)點(diǎn)B順時(shí)針旋轉(zhuǎn)一樣。

具體算法步驟如下:
① 將A的左孩子B提升為新的根節(jié)點(diǎn)
② 將原來的根節(jié)點(diǎn)A降為B的右孩子
③ 各子樹按照大小關(guān)系連接(BL和AR不變立膛，BR調(diào)整為A的左子樹)

image

/// LL型旋轉(zhuǎn)
/// @param node 原根節(jié)點(diǎn)
void ll_rotate(BinaryTree *node){
    BinaryTree A = *node;
    //取出B結(jié)點(diǎn)作為新的根節(jié)點(diǎn)
    BinaryTree B = A->lChild;
    //B的右子樹作為A的左子樹(因?yàn)锽這邊都是比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型調(diào)整

RR型調(diào)整

在A的右孩子B的右孩子上插入新結(jié)點(diǎn)C，使得A的平衡因子BF從-1變?yōu)?2宝泵，按照大小關(guān)系好啰，結(jié)點(diǎn)B應(yīng)作為新的根節(jié)點(diǎn)，其余兩個(gè)結(jié)點(diǎn)分別作為左右孩子結(jié)點(diǎn)才能平衡儿奶，A結(jié)點(diǎn)就好像是繞B逆時(shí)針旋轉(zhuǎn)一樣框往。

具體算法步驟如下：
① 將A的右孩子B提升為新的根節(jié)點(diǎn)
② 將原來的根節(jié)點(diǎn)A降為B的左孩子
③ 各子樹按照大小關(guān)系(AL和BR不變，將BL調(diào)整為A的右子樹)

image

/// rr型旋轉(zhuǎn)
/// @param node 原根節(jié)點(diǎn)
void rr_rotate(BinaryTree *node){
    BinaryTree A = *node;
    //取出B結(jié)點(diǎn)作為新的根節(jié)點(diǎn)
    BinaryTree B = A->rChild;
    //B的左子樹作為A的右子樹(因?yàn)锽這邊都是比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型調(diào)整

LR型調(diào)整

在A的左孩子B的右孩子上插入新節(jié)點(diǎn)C椰弊，使得A的BF從1增大為2，按照大小關(guān)系瓤鼻，結(jié)點(diǎn)C應(yīng)該作為新的根節(jié)點(diǎn)秉版，其余兩個(gè)結(jié)點(diǎn)分別作為左右孩子結(jié)點(diǎn)才能平衡。

算法步驟如下:
① 將B的右孩子C提升為新的根節(jié)點(diǎn)
② 將原來的根節(jié)點(diǎn)A降為C的右孩子茬祷，B降為C的左孩子
③ 各子樹按照大小關(guān)系連接(BL和AR不變清焕，CL和CR分別調(diào)整為B的右子樹和A的左子樹)

image

/// lr型旋轉(zhuǎn)
/// @param node 原根節(jié)點(diǎn)
void lr_rotate(BinaryTree *node){
    //先對B進(jìn)行rr轉(zhuǎn)換，接著再來一次ll轉(zhuǎn)換
    rr_rotate(&((*node)->lChild));
    ll_rotate(node);
}

4.RL型調(diào)整

RL型調(diào)整

在A的右孩子B的左子樹上插入新節(jié)點(diǎn)C，此時(shí)A的BF由-1變?yōu)?2秸妥，按照大小關(guān)系滚停，結(jié)點(diǎn)C應(yīng)作為新的根節(jié)點(diǎn)，其余兩個(gè)結(jié)點(diǎn)分別作為左右孩子結(jié)點(diǎn)才能平衡粥惧。

算法步驟如下:
① 將B的左孩子C提升為新的根節(jié)點(diǎn)
② 將原來的根節(jié)點(diǎn)A降為C的左孩子键畴，B降為C的右孩子
③ 各子樹按大小關(guān)系連接(AL和BR不變，CL和CR分別調(diào)整為A的左子樹和B的右子樹)

image

/// rl型轉(zhuǎn)換
/// @param node 原根節(jié)點(diǎn)
void rl_rotate(BinaryTree *node){
    //先對B進(jìn)行l(wèi)l型轉(zhuǎn)換影晓，接著再來一次rr型轉(zhuǎn)換
    ll_rotate(&((*node)->rChild));
    rr_rotate(node);
}

四镰吵、插入代碼實(shí)現(xiàn)

BalanceBinaryTree.h中


#ifndef BalanceBinaryTree_h
#define BalanceBinaryTree_h

#include <stdio.h>
#include <stdlib.h>

typedef enum Status{
    success = 0,//成功
    fail = 1//失敗
}Status;

//二叉樹結(jié)點(diǎn)定義
typedef struct BinaryTreeNode{
    int val;//存儲(chǔ)的值
    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 樹結(jié)點(diǎn)
int height(BinaryTree node){
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

int max(int x, int y){
    return (x > y) ? x : y;
}
/// 生成一個(gè)新的結(jié)點(diǎn)
/// @param key 結(jié)點(diǎn)的值
BinaryTree newNode(int key){
    BinaryTree node = (BinaryTree)malloc(sizeof(BinaryTreeNode));
    node->val = key;
    node->lChild = node->rChild = 0;
    node->height = 1;
    return node;
}


/// LL型旋轉(zhuǎn)
/// @param node 原根節(jié)點(diǎn)
void ll_rotate(BinaryTree *node){
    BinaryTree A = *node;
    //取出B結(jié)點(diǎn)作為新的根節(jié)點(diǎn)
    BinaryTree B = A->lChild;
    //B的右子樹作為A的左子樹(因?yàn)锽這邊都是比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型旋轉(zhuǎn)
/// @param node 原根節(jié)點(diǎn)
void rr_rotate(BinaryTree *node){
    BinaryTree A = *node;
    //取出B結(jié)點(diǎn)作為新的根節(jié)點(diǎn)
    BinaryTree B = A->rChild;
    //B的左子樹作為A的右子樹(因?yàn)锽這邊都是比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型旋轉(zhuǎn)
/// @param node 原根節(jié)點(diǎn)
void lr_rotate(BinaryTree *node){
    //先對B進(jìn)行rr轉(zhuǎn)換，接著再來一次ll轉(zhuǎn)換
    rr_rotate(&((*node)->lChild));
    ll_rotate(node);
}

/// rl型轉(zhuǎn)換
/// @param node 原根節(jié)點(diǎn)
void rl_rotate(BinaryTree *node){
    //先對B進(jìn)行l(wèi)l型轉(zhuǎn)換盼产，接著再來一次rr型轉(zhuǎn)換
    ll_rotate(&((*node)->rChild));
    rr_rotate(node);
}

/// 獲取結(jié)點(diǎn)的平衡因子
/// @param node 結(jié)點(diǎn)
int getBF(BinaryTree node){
    if (!node) {
        return 0;
    }
    return height(node->lChild) - height(node->rChild);
}

Status insertVAL(BinaryTree *T,int key){
    if (!*T) {
        //空樹饵婆，直接新建一個(gè)結(jié)點(diǎn)
        *T = newNode(key);
        return success;
    }
    if (key < (*T)->val) {
        //如果比結(jié)點(diǎn)的值小，從左子樹去找地方插入
        insertVAL(&((*T)->lChild), key);
    } else if (key > (*T)->val) {
        //如果比結(jié)點(diǎn)的值大戏售，從右子樹去找地方插入
        insertVAL(&((*T)->rChild), key);
    } else {
        //相等因?yàn)闆]有插入新結(jié)點(diǎn)侨核，所以直接返回
//        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);
}

我們進(jìn)行測試,在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;
}
/*
 打印結(jié)果:
 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
 */

參考自:
平衡二叉樹

七请唱、二叉樹(九)菩帝、平衡二叉樹

七、二叉樹(九)族檬、平衡二叉樹

一歪赢、定義(AVL樹)

二、平衡二叉樹相關(guān)概念

三帆赢、平衡二叉樹的平衡調(diào)整

1.LL型調(diào)整

2.RR型調(diào)整

3.LR型調(diào)整

4.RL型調(diào)整

四镰吵、插入代碼實(shí)現(xiàn)