smatskevich

AVL Tree

May 23rd, 2015
311
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2.  
  3. class CAVLTree {
  4. public:
  5.     CAVLTree() : root( 0 ) {}
  6.     ~CAVLTree();
  7.  
  8.     void Add( int key );
  9.  
  10. private:
  11.     struct CAVLNode {
  12.         int Key;
  13.         CAVLNode* Left;
  14.         CAVLNode* Right;
  15.         int Height;
  16.  
  17.         explicit CAVLNode( int key ) : Key( key ), Left( 0 ), Right( 0 ), Height( 1 ) {}
  18.     };
  19.     CAVLNode* root;
  20.  
  21.     static void deleteNode( CAVLNode* node );
  22.     static void addNode( int key, CAVLNode*& node );
  23.     static void balance( CAVLNode*& node );
  24.     static void rotateLeft( CAVLNode*& node );
  25.     static void rotateRight( CAVLNode*& node );
  26.     static int height( CAVLNode* node );
  27.     static void fixHeight( CAVLNode* node );
  28. };
  29.  
  30. CAVLTree::~CAVLTree()
  31. {
  32.     deleteNode( root );
  33. }
  34.  
  35. void CAVLTree::deleteNode( CAVLNode* node ) {
  36.     if( node == 0 )
  37.         return;
  38.     deleteNode( node->Left );
  39.     deleteNode( node->Right );
  40.     delete node;
  41. }
  42.  
  43. void CAVLTree::Add( int key ) {
  44.     addNode( key, root );
  45. }
  46.  
  47. void CAVLTree::addNode( int key, CAVLNode*& node ) {
  48.     if( node == 0 ) {
  49.         node = new CAVLNode( key );
  50.         return;
  51.     }
  52.     if( key < node->Key ) {
  53.         addNode( key, node->Left );
  54.     } else {
  55.         addNode( key, node->Right );
  56.     }
  57.     balance( node );
  58. }
  59.  
  60. void CAVLTree::balance( CAVLNode*& node ) {
  61.     if( height( node->Right ) == height( node->Left ) + 2 ) {
  62.         if( height( node->Right->Left ) == height( node->Right->Right ) + 1 )
  63.             rotateRight( node->Right );
  64.         rotateLeft( node );
  65.     }
  66.     // + Симметричный случай...
  67. }
  68.  
  69. void CAVLTree::rotateLeft( CAVLNode*& node ) {
  70.     // Крутим...
  71.     fixHeight( node->Left );
  72.     fixHeight( node );
  73. }
  74.  
  75. int CAVLTree::height( CAVLNode* node ) {
  76.     return node == 0 ? 0 : node->Height;
  77. }
  78.  
  79. void CAVLTree::fixHeight( CAVLNode* node ) {
  80.     node->Height = std::max( height( node->Left ), height( node->Right ) ) + 1;
  81. }
  82.  
  83. int main() {
  84.     return 0;
  85. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×