# BinarySearchTrees

Dec 2nd, 2021
883
0
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)
20.     else
21.       node->Right = new Node(key, node);
22.   } else {
23.     if (node->Left)
25.     else
26.       node->Left = new Node(key, node);
27.   }
28. }
29.
30. // insert <-> delete
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);
50.   // Удаление. Вариант 1. Фиктивный корень.
51.   Node* unreal_root = new Node(INT_MAX, nullptr);
52.   // Node* root = new Node(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);
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.
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.
106.   if (root == nullptr) {
107.     root = new Node(key, nullptr);
108.   } else {
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;
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;
201.   DFS(root, 0);
202.   return 0;
203. }