数据结构学习-AVL平衡树

环境：c++ 11 + win10

ide：clion 2018.3

avl平衡树是在bst二叉查找树的基础上添加了平衡机制。

我们把平衡的bst认为是任一节点的左子树和右子树的高度差为-1,0,1中的一种情况，即不存在相差两层及以上。

所谓平衡机制就是bst在理想情况下搜索复杂度是o(logn)

但是如果在（存在某一节点，该节点的左子树的高度与右子树的高度差>1）这种状况下，复杂度会超过o(logn)

举个极端的例子如加入1,2,3,4，bst就退化为一个线性的链表，复杂度变成了o(n)

为了避免这种情况，我们在bst中引入平衡操作（旋转操作），使得bst始终不存在左右子树超过1高度差的节点。

本次代码基于我的另一篇博客的基础之上，有需要可以翻看 https://www.cnblogs.com/cyrio/p/10118132.html

平衡机制主要通过反转完成，经过归纳，可能出现以下四种不平衡的情况：ll、lr、rl、rr

l=left     r=right

我们将不平衡点设为x点，以lr为例，第一个l表示x点的左子树比右子树层数多（>1），第二个r表示多出的那部分在x点的左子树的右子树。（不管他是在x的左子树的右子树的左右哪边，都称为lr）

 

如图：

 

 接下来我们以ll、lr、rr、rl四种情况讨论。

1、ll：

通俗的讲就是把k2从k1那扯下来，然后把y移到k2的左子树，最后把k2移到k1的右子树。

2、rr：

与ll同理，把k1先扯下来，再把y接到k1的右侧，再把k1作为左子树接到k2。

 3、lr：

lr需要先做一次rr再做一次ll：

先把k1从k2那扯下来，让k2和k3连，然后把b作为k1的右子树，再把k1连到k2的左子树上。

然后再做ll，把k3从k2上面扯下来，让c作为k3的左子树，再把k3连到k2的右子树。

4、rl：

先ll再rr，与lr同理。

以上是主要思想的分析，除了旋转操作，我们还需要添加新的方法：

1、求树的高度：height方法

2、求某节点的左子树和右子树的高度差 ：diff方法      

3、一个对整个树进行判断，对里面的x节点进行对应操作：balance方法

同时avl中的insert（插入某一节点）的方法与bst中也略有不同，需要注意的是avl种的__insert（ps：带"__"的表示私有内部接口）的参数中第一个为bstnode<t> * & root （需要&引用）

具体代码如下：（此代码为完整代码，可以直接复制进自己的项目查看效果）

mybst.h

#ifndef test1_mybst_h
#define test1_mybst_h

#include <iomanip>
#include "bstnode.h"
#include <vector>
#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;

