smatskevich

SplayTree

Apr 20th, 2018
189
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <assert.h>
  2. #include <iostream>
  3.  
  4. class CSplayTree {
  5. public:
  6.     ~CSplayTree();
  7.  
  8.     // Проверяет наличие ключа в дереве. Неконстантный, т.к. перебалансирует дерево в Splay.
  9.     bool Has( int key );
  10.     // Добавление ключа. Если ключ уже есть в дереве, возвращает false.
  11.     bool Add( int key );
  12.     // Удаление ключа. Если ключа нет, то возвращает false.
  13.     bool Remove( int key );
  14.  
  15. private:
  16.     struct CNode {
  17.         int Key = 0;
  18.         CNode* Left = nullptr;
  19.         CNode* Right = nullptr;
  20.         CNode* Parent = nullptr;
  21.         explicit CNode( int key ) : Key( key ) {}
  22.     };
  23.  
  24.     CNode* root = nullptr;
  25.  
  26.     CNode* find( int key );
  27.     void splay( CNode* x );
  28.     void deleteTree( CNode* node );
  29.  
  30.     // Проверка, что x слева от parent.
  31.     static bool isLeft( const CNode* parent, const CNode* x ) { return parent->Left == x; }
  32.     static void zig( CNode* x );
  33.     static void zigZig( CNode* x );
  34.     static void zigZag( CNode* x );
  35.     static void rotateLeft( CNode* x );
  36.     static void rotateRight( CNode* x );
  37. };
  38.  
  39. CSplayTree::~CSplayTree()
  40. {
  41.     deleteTree( root );
  42. }
  43.  
  44. void CSplayTree::deleteTree( CNode* node )
  45. {
  46.     if( node != nullptr ) {
  47.         deleteTree( node->Left );
  48.         deleteTree( node->Right );
  49.         delete node;
  50.     }
  51. }
  52.  
  53. bool CSplayTree::Has( int key )
  54. {
  55.     if( root == nullptr ) {
  56.         return false;
  57.     }
  58.     CNode* node = find( key );
  59.     splay( node );
  60.     return node->Key == key;
  61. }
  62.  
  63. bool CSplayTree::Add( int key )
  64. {
  65.     if( root == nullptr ) {
  66.         root = new CNode( key );
  67.         return true;
  68.     }
  69.     CNode* node = find( key );
  70.     if( node->Key == key ) {
  71.         return false;
  72.     }
  73.     // Смотрим, где разместить новый узел.
  74.     CNode*& newNodePlace = node->Key < key ? node->Right : node->Left;
  75.     assert( newNodePlace == nullptr );
  76.     newNodePlace = new CNode( key );
  77.     newNodePlace->Parent = node;
  78.  
  79.     splay( newNodePlace );
  80.  
  81.     return true;
  82. }
  83.  
  84. bool CSplayTree::Remove( int )
  85. {
  86.     // place your code here...
  87.     return false;
  88. }
  89.  
  90. // Ищем узел, содержащий ключ key.
  91. // Если такого нет, то узел, под который этот ключ можно было бы вставить.
  92. CSplayTree::CNode* CSplayTree::find( int key )
  93. {
  94.     assert( root != nullptr );
  95.     CNode* node = root;
  96.     while( true ) {
  97.         if( node->Key == key ) {
  98.             return node;
  99.         } else if( node->Key < key ) {
  100.             if( node->Right == nullptr ) {
  101.                 return node;
  102.             }
  103.             node = node->Right;
  104.         } else {
  105.             if( node->Left == nullptr ) {
  106.                 return node;
  107.             }
  108.             node = node->Left;
  109.         }
  110.     }
  111. }
  112.  
  113. void CSplayTree::splay( CNode* x )
  114. {
  115.     while( x->Parent != nullptr ) {
  116.         if( x->Parent->Parent == nullptr ) {
  117.             zig( x );
  118.         } else if( isLeft( x->Parent, x ) == isLeft( x->Parent->Parent, x->Parent ) ) {
  119.             zigZig( x );
  120.         } else {
  121.             zigZag( x );
  122.         }
  123.     }
  124.     root = x;
  125. }
  126.  
  127. void CSplayTree::zig( CNode* x )
  128. {
  129.     if( isLeft( x->Parent, x ) ) {
  130.         rotateRight( x->Parent );
  131.     } else {
  132.         rotateLeft( x->Parent );
  133.     }
  134. }
  135.  
  136. void CSplayTree::zigZig( CNode* x )
  137. {
  138.     if( isLeft( x->Parent, x ) ) {
  139.         rotateRight( x->Parent->Parent );
  140.         rotateRight( x->Parent );
  141.     } else {
  142.         rotateLeft( x->Parent->Parent );
  143.         rotateLeft( x->Parent );
  144.     }
  145. }
  146.  
  147. void CSplayTree::zigZag( CNode* x )
  148. {
  149.     if( isLeft( x->Parent, x ) ) {
  150.         rotateRight( x->Parent );
  151.         rotateLeft( x->Parent );
  152.     } else {
  153.         rotateLeft( x->Parent );
  154.         rotateRight( x->Parent );
  155.     }
  156. }
  157.  
  158. void CSplayTree::rotateLeft( CNode* x )
  159. {
  160.     assert( x != nullptr );
  161.     CNode* parent = x->Parent;
  162.     CNode* right = x->Right;
  163.     x->Right = right->Left;
  164.     if( right->Left != nullptr ) {
  165.         right->Left->Parent = x;
  166.     }
  167.     right->Left = x;
  168.     x->Parent = right;
  169.     right->Parent = parent;
  170.     if( parent != nullptr ) {
  171.         if( isLeft( parent, x ) ) {
  172.             parent->Left = right;
  173.         } else {
  174.             parent->Right = right;
  175.         }
  176.     }
  177. }
  178.  
  179. void CSplayTree::rotateRight( CNode* x )
  180. {
  181.     assert( x != nullptr );
  182.     CNode* parent = x->Parent;
  183.     CNode* left = x->Left;
  184.     x->Left = left->Right;
  185.     if( left->Right != nullptr ) {
  186.         left->Right->Parent = x;
  187.     }
  188.     left->Right = x;
  189.     x->Parent = left;
  190.     left->Parent = parent;
  191.     if( parent != nullptr ) {
  192.         if( isLeft( parent, x ) ) {
  193.             parent->Left = left;
  194.         } else {
  195.             parent->Right = left;
  196.         }
  197.     }
  198. }
  199.  
  200. int main()
  201. {
  202.     CSplayTree splayTree;
  203.     std::cout << ( !splayTree.Has( 5 ) ? "Ok" : "Fail" ) << std::endl;
  204.     std::cout << ( splayTree.Add( 6 ) ? "Ok" : "Fail" ) << std::endl;
  205.     std::cout << ( splayTree.Has( 6 ) ? "Ok" : "Fail" ) << std::endl;
  206.     std::cout << ( !splayTree.Add( 6 ) ? "Ok" : "Fail" ) << std::endl;
  207.  
  208.     std::cout << ( splayTree.Add( 4 ) ? "Ok" : "Fail" ) << std::endl;
  209.     std::cout << ( splayTree.Add( 5 ) ? "Ok" : "Fail" ) << std::endl;
  210.     std::cout << ( !splayTree.Has( 7 ) ? "Ok" : "Fail" ) << std::endl;
  211.     std::cout << ( splayTree.Has( 5 ) ? "Ok" : "Fail" ) << std::endl;
  212.     std::cout << ( splayTree.Has( 4 ) ? "Ok" : "Fail" ) << std::endl;
  213.     std::cout << ( splayTree.Has( 6 ) ? "Ok" : "Fail" ) << std::endl;
  214.  
  215.     std::cout << ( splayTree.Add( 8 ) ? "Ok" : "Fail" ) << std::endl;
  216.     std::cout << ( splayTree.Add( 3 ) ? "Ok" : "Fail" ) << std::endl;
  217.     std::cout << ( splayTree.Has( 8 ) ? "Ok" : "Fail" ) << std::endl;
  218.     std::cout << ( splayTree.Has( 3 ) ? "Ok" : "Fail" ) << std::endl;
  219.     std::cout << ( !splayTree.Has( 7 ) ? "Ok" : "Fail" ) << std::endl;
  220.     std::cout << ( splayTree.Has( 5 ) ? "Ok" : "Fail" ) << std::endl;
  221.     std::cout << ( splayTree.Has( 4 ) ? "Ok" : "Fail" ) << std::endl;
  222.     std::cout << ( splayTree.Has( 6 ) ? "Ok" : "Fail" ) << std::endl;
  223.     return 0;
  224. }
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.

×