smatskevich

AVLTreeDraft

Dec 9th, 2017
157
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.  
  5. // АВЛ-дерево с целочисленными ключами.
  6. class CAVLTree {
  7. public:
  8.     CAVLTree() : root( nullptr ) {}
  9.     bool Has( int key ) const;
  10.     void Add( int key );
  11.     void Remove( int key );
  12.  
  13. private:
  14.     // Узел дерева. Пока без Count.
  15.     struct CAVLTreeNode {
  16.         int Key;
  17.         int Height;
  18.         CAVLTreeNode* Left;
  19.         CAVLTreeNode* Right;
  20.         CAVLTreeNode( int key ) : Key( key ), Height( 1 ), Left( nullptr ), Right( nullptr ) {}
  21.     };
  22.  
  23.     CAVLTreeNode* root;
  24.  
  25.     static void add( CAVLTreeNode*& node, int key );
  26.     static void fixupBalance( CAVLTreeNode*& node );
  27.     static int height( const CAVLTreeNode* node ) { return node == nullptr ? 0 : node->Height; }
  28.     static int balance( const CAVLTreeNode* node );
  29.     static void fixHeight( CAVLTreeNode* node );
  30.     static int rotateLeft( CAVLTreeNode* node );
  31.     static int rotateRight( CAVLTreeNode* node );
  32. };
  33.  
  34. void CAVLTree::Add( int key )
  35. {
  36.     add( root, key );
  37. }
  38.  
  39. // Рекурсивное добавление узла в поддерево.
  40. // node передается по ссылке, чтобы обновить указатель в случае поворота или добавления нового узла.
  41. void CAVLTree::add( CAVLTreeNode*& node, int key )
  42. {
  43.     if( node == nullptr ) {
  44.         node = new CAVLTreeNode( key );
  45.         return;
  46.     }
  47.     // Рекурсивно добавляем узел.
  48.     if( node->Key < key ) {
  49.         add( node->Right, key );
  50.     } else {
  51.         add( node->Left, key );
  52.     }
  53.     // Восстановим баланс текущего узла.
  54.     fixupBalance( node );
  55. }
  56.  
  57. int CAVLTree::balance( const CAVLTreeNode* node )
  58. {
  59.     assert( node != nullptr );
  60.     return height( node->Left ) - height( node->Right );
  61. }
  62.  
  63. void CAVLTree::fixupBalance( CAVLTreeNode*& node )
  64. {
  65.     assert( node != nullptr );
  66.  
  67.     if( balance( node ) == 2 ) {
  68.         if( balance( node->Left ) == -1 ) {
  69.             rotateLeft( node->Left );
  70.         }
  71.         rotateRight( node );
  72.     } else if( height( node->Left ) - height( node->Right ) == -2 ) {
  73.         if( balance( node->Right ) == 1 ) {
  74.             rotateRight( node->Right );
  75.         }
  76.         rotateLeft( node );
  77.     } else {
  78.         fixHeight( node );
  79.     }
  80. }
  81.  
  82. void CAVLTree::fixHeight( CAVLTreeNode* node )
  83. {
  84.     node->Height = std::max( height( node->Left ), height( node->Right ) ) + 1;
  85. }
  86.  
  87. int main()
  88. {
  89.     CAVLTree tree;
  90.     return 0;
  91. }
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.

×