怎么在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(){/*Init();*/ 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树的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注亿速云行业资讯频道，感谢各位的阅读！