C++Linux平衡二叉搜索樹簡介

avltree， 平衡二叉查找樹，是一種特殊情況下的二叉查找樹，它的特殊之處在於，對於每一個節點，其左子樹深度和右子樹深度之差的絕對值不大於1.

自從上次寫完BSTree後，心裡想寫AVL樹了，查了點資料，感覺自己之前的結構是真的low，哎，知恥而後勇，先說一下這次的avl與上次bstree的兩點不同：

1）節點數據結構中新增了一個高度變量，代碼如下：

<code>struct Node{

    struct Node *left;
    struct Node *right;
    int val;
    int height;
    Node(int x):val(x), height(1), left(NULL), right(NULL){}
};/<code>

2）邏輯上，該樹的根節點，多了一個父節點，該父節點沒有實際意義，只是為了方便後續的所有關於該樹的增刪改查（別想到數據庫。。。）的操作。形式如下圖：

之後就要開啟我們的插入和刪除操作了，為什麼沒有查找？由於avl是一種bst，所以查找操作不在此贅述。

插入時，由於要保證平衡這一性質，所以要針對不同不平衡情況進行分別處理，其中，不平衡的情況分為左左失衡，右右失衡，左右失衡，右左失衡，下面進行分情況討論處理，這裡有一點需要說明的是，以上四種情況都要找到，發生不平衡的最低的樹節點。

左左失衡：情況如圖：

調整後的結果如下圖：

代碼奉上：

<code>struct Node *avltree::ll_rotate(struct Node *y){

    struct Node *x = y->left;
    y->left = x->right;
    x->right = y;
    y->height = std::max(getHeight(y->left), getHeight(y->right)) +1;
    x->height = std::max(getHeight(x->left), getHeight(x->right)) +1;
return x;}/<code>

右右失衡情況如下圖：

調整後如下圖：

代碼奉上：

<code>struct Node *avltree::rr_rotate(struct Node *y){

    struct Node *x = y->right;
    y->right = x->left;
    x->left = y;
    y->height = std::max(getHeight(y->left), getHeight(y->right)) +1;
    x->height = std::max(getHeight(x->left), getHeight(x->right)) +1;
    return x;
}/<code>

左右失衡如下圖，這種情況需要先將x按照右右失衡情況處理，轉換為左左失衡，然後按照左左失衡處理：

第一步處理完後，如下圖：

之後就按照左左失衡處理就行了，代碼奉上：

<code>struct Node *avltree::lr_rotate(struct Node *y){

    struct Node *x = y->left;
    y->left = rr_rotate(x);
    return ll_rotate(y);
}/<code>

需要一線互聯網大廠的面試資料以及c/c++Linux視頻資料後臺私信“1”免費領取！

右左失衡如下圖，這種情況需要先將x按照左左失衡情況處理，轉換為右右失衡，然後按照右右失衡處理：：

第一步調整後的結果如下圖：

之後就按照右右失衡處理就行了，代碼奉上：

<code>struct Node *avltree::rl_rotate(struct Node *y){

    struct Node *x = y->right;
    y->right = ll_rotate(x);
    return rr_rotate(y);
}/<code>

接下來奉上整個插入代碼：

<code>struct Node *avltree::insert(int k, struct Node *node){

    if(node == NULL) return (new struct Node(k));
    if(k val) node->left=insert(k, node->left);
    else if( k > node->val) node->right=insert(k, node->right);
    else return node;
    node->height = std::max(getHeight(node->right), getHeight(node->left)) + 1;
    int balance = isBalance(node);
    if(balance > 1 && isBalance(node->left)>0) return ll_rotate(node);
    if(balance > 1 && isBalance(node->left)<0) return lr_rotate(node);
    if(balance right) > 0) return rl_rotate(node);
    if(balance right) left = insert(k, root->left);
}/<code>

刪除的話，跟插入是非常類似的，直接上代碼了~：

