smatskevich

AVLTreeInHabraStyle

May 3rd, 2017
218
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();
  6.     ~CAVLTree();
  7.  
  8.     void Add( int key );
  9.     void Remove( int key );
  10.     bool Has( int key );
  11.  
  12. private:
  13.     struct CAVLNode {
  14.         int Key;
  15.         int Depth;
  16.         CAVLNode* Left;
  17.         CAVLNode* Right;
  18.         explicit CAVLNode( int key ) : Key( key ), Depth( 1 ), Left( 0 ), Right( 0 ) {}
  19.     };
  20.     CAVLNode* root;
  21.  
  22.     // Безопасное вычисление глубины поддерева.
  23.     static int depth( CAVLNode* node ) { return node == 0 ? 0 : node->Depth; }
  24.     void add( int key, CAVLNode*& node );
  25.     void balance( CAVLNode*& node );
  26.     void rotateLeft( CAVLNode*& node );
  27.     void rotateRight( CAVLNode*& node );
  28.     void fixDepth( CAVLNode*& node );
  29. };
  30.  
  31. void CAVLTree::Add( int key )
  32. {
  33.     add( key, root );
  34. }
  35.  
  36. // Рекурсивный метод добавления элемента в поддерево.
  37. void CAVLTree::add( int key, CAVLNode*& node )
  38. {
  39.     if( node == 0 ) {
  40.         node = new CAVLNode( key );
  41.         return;
  42.     }
  43.     if( node->Key > key ) {
  44.         add( key, node->Left );
  45.     } else {
  46.         // Больше или равные ключи добавляем вправо.
  47.         add( key, node->Right );
  48.     }
  49.     balance( node );
  50. }
  51.  
  52. // Восстановление балансировки при необходимости с помощью поворотов.
  53. void CAVLTree::balance( CAVLNode*& node )
  54. {
  55.     if( depth( node->Left ) - depth( node->Right ) == 2 ) {
  56.         if( depth( node->Left->Left ) - depth( node->Left->Right ) == -1 ) {
  57.             rotateLeft( node->Left );
  58.         }
  59.         rotateRight( node );
  60.     } else if( depth( node->Left ) - depth( node->Right ) == -2 ) {
  61.         if( depth( node->Right->Left ) - depth( node->Right->Right ) == 1 ) {
  62.             rotateRight( node->Right );
  63.         }
  64.         rotateLeft( node );
  65.     }
  66.     fixDepth( node );
  67. }
  68.  
  69. // Левый малый поворот.
  70. void CAVLTree::rotateLeft( CAVLNode*& node )
  71. {
  72.     CAVLNode* tmp = node->Right;
  73.     node->Right = tmp->Left;
  74.     tmp->Left = node;
  75.     node = tmp;
  76.     fixDepth( node->Left );
  77.     fixDepth( node );
  78. }
  79.  
  80. // Правый малый поворот.
  81. void CAVLTree::rotateRight( CAVLNode*& node )
  82. {
  83.     CAVLNode* tmp = node->Left;
  84.     node->Left = tmp->Right;
  85.     tmp->Right = node;
  86.     node = tmp;
  87.     fixDepth( node->Right );
  88.     fixDepth( node );
  89. }
  90.  
  91. // Обновление поля Depth в узле node.
  92. void CAVLTree::fixDepth( CAVLNode*& node )
  93. {
  94.     node->Depth = std::max( depth( node->Left ), depth( node->Right ) ) + 1;
  95. }
  96.  
  97. int main()
  98. {
  99.     return 0;
  100. }
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.

×