smatskevich

BinarySearchTrees

Dec 2nd, 2021
760
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cassert>
  2. #include <iostream>
  3. #include <limits.h>
  4. #include <queue>
  5.  
  6. struct Node {
  7.   int Key;
  8.   Node* Left;
  9.   Node* Right;
  10.   Node* Parent;
  11.  
  12.   Node(int key, Node* parent) : Key(key), Left(nullptr), Right(nullptr), Parent(parent) {}
  13. };
  14.  
  15. void Add(int key, Node* node) {
  16.   assert(node);
  17.   if (node->Key < key) {
  18.     if (node->Right)
  19.       Add(key, node->Right);
  20.     else
  21.       node->Right = new Node(key, node);
  22.   } else {
  23.     if (node->Left)
  24.       Add(key, node->Left);
  25.     else
  26.       node->Left = new Node(key, node);
  27.   }
  28. }
  29.  
  30. // insert <-> delete
  31. // add <-> remove
  32.  
  33. Node* Remove(int key, Node*& root) {
  34.  
  35.   delete root;
  36.   return nullptr;
  37. }
  38.  
  39. void DeleteTree(Node* root) {
  40.   if (root != nullptr) {
  41.     DeleteTree(root->Left);
  42.     DeleteTree(root->Right);
  43.     delete root;
  44.   }
  45. }
  46.  
  47. int main1() {
  48. //  Node* root = new Node(5, nullptr);
  49. //  Add(7, root);
  50.   // Удаление. Вариант 1. Фиктивный корень.
  51.   Node* unreal_root = new Node(INT_MAX, nullptr);
  52.   // Node* root = new Node(5, unreal_root);
  53.   Add(5, unreal_root);
  54.   Remove(7, unreal_root);
  55.   // Удаление. Вариант 2. Возвращать из Remove новый корень.
  56.  
  57.   std::cout << unreal_root->Key << " " << unreal_root->Right->Key << std::endl;
  58.   DeleteTree(unreal_root);
  59.   return 0;
  60. }
  61.  
  62. int height(Node* root) {
  63.   if (root == nullptr) return 0;
  64.   int l = height(root->Left);
  65.   int r = height(root->Right);
  66.   return std::max(l, r) + 1;
  67. }
  68.  
  69. int main2() {
  70.   Node* fake_root = new Node(INT_MAX, nullptr);
  71.   Add(5, fake_root);
  72.   Add(7, fake_root);
  73.   std::cout << height(fake_root->Left) << std::endl;
  74.   return 0;
  75. }
  76.  
  77. class Tree {
  78.  public:
  79.   Tree() : root(nullptr) { std::cout << "Constructor called" << std::endl; }
  80.   ~Tree() { Destruct(root); std::cout << "Destructor called" << std::endl; }
  81.  
  82.   void Add(int key);
  83.   void BFS();
  84.   void Print() { if(root) DFS(root, 0); }
  85.  
  86.  private:
  87.   Node* root;  // = nullptr, если дерево пустое
  88.  
  89.   void Destruct(Node* node) {
  90.     if (node != nullptr) {
  91.       Destruct(node->Left);
  92.       Destruct(node->Right);
  93.       delete node;
  94.     }
  95.   }
  96.   void DFS(Node* node, int margin) {
  97.     if (node->Right) DFS(node->Right, margin + 4);
  98.     for (int i = 0; i < margin - 4; ++i) std::cout << " ";
  99.     if (margin > 3) for (int i = 0; i < 4; ++i) std::cout << "-";
  100.     std::cout << "(" << node->Key << ")" << std::endl;
  101.     if (node->Left) DFS(node->Left, margin + 4);
  102.   }
  103. };
  104.  
  105. void Tree::Add(int key) {
  106.   if (root == nullptr) {
  107.     root = new Node(key, nullptr);
  108.   } else {
  109.     ::Add(key, root);
  110.   }
  111. }
  112.  
  113. void Tree::BFS() {
  114.   std::queue<Node*> q;
  115.   if (root) q.push(root);
  116.   while (!q.empty()) {
  117.     Node* current = q.front(); q.pop();
  118.     std::cout << current->Key << " ";
  119.     if (current->Left) q.push(current->Left);
  120.     if (current->Right) q.push(current->Right);
  121.   }
  122.   std::cout << std::endl;
  123. }
  124.  
  125. int main3() {
  126.   {
  127.     Tree tree;
  128.     tree.Add(5);
  129.     tree.Add(9);
  130.     tree.Add(3);
  131.     tree.Add(1);
  132.     tree.Add(2);
  133.     tree.Add(7);
  134.     tree.Add(6);
  135.     tree.Add(8);
  136.     tree.Add(10);
  137.     tree.BFS();
  138.     tree.Print();
  139.   }
  140.   std::cout << "Before return" << std::endl;
  141.   return 0;
  142. }
  143.  
  144. struct TreapNode {
  145.   int Key;
  146.   int Priority;
  147.   TreapNode* Left;
  148.   TreapNode* Right;
  149.  
  150.   TreapNode(int key, int priority) : Key(key), Priority(priority), Left(nullptr), Right(nullptr) {}
  151. };
  152.  
  153. std::pair<TreapNode*, TreapNode*> Split(TreapNode* node, int key) {
  154.   if (node == nullptr) return {nullptr, nullptr};
  155.   if (key < node->Key) {
  156.     std::pair<TreapNode*, TreapNode*> p = Split(node->Left, key);
  157.     node->Left = p.second;
  158.     return {p.first, node};
  159.   } else {
  160.     auto [first, second] = Split(node->Right, key);
  161.     node->Right = first;
  162.     return {node, second};
  163.   }
  164. }
  165.  
  166. TreapNode* Merge(TreapNode* left, TreapNode* right) {
  167.   if (left == nullptr || right == nullptr) {
  168.     return left == nullptr ? right : left;
  169.   }
  170.   if (left->Priority > right->Priority) {
  171.     left->Right = Merge(left->Right, right);
  172.     return left;
  173.   } else {
  174.     right->Left = Merge(left, right->Left);
  175.     return right;
  176.   }
  177. }
  178.  
  179. TreapNode* Add(TreapNode* root, int key) {
  180.   TreapNode* new_node = new TreapNode(key, rand());
  181.   auto [first, second] = Split(root, key);
  182.   return Merge(Merge(first, new_node), second);
  183. }
  184.  
  185. void DFS(TreapNode* node, int margin) {
  186.   if (node->Right) DFS(node->Right, margin + 4);
  187.   for (int i = 0; i < margin - 4; ++i) std::cout << " ";
  188.   if (margin > 3) for (int i = 0; i < 4; ++i) std::cout << "-";
  189.   std::cout << "(" << node->Key << ")" << std::endl;
  190.   if (node->Left) DFS(node->Left, margin + 4);
  191. }
  192.  
  193. int main() {
  194.   srand(2021);
  195.  
  196.   TreapNode* root = nullptr;
  197.   root = Add(root, 5);
  198.   root = Add(root, 7);
  199.   root = Add(root, 92);
  200.   root = Add(root, 198);
  201.   DFS(root, 0);
  202.   return 0;
  203. }
RAW Paste Data