怎么在C++中实现AVL树

怎么在c++中实现AVL树？相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

AVL树的介绍

AVL树是一种自平衡的二叉搜索树，它通过单旋转（single rotate）和双旋转(double rotate)的方式实现了根节点的左子树与右子树的高度差不超过1,。这有效的降低了二叉搜索树的时间复杂度，为O（log n）。那么，下面小编将详细介绍C++实现AVL树的代码。最后一步提供可靠的代码实现

这里先粘贴代码
给大家的忠告，一定要及时去实现，不然之后再实现要花更多的时间

 #ifndef _AVLTREE_#define _AVLTREE_#include<iOStream>#include<vector>#include<queue>#include<map>using namespace std;#define MAXFACTOR = 2;template<class Key , class E>class AVLnode{    private:        Key key;        E value;        AVLNode<Key,E>* left;        AVLNode<Key,E>* right;        AVLNode<Key,E>* parent;    public:        AVLNode():left(nullptr),right(nullptr),parent(nullptr){}        AVLNode(Key _key,E _value , AVLNode<Key,E>* _parent = nullptr,AVLNode<Key,E>*_left = nullptr, AVLNode<Key,E>*_right = nullptr):                key(_key),value(_value),left(_left),right(_right),parent(_parent){}                bool isLeaf(){return left==nullptr && right == nullptr ;}        //元素设置        Key geTKEy() const { return key;}        void setKey(Key set) {key = set;}                E getValue() const { return value;}        void setValue(E set) {value = set;}        AVLNode<Key,E>*  getLeft() { return left; }        void setLeft (AVLNode< Key,E >* set){ left = set;}        AVLNode<Key,E>*  getRight()  { return right;}        void setRight (AVLNode<Key,E>* set) {right = set ;}        AVLNode<Key,E>* getParent()  {return parent;}        void setParent(AVLNode<Key,E>* set) { parent = set;}};template<class Key , class E>class AVLTree{    private:        AVLNode<Key,E>* root;        void clear(AVLNode<Key,E>* &r)        {            if(r==nullptr)return;            if(r->getLeft())clear(r->getLeft());            if(r->getRight())clear(r->getRight);            delete r;         }        void Init()        {            root = new AVLNode<Key,E>();            root=nullptr;        }        void preOrder(AVLNode<Key,E>* r,void(*visit) (AVLNode<Key,E> * node))        {            if(r==nullptr)return;            (*visit) (r);            preOrder(r->getLeft() , visit);            preOrder(r->getRight(), visit);        }        void inOrder(AVLNode<Key,E>* r , void(*visit)(AVLNode<Key,E>* node) )        {            if(r==nullptr)return;            inOrder(r->getLeft() , visit);            (*visit)(r);            inOrder(r->getRight(),visit);        }        void postOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))        {            if(r==nullptr)return;            postOrder(r->getLeft(),visit);            postOrder(r->getRight(),visit);            (*visit)(r);        }        void levelOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))        {            queue< AVLNode<Key,E>* > q;            if(r==nullptr)return;            q.push(r);            while( ! q.empty() )            {                AVLNode<Key,E>* tmp = q.front();                q.pop();                (*visit)(tmp);                if(tmp->getLeft() ) q.push(tmp->getLeft() );                if(tmp->getRight()) q.push(tmp->getRight());                            }        }        AVLNode<Key,E>* find(AVLNode<Key,E>* r,Key k)        {            if(r==nullptr)return nullptr;            if(k == r->getKey() ) return r;            else if( k < r->getKey())            {                find(r->getLeft(),k);            }            else {                find(r->getRight(),k);            }        }        //Find the smallest element in the avl tree        AVLNode<Key,E>* getMin(AVLNode<Key,E>* r)        {            if(r->getLeft() == nullptr) return r;            else{                getMin(r->getLeft());            }        }        //Remove the smallest element         AVLNode<Key,E>* deleteMin(AVLNode<Key,E>* rt)        {            if(rt->getLeft() == nullptr) return rt->getRight();            else{                rt->setLeft(deleteMin(rt->getLeft()));                return rt;            }        }        AVLNode<Key,E>* leftRotate(AVLNode<Key,E>* node)        {            if( node == nullptr) return nullptr;            AVLNode<Key,E>* newHead = node->getRight();            node->setRight( newHead -> getLeft() );            newHead -> setLeft( node );            return newHead;         }        AVLNode<Key,E>* rightRotate(AVLNode<Key,E>* node)        {            if(node == nullptr)return nullptr;            AVLNode<Key,E>* newHead = node->getLeft();            node->setLeft( newHead->getRight() );            newHead ->setRight(node);            return newHead;        }        int getHeight(AVLNode<Key,E>*node)        {            if(node == nullptr)return 0;            if(node->isLeaf())return 1;            else return ( getHeight( node->getLeft() ) > getHeight( node->getRight() ) ?                        getHeight( node->getLeft() ) : getHeight( node->getRight() ) ) + 1;        }        int getBalanceFactor(AVLNode<Key,E>* node)        {            return getHeight(node->getLeft()) - getHeight(node->getRight() );        }        AVLNode<Key,E>* balance(AVLNode<Key,E>* node)        {            if(!node) return nullptr;            else if ( getBalanceFactor( node ) == 2)            {                if(getBalanceFactor( node ->getLeft() ) == 1)                {                    node = rightRotate(node);                }                else                {                    node->setLeft(leftRotate( node->getLeft() ) );                    node = rightRotate(node);                }            }            else if(getBalanceFactor( node ) == -2)            {                if(getBalanceFactor( node->getRight()) == -1)                {                    node = leftRotate(node);                }                else                {                    node->setRight( rightRotate( node->getRight() ) );                    node = leftRotate(node);                }            }            return node;        }        AVLNode<Key,E>* insert( AVLNode<Key,E>* root ,const pair<Key,E>& it)        {            if(root == nullptr)            {                return new AVLNode<Key,E>(it.first , it.second,NULL,NULL,NULL);            }            else if (it.first < root->getKey() )            {                                root ->setLeft( insert(root->getLeft() , it) ) ;            }            else{                root ->setRight( insert(root->getRight() , it) );                            }            root = balance(root);            return root;        }        AVLNode<Key,E>* remove(AVLNode<Key,E>*  node , const Key k)        {            if(node == nullptr) return nullptr;            if(node->getKey() > k)            {                node->setLeft( remove(node->getLeft() , k) );                node = balance(node);            }            else if(node->getKey() < k)            {                node->setRight( remove(node->getRight(), k) );                node = balance(node);            }            else if(node->getKey() == k)            {                if(! node->isLeaf() )                {                    AVLNode<Key,E>* tmp = getMin(node->getRight() );                    node->setKey( tmp->getKey() );                    node->setValue( tmp->getValue() );                    node->setRight( deleteMin(node->getRight() ) );                    delete tmp;                }                else {                    AVLNode<Key,E>* tmp = node;                    node = (node->getLeft() != nullptr) ? node->getLeft() : node->getRight() ;                    delete tmp;                }            }            return node;        }       public:        ~AVLTree(){clear(root);}        AVLTree(){ root = nullptr; }    //四种遍历方式        void preOrder( void (*visit)(AVLNode<Key,E>* r))        {            preOrder(root,visit);        }        void inOrder(void (*visit)(AVLNode<Key,E>* r))        {            inOrder(root,visit);        }        void postOrder(void (*visit)(AVLNode<Key,E>* r))        {            postOrder(root,visit);        }        void levelOrder( void(*visit)(AVLNode<Key,E>*r) )        {            levelOrder(root,visit);        }         //插入        void insert(const pair<Key,E> &it)        {            root = insert(root,it);        }        //删除       void remove(const Key& k)        {            remove(root,k);        }        bool find(const Key&k)        {            return find(root,k);           }               };#endif

//AVLtest.cpp#include"NewAvl.h"#include<iostream>using namespace std;template<typename Key,typename E>void traverse(AVLNode<Key,E>* root){    cout<<root->getKey()<<" "<<root->getValue()<<" ";    cout<<endl;}int main(){    AVLTree<int,int>* tree = new AVLTree<int ,int>;    for(int i = 0 ; i < 5 ; i ++)    {        tree->insert(make_pair(i,i));    }    tree->remove(1);    cout<<"PreOrder: "<<endl;    tree->preOrder(traverse);    cout<<endl;    cout<<"LevelOrder: "<<endl;    tree->levelOrder(traverse);    cout<<endl;    cout<<"InOrder: "<<endl;    tree->inOrder(traverse);    cout<<endl;    cout<<"PostOrder: "<<endl;    tree->postOrder(traverse);    cout<<endl;    cout<<tree->find(2)<<endl;    tree->insert(make_pair(9,9));    tree->levelOrder(traverse);}

运行结果

看完上述内容，你们掌握怎么在C++中实现AVL树的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注编程网其他教程频道，感谢各位的阅读！