smatskevich

AVLTree for strings

Dec 3rd, 2016
179
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <assert.h>
  3. #include <iostream>
  4. #include <string>
  5. using std::string;
  6.  
  7. class CAVLTree {
  8. public:
  9.     CAVLTree() : root( 0 ) {}
  10.     ~CAVLTree() { clear( root ); }
  11.    
  12.     bool Has( const string& key ) const;
  13.     bool Add( const string& key );
  14.     bool Remove( const string& key ) { return false; }
  15.  
  16. private:
  17.     // Узел дерева.
  18.     struct CAVLNode {
  19.         string Key;
  20.         CAVLNode* Left;
  21.         CAVLNode* Right;
  22.         int Depth;
  23.  
  24.         explicit CAVLNode( const string& key ) : Key( key ), Left( 0 ), Right( 0 ), Depth( 1 ) {}
  25.     };
  26.     CAVLNode* root;
  27.  
  28.     void clear( CAVLNode* node );
  29.     bool add( CAVLNode*& node, const string& key );
  30.     void balance( CAVLNode*& node );
  31.     static int depth( CAVLNode* node );
  32.     static void rotateLeft( CAVLNode*& node );
  33.     static void rotateRight( CAVLNode*& node );
  34.     static void fixDepth( CAVLNode* node );
  35. };
  36.  
  37. // Рекурсивная очистка всего поддерева.
  38. void CAVLTree::clear( CAVLNode* node )
  39. {
  40.     if( node == 0 ) {
  41.         return;
  42.     }
  43.     clear( node->Left );
  44.     clear( node->Right );
  45.     delete node;
  46. }
  47.  
  48. bool CAVLTree::Has( const string& key ) const
  49. {
  50.     CAVLNode* node = root;
  51.     while( node != 0 ) {
  52.         if( node->Key == key ) {
  53.             return true;
  54.         }
  55.         node = node->Key < key ? node->Right : node->Left;
  56.     }
  57.     return false;
  58. }
  59.  
  60. bool CAVLTree::Add( const string& key )
  61. {
  62.     return add( root, key );
  63. }
  64.  
  65. // Добавление ключа. Если ключ уже есть, вернет false.
  66. // Иначе добавит ключ, сделает балансировку во всем поддереве на пути до добавленного элемента.
  67. bool CAVLTree::add( CAVLNode*& node, const string& key )
  68. {
  69.     if( node == 0 ) {
  70.         node = new CAVLNode( key );
  71.         return true;
  72.     }
  73.     if( node->Key == key ) {
  74.         return false;
  75.     }
  76.     if( node->Key < key ) {
  77.         add( node->Right, key );
  78.     }
  79.     //...
  80.     return true;
  81. }
  82.  
  83. void CAVLTree::balance( CAVLNode*& node )
  84. {
  85.     const int bFactor = depth( node->Left ) - depth( node->Right );
  86.     if( bFactor == -2 ) {
  87.         const int rightBFactor = depth( node->Right->Left ) - depth( node->Right->Right );
  88.         if( rightBFactor == 1 ) {
  89.             rotateRight( node->Right );
  90.         }
  91.         rotateLeft( node );
  92.     } else if( bFactor == 2 ) {
  93.         const int leftBFactor = depth( node->Left->Left ) - depth( node->Left->Right );
  94.         if( leftBFactor == -1 ) {
  95.             rotateLeft( node->Left );
  96.         }
  97.         rotateRight( node );
  98.     } else {
  99.         fixDepth( node );
  100.     }
  101. }
  102.  
  103. int CAVLTree::depth( CAVLNode* node )
  104. {
  105.     return node == 0 ? 0 : node->Depth;
  106. }
  107.  
  108. // Левый поворот.
  109. void CAVLTree::rotateLeft( CAVLNode*& node )
  110. {
  111.     assert( node != 0 );
  112.     assert( node->Right != 0 );
  113.     CAVLNode* right = node->Right;
  114.     node->Right = right->Left;
  115.     right->Left = node;
  116.     node = right;
  117.  
  118.     fixDepth( node->Left );
  119.     fixDepth( node );
  120. }
  121.  
  122. // Правый поворот.
  123. void CAVLTree::rotateRight( CAVLNode*& node )
  124. {
  125.     assert( node != 0 );
  126.     assert( node->Left != 0 );
  127.     CAVLNode* left = node->Left;
  128.     node->Left = left->Right;
  129.     left->Right = node;
  130.     node = left;
  131.  
  132.     fixDepth( node->Right );
  133.     fixDepth( node );
  134. }
  135.  
  136. // Восстановить глубину в узле node по дочерним.
  137. void CAVLTree::fixDepth( CAVLNode* node )
  138. {
  139.     assert( node != 0 );
  140.     node->Depth = std::max( depth( node->Left ), depth( node->Right ) ) + 1;
  141. }
  142.  
  143. int main()
  144. {
  145.     CAVLTree tree;
  146.     while( true ) {
  147.         char command = 0;
  148.         string value;
  149.         std::cin >> command >> value;
  150.         if( std::cin.fail() ) {
  151.             break;
  152.         }
  153.         switch( command ) {
  154.         case '?':
  155.             std::cout << ( tree.Has( value ) ? "OK" : "FAIL" ) << std::endl;
  156.             break;
  157.         case '+':
  158.             std::cout << ( tree.Add( value ) ? "OK" : "FAIL" ) << std::endl;
  159.             break;
  160.         case '-':
  161.             std::cout << ( tree.Remove( value ) ? "OK" : "FAIL" ) << std::endl;
  162.             break;
  163.         }
  164.     }
  165.     return 0;
  166. }
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.

×