資料結構 — AVL tree（平衡二叉樹）

# BST（二叉搜尋樹、二叉查找樹、二叉排序樹）

定義：

1、要麼是一棵空樹

2、如果不為空，那麼其左子樹節點的值都小于根節點的值；右子樹節點的值都大于根節點的值

3、其左右子樹也是二叉搜尋樹

#

定義：

 平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有别于AVL算法），且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用算法有紅黑樹、AVL、Treap、伸展樹等。

最小不平衡子樹： 以離插入結點最近、且平衡因子絕對值大于 1 的結點作根結點的子樹。

調整該子樹的分為四種情況：

（1）LL形

（2）LR形

（3）RR形

（4）RL形

代碼實作：

LR：

RL：

#include<stdio.h>
#include<iostream>
using namespace std;

#define FALSE 0
#define TRUE 1

typedef struct {
    int key;
} element;

typedef struct tree_node {
    struct tree_node *left_child;
    element data;
    short bf;
    struct tree_node *right_child;
} tree_node, *tree_pointer;

int unbalanced = FALSE;
tree_pointer root = NULL;

void left_rotation(tree_pointer *parent, int *unbalanced);
void right_rotation(tree_pointer *parent, int *unbalanced);
void avl_insert(tree_pointer *parent, element x, int *unbalanced);
/*
 *1.如果要插入的元素的父節點為空則為其配置設定記憶體并處理
 *2.如果小于父節點的資料域則插入父節點的左孩子，并旋轉
 *3.如果大于父節點的資料域則插入父節點的右孩子，并旋轉
 */
void avl_insert(tree_pointer *parent, element x, int *unbalanced) {
    if(!*parent) {
        *unbalanced = TRUE;
        *parent = new tree_node();
        (*parent)->left_child = (*parent)->right_child = NULL;
        (*parent)->bf = 0;
        (*parent)->data = x;
    }
    else if(x.key < (*parent)->data.key) {
        avl_insert(&(*parent)->left_child, x, unbalanced);
        if(*unbalanced) {
            /*
             * unbalanced表示是插完之後就不平衡了 和 判斷還用不用處理平衡因子
             */
            switch((*parent)->bf) {
                case -1:
                    (*parent)->bf = 0;
                    *unbalanced = FALSE;
                    break;
                case 0:
                    (*parent)->bf = 1;
                    break;
                case 1:
                    left_rotation(parent,unbalanced);
            }
        }
    }
    else if(x.key > (*parent)->data.key) {
        avl_insert(&(*parent)->right_child, x, unbalanced);
        if(*unbalanced) {
            switch((*parent)->bf) {
                case 1:
                    (*parent)->bf = 0;
                    *unbalanced = FALSE;
                    break;
                case 0:
                    (*parent)->bf = 1;
                    break;
                case -1:
                    right_rotation(parent, unbalanced);
            }
        }
    }
    else {
        *unbalanced = FALSE;
        printf("該元素已經存在！\n");
    }
}

void left_rotation(tree_pointer *parent, int *unbalanced) {
   tree_pointer grand_child, child;
    child = (*parent)->left_child;
    if(child->bf == 1) {
        //LL
        (*parent)->left_child = child->right_child;
        child->right_child = *parent;
        (*parent)->bf = 0;
        (*parent) = child;
    } else {
        //LR
        grand_child = child->right_child;
        child->right_child = grand_child->left_child;
        grand_child->left_child = child;
        (*parent)->left_child = grand_child->right_child;
        grand_child->right_child = (*parent);
        switch(grand_child->bf) {
            case 1:
                (*parent)->bf = -1;
                child->bf = 0;
            case 0:
                (*parent)->bf = child->bf = 0;
            case -1:
                (*parent)->bf = 0;
                child->bf = 1;
        }
        (*parent) = grand_child;
    }
    (*parent)->bf = 0;
    *unbalanced = FALSE;
}

void right_rotation(tree_pointer *parent, int *unbalanced) {
    tree_pointer grand_child, child;
    child = (*parent)->right_child;
    if(child->bf == -1) {
        //RR
        (*parent)->right_child = child->left_child;
        child->left_child = (*parent);
        (*parent) = child;
    } else {
        //RL
        grand_child = child->left_child;

        child->left_child = grand_child->right_child;
        grand_child->right_child = child;
        (*parent)->right_child = grand_child->left_child;
        grand_child->left_child = (*parent);
        switch(grand_child->bf) {
            case 1:
                (*parent)->bf = 0;
                child->bf = -1;
            case 0:
                (*parent)->bf = child->bf = 0;
            case -1:
                (*parent)->bf = 1;
                child->bf = 0;
        }
        (*parent) = grand_child;
    }
    (*parent)->bf = 0;
    *unbalanced = FALSE;
}
void raverse(tree_pointer root) {
    if(root) {
        printf("%d ",root->data.key);
        raverse(root->left_child);
        raverse(root->right_child);
    }
}
int main() {
    int arr[11] = {15,6,18,3,7,17,20,2,4,13,9};
    element arr_x[11];
    for(int i = 0; i<11; i++) {
    
        arr_x[i].key = arr[i];
     //   cout<<arr_x[i].key<<endl;
        avl_insert(&root, arr_x[i], &unbalanced);
    }
    
    raverse(root);
    printf("\n");
    return 0;
}