平衡树

AVLtree.h

#ifndef _AVLTREE_H_
#define _AVLTREE_H_

#include <iostream>

namespace model_AVLtree {
using std::cout;
#define nullptr 0
  class AVLtree {
      private:  
    struct node {
        int item;
        int bf;
        node *rchild,*lchild;
    };
    void visit( node *p );
    void destory( node *p );
    void R_Rotate( node *&p );
    void L_Rotate( node *&p );
    void AVL_insert( node *&p, int num, bool &tall );
    bool AVL_find( node *p, int n );
    void Left_balance( node *&p );
    void Right_balance( node *&p );
    node *head;
      public:
    AVLtree(){ head = nullptr; }
    ~AVLtree();
    void output();
    void insert( int n);
    bool find( int n);
  };

  void AVLtree::R_Rotate( node *&p ) {
      node *q = p->lchild;
      p->lchild = q->rchild;
      q->rchild = p;
      p = q;
  }

  void AVLtree::L_Rotate( node *&p ) {
      node *q = p->rchild;
      p->rchild = q->lchild;
      q->lchild = p;
      q = p;
  }

  void AVLtree::Left_balance( node *&p ) {
      node *q = p->lchild;
      switch (q->bf) {
    case 1:
       p->bf = q->bf = 0;
       R_Rotate(p);
       break;
    case -1:
       node *k = q->rchild;
       switch (k->bf) {
          case 1:p->bf = -1; q->bf = 0;break;
          case -1:p->bf = 0; q->bf = -1;break;
           }
       k->bf = 0;
       L_Rotate(q);
       R_Rotate(p);
      }
  }

  void AVLtree::Right_balance( node *&p ) {
      node *q = p->rchild;
      switch (q->bf) {
    case -1:
       p->bf = q->bf = 0;
       L_Rotate(p);
       break;
    case 1:
      node *k = q->lchild;
       switch (k->bf) {
          case 1:p->bf = 0;q->bf = -1;break;
          case -1:p->bf = 1;q->bf = 0;break;
       }
       k->bf = 0;
       R_Rotate(q);
       L_Rotate(p);
      }
  }


  void AVLtree::AVL_insert( node *&now, int num, bool &tall) {
      if(now == nullptr){
         now = new node;
         now->item = num;
         now->rchild = now->lchild = nullptr;
         now->bf = 0;
     tall = true;
         return ;
      }
      if(num < now->item) {
         AVL_insert( now->lchild, num, tall);
         if(tall) 
        switch (now->bf) {
           case 1:Left_balance(now); tall = false; break;
           case 0:now->bf = 1; break;
           case -1:now->bf = 0; tall = false; break;
        }
      }
      else {
     AVL_insert( now->rchild, num, tall );
     if(tall)
        switch (now->bf) {
               case -1:Right_balance(now); tall = false; break;
               case 0:now->bf = 1; break;
               case 1:now->bf = 0; tall = false;  break;
            }
      }
  }

  AVLtree::~AVLtree() {
     destory( head );
  }

  void AVLtree::destory( node *p ) {
     if(p == nullptr) return;
     destory(p->lchild);
     destory(p->rchild);
     delete p;
  }

  void AVLtree::insert( int n ) {
     bool tall = false;
     AVL_insert( head, n, tall );
  }
  
  bool AVLtree::find( int n ) {
     if(AVL_find( head, n ))return true;
     return false;;
  }

  bool AVLtree::AVL_find( node *p, int n ) {
     if(!p) return false;
     if(n == p->item) return true;
     if(AVL_find( p->lchild, n )) return true;
     if(AVL_find( p->rchild, n )) return true;
     return false;
  }

  void AVLtree::visit( node *p ) {
     if(!p) return;
     visit(p->lchild);
     cout<<p->item<<" ";
     visit(p->rchild); 
  }

  void AVLtree::output(){
     visit(head);
  }

}
#endif

测试文件AVLtree.cpp，头文件中只有插入，没有删除操作。

#include "AVLtree.h"
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using namespace model_AVLtree;

int main() {
   int n,a;
   int i;
   AVLtree s;
   cin>>n;
   for( i=0; i<n; i++) {
      cin>>a;
      s.insert(a);
      if(s.find(a))cout<<"get"<<endl;
   }
   s.output(); 
   return 0;
}