template <typename t>
class mybst{
private:
    bstnode<t> * root = nullptr;
    bstnode<t> * __search(bstnode<t> * root , const t &key){
        if (nullptr == root)
            return nullptr;
        if (key == root->data)
            return root;
        else if (key < root->data)
            return __search(root->left, key);
        else
            return __search(root->right, key);
    } //查找关键字是否存在
    bstnode<t> * __treemin(bstnode<t> * root , bstnode<t> * &parent){
        bstnode<t> * curr = root;
        while(curr->left!= nullptr){
            parent = curr;
            curr = curr->left;
        }
        return  curr;
    } //返回最小节点（一路向左）
    bstnode<t> * __insert(bstnode<t> * &root, const t &key){
        if (nullptr == root)
        {
            root = new bstnode<t>(key);
            return root;
        }//递归返回条件
        else if (key < root->data)
        {
            root->left = __insert(root->left,key);//递归左子树
            //balance operation
            root = __balance(root);//平衡操作包含了四种旋转
        }
        else if (key>root->data)
        {
            root->right = __insert(root->right,key);//递归右子树
            //balance operation
            root = __balance(root);//平衡操作包含了四种旋转
        }
        return root;
    } //插入指定值
    bool __delete(const t &key){
        bool found = false;//存储有没有找到key的变量
        if(isempty()){
            cerr<<"bst为空"<<endl;
            return false;
        }
        bstnode<t> * curr = root;
        bstnode<t> * parrent = nullptr;
        while(curr!= nullptr) {
            if (key == curr->data) {
                found = true;
                break;
            } else {
                parrent = curr;
                if (key < curr->data) curr = curr->left;
                else curr = curr->right;
            }
        }
        if(!found){
            cerr<<"未找到key！"<<endl;
            return false;
        }
        if (parrent == nullptr){//删除根节点
            root = nullptr;
            delete(curr);
            return true;
        }
        /*
         删除的节点有三种可能：
         1、叶子结点
         2、一个孩子的节点
         3、两个孩子的节点
         */
        if (__isleaf(curr)){ //删除的点是叶子结点
            if(parrent->left==curr) parrent->left= nullptr;
            else parrent->right= nullptr;
            delete(curr);
            return true;
        }
        else if(__isnodewithtwochild(curr)){ //是两个孩子的节点
            //以当前右子树中的最小值取代他
            bstnode<t> * parrent = curr;
            bstnode<t> * tmp = __treemin(curr->right,parrent);
            curr->data = tmp->data;
            if(parrent->right==tmp)
                parrent->right== nullptr;
            else parrent->left== nullptr;
            delete(tmp);
            return true;
        }
        else{ //只有一个孩子的节点
            if(curr->left!= nullptr){
                if(curr->left == curr){
                    parrent->left=curr->left;
                    delete(curr);
                    return true;
                }
                else{
                    parrent->right=curr->right;
                    delete(curr);
                    return true;
                }
            }
            if(curr->right!= nullptr){
                if(curr->left == curr){
                    parrent->left=curr->left;
                    delete(curr);
                    return true;
                }
                else{
                    parrent->right=curr->right;
                    delete(curr);
                    return true;
                }
            }
        }
        return false;
    } //删除指定值
    bool __isleaf(bstnode<t> * const & root){
        if(root->left== nullptr && root->right== nullptr) return true;
        else return false;
    }//判断是否是叶子节点
    bool __isnodewithtwochild(bstnode<t> * const & root){
        if(root->left!= nullptr && root->right!= nullptr) return true;
        else return false;
    }//判断是否有两个孩子
    void __inordertraversal(bstnode<t> *root,std::vector<int>&result){
        if(nullptr == root) return;
        __inordertraversal(root->left,result);
        cout<<root->data<<" ";
        result.push_back(root->data);
        __inordertraversal(root->right,result);
    }//中序遍历
    void __preordertraversal(bstnode<t> *root,std::vector<int>&result){
        if(nullptr == root) return;
        cout<<root->data<<" ";
        result.push_back(root->data);
        __inordertraversal(root->left,result);
        __inordertraversal(root->right,result);
    }//前序遍历
    void __postordertraversal(bstnode<t> *root,std::vector<int>&result){
        if(nullptr == root) return;
        __inordertraversal(root->left,result);
        __inordertraversal(root->right,result);
        cout<<root->data<<" ";
        result.push_back(root->data);
    }//后序遍历
    void __deleteallnodes(bstnode<t> *root){
        if (root == nullptr) return;
        __deleteallnodes(root->left);
        __deleteallnodes(root->right);
        __delete(root->data);
    }//删除所有节点
    void __bftraversal(vector<t>&result) {
        deque<bstnode<t> *> tqueue;
        bstnode<t> *pointer = root;
        if (pointer != nullptr) {
            tqueue.push_back(pointer);
        }
        while (!tqueue.empty()) {
            pointer = tqueue.front();
            tqueue.pop_front();
            cout << pointer->data << " ";
            result.push_back(pointer->data);
            if (pointer->left != nullptr) tqueue.push_back(pointer->left);
            if (pointer->right != nullptr) tqueue.push_back(pointer->right);
        }
    } //广度搜索来进行周游
    void __graph(int indent,bstnode<t>* root){
        if(root != 0){
            __graph(indent + 8, root->right);
            cout<<setw(indent)<<" "<<root->data<<endl;
            __graph(indent + 8, root->left);
        }
    } //横着画图的内部接口
    bstnode<t> * __getroot(){
        return root;
    } //返回根节点的内部接口
    //以下为avl平衡树新加的方法
    int __height(const bstnode<t>* root){
        if(root == nullptr){
            return 0;
        }
        return max(__height(root->left),__height(root->right))+1;
    } //求树的高度
    int __diff(const bstnode<t>* root){
        return __height(root->left)-__height(root->right);
    } //求节点的高度差（平衡因子）
    bstnode<t> * __ll__rotation(bstnode<t> * root){
        bstnode<t> * tmp;
        tmp = root->left;
        root->left = tmp->right;
        tmp->right = root;
        return tmp;
    } //单旋转-左左
    bstnode<t> * __rr__rotation(bstnode<t> * root){
        bstnode<t> * tmp;
        tmp = root->right;
        root->right = tmp->left;
        tmp->left = root;
        return tmp;
    } //单旋转-右右
    bstnode<t> * __lr__rotation(bstnode<t> * root){
        bstnode<t> * tmp;
        tmp = root->left;
        root->left = __rr__rotation(tmp);
        return __ll__rotation(root);
    } //双旋转-左右型，先右后左转（注意此处相反）
    bstnode<t> * __rl__rotation(bstnode<t> * root){
        bstnode<t> * tmp;
        tmp = root->right;
        root->right = __ll__rotation(tmp);
        return __rr__rotation(root);
    } //双旋转-右左型，先左后右转
    bstnode<t> * __balance(bstnode<t> * root){
        int balancefactor = __diff(root);//__diff用来计算平衡因子（左右子树高度差）
        if (balancefactor > 1)//左子树高于右子树
        {
            if (__diff(root->left) > 0)//左左外侧
                root=__ll__rotation(root);
            else//左右内侧
                root=__lr__rotation(root);
        }
        else if (balancefactor < -1)//右子树高于左子树
        {
            if (__diff(root->right) > 0)//右左内侧
                root=__rl__rotation(root);
            else//右右外侧
                root=__rr__rotation(root);
        }
        return root;
    } //平衡的内部操作
public:
    mybst(){
        root = nullptr;
    } //默认构造
    mybst(vector<t> arr){
        root = nullptr;
        for(int i =0;i<(t)arr.size();i++){
            insert(arr[i]);
        }
    }
    mybst(t * arr,int len){
        root = nullptr;
        for(int i =0;i<len;i++){
            __insert(*(arr+i));
        }
    }
    ~mybst(){
        bstnode<t> * curr = root;
        __deleteallnodes(curr);
    }//析构
    bool isempty() const{
        return root == nullptr;
    }//判断树空
    bool search(const t &key){
        bstnode<t> * temp = __search(root, key);
        return (temp == nullptr) ? false : true;
    }//查找关键字是否存在的对外接口
    bool insert(const t &key){
        return __insert(root,key);
    }//插入节点的外部接口
    bool delete(const t &key){
        return __delete(key);
    }//删除节点的外部接口
    void inordertraversal(vector<t>&result){
        __inordertraversal(root, result);
    }//中序遍历的外部接口
    void preordertraversal(vector<t>&result){
        __preordertraversal(root, result);
    }//前序遍历的外部接口
    void postordertraversal(vector<t>&result){
        __postordertraversal(root, result);
    }//后序遍历的外部接口
    void bftraversal(vector<t>&result){
        return __bftraversal(result);
    } //广度搜索外部接口
    void graph(int indent,bstnode<t>* root){
        return __graph(indent,root);
    } //横着画图的外部接口
    bstnode<t> * getroot(){
        return __getroot();
    } //返回根节点的外部接口
};