<code>struct Node *avltree::delNode(int k, struct Node *node){

    if(node==NULL) return NULL;
    if(k val) node->left = delNode(k, node->left);
    else if(k > node->val) node->right = delNode(k, node->right);
    else{
        if(node->left && node->right){
            struct Node *x = node->right;
            while(x->left) x = x->left;
            node->val = x->val;
            node->right = delNode(x->val, node->right);
        }else{
            struct Node *p = node;
            node = node->left?node->left:node->right;
            delete p, p = NULL;
            if(node == NULL) return NULL;
        }
    }
    node->height = std::max(getHeight(node->right), getHeight(node->left)) + 1;
    int balance = isBalance(node);
    if(balance > 1 && isBalance(node->left)>0) return ll_rotate(node);
    if(balance > 1 && isBalance(node->left)<0) return lr_rotate(node);
    if(balance right) > 0) return rl_rotate(node);
    if(balance right) left = delNode(k, root->left);
}/<code>

整個類的代碼如下：

<code>#ifndef AVLTREE_H

#define AVLTREE_H
#include 
struct Node{
    struct Node *left;
    struct Node *right;
    int val;
    int height;
    Node(int x):val(x), height(1), left(NULL), right(NULL){}
};

class avltree
{
public:
    avltree();
    int isBalance(struct Node *node);
    int getHeight(struct Node *node);
    struct Node *ll_rotate(struct Node *y);
    struct Node *rr_rotate(struct Node *y);
    struct Node *lr_rotate(struct Node *y);
    struct Node *rl_rotate(struct Node *y);
    struct Node *insert(int k, struct Node *node);
    void insert(int k);
    struct Node *delNode(int k, struct Node *node);
    void delNode(int k);
    struct Node *root;
};

#endif // AVLTREE_H/<code>

<code>avltree::avltree(){

    root = new struct Node(0);
}
int avltree::isBalance(struct Node *node){
    if(node == NULL) return 0;
    return getHeight(node->left) - getHeight(node->right);
}
int avltree::getHeight(struct Node *node){
    if(node == NULL) return 0;
    return node->height;
}
struct Node *avltree::ll_rotate(struct Node *y){
    struct Node *x = y->left;
    y->left = x->right;
    x->right = y;
    y->height = std::max(getHeight(y->left), getHeight(y->right)) +1;
    x->height = std::max(getHeight(x->left), getHeight(x->right)) +1;
    return x;
}
struct Node *avltree::rr_rotate(struct Node *y){
    struct Node *x = y->right;
    y->right = x->left;
    x->left = y;
    y->height = std::max(getHeight(y->left), getHeight(y->right)) +1;
    x->height = std::max(getHeight(x->left), getHeight(x->right)) +1;
    return x;
}
struct Node *avltree::lr_rotate(struct Node *y){
    struct Node *x = y->left;
    y->left = rr_rotate(x);
    return ll_rotate(y);
}
struct Node *avltree::rl_rotate(struct Node *y){
    struct Node *x = y->right;
    y->right = ll_rotate(x);
    return rr_rotate(y);
}
struct Node *avltree::insert(int k, struct Node *node){
    if(node == NULL) return (new struct Node(k));
    if(k val) node->left=insert(k, node->left);
    else if( k > node->val) node->right=insert(k, node->right);
    else return node;
    node->height = std::max(getHeight(node->right), getHeight(node->left)) + 1;
    int balance = isBalance(node);
    if(balance > 1 && isBalance(node->left)>0) return ll_rotate(node);
    if(balance > 1 && isBalance(node->left)<0) return lr_rotate(node);
    if(balance right) > 0) return rl_rotate(node);
    if(balance right) left = insert(k, root->left);
}
struct Node *avltree::delNode(int k, struct Node *node){
    if(node==NULL) return NULL;
    if(k val) node->left = delNode(k, node->left);
    else if(k > node->val) node->right = delNode(k, node->right);
    else{
        if(node->left && node->right){
            struct Node *x = node->right;
            while(x->left) x = x->left;
            node->val = x->val;
            node->right = delNode(x->val, node->right);
        }else{
            struct Node *p = node;
            node = node->left?node->left:node->right;
            delete p, p = NULL;
            if(node == NULL) return NULL;
        }
    }
    node->height = std::max(getHeight(node->right), getHeight(node->left)) + 1;
    int balance = isBalance(node);
    if(balance > 1 && isBalance(node->left)>0) return ll_rotate(node);
    if(balance > 1 && isBalance(node->left)<0) return lr_rotate(node);
    if(balance right) > 0) return rl_rotate(node);
    if(balance right) left = delNode(k, root->left);
}/<code>

如果各位看官發現有問題，歡迎留言探討~