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>

如果各位看官发现有问题，欢迎留言探讨~