#endif //test1_mybst_h

bstnode.h

#ifndef test1_bstnode_h
#define test1_bstnode_h
template <typename t>
class bstnode{
public:
    t data;
    bstnode* left;
    bstnode* right;
    bstnode(){
        data = 0;
        left = nullptr;
        right = nullptr;
    }
    bstnode(t val){
        data = val;
        left = nullptr;
        right = nullptr;
    }
};
#endif //test1_bstnode_h

main.cpp

#include <iostream>
#include <vector>
#include "mybst.h"
#include "bstnode.h"
using namespace std;
int main() {
    vector<int> in = {7,6,5,13,17,22,10,3,2,1};
    mybst<int> bst(in);
    bst.delete(5);
    bst.insert(4);
    bool found = bst.search(4);
    if(!found)
        cout<<"not found!"<<endl;
    else
        cout<<"found!"<<endl;
    vector<int> result;
    cout<<"inordertravelsal:  ";
    bst.inordertraversal(result);
    cout<<endl<<"preordertravelsal:  ";
    bst.preordertraversal(result);
    cout<<endl<<"postordertraversal:  ";
    bst.postordertraversal(result);
    cout<<endl<<"bftraversal:  ";
    bst.bftraversal(result);
    cout<<endl<<"graph:"<<endl;
    bstnode<int>* pointer = bst.getroot();
    bst.graph(0,pointer);
    return 0;
}

 

参考：https://blog.csdn.net/zhangxiao93/article/details/51459743