Advertisement
Ser1ousSAM

AVL-Tree

Nov 25th, 2022 (edited)
557
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using std::cout;
  5. using std::cin;
  6. using std::max;
  7.  
  8. template<typename T>
  9. class Node;
  10.  
  11. template<typename T>
  12. class AVL_Tree {
  13. public:
  14.     Node<T> *root = nullptr;
  15.     int treeSize;
  16.  
  17.     AVL_Tree();
  18.  
  19.     ~AVL_Tree() = default;
  20.  
  21.     void add(T x) {
  22.         root = add_p(root, x);
  23.         treeSize++;
  24.     }
  25.  
  26.     void remove(T x) {
  27.         root = remove_p(root, x);
  28.         treeSize--;
  29.     }
  30.  
  31.     bool find(T x) {
  32.         Node<T>* temp = find_p(root, x);
  33.         if (temp != nullptr){
  34.             if (temp->val_p == x)
  35.                 return true;
  36.         }
  37.         return false;
  38.     }
  39.  
  40.     void clear(){
  41.         clear_p(root);
  42.         treeSize = 0;
  43.     }
  44.  
  45.     void prefix(){
  46.         prefix_p(root);
  47.         cout << '\n';
  48.     }
  49.  
  50.     void infix(){
  51.         infix_p(root);
  52.         cout << '\n';
  53.     }
  54.  
  55.     void postfix(){
  56.         postfix_p(root);
  57.         cout << '\n';
  58.     }
  59.  
  60. private:
  61.     int height(Node<T> *);
  62.  
  63.     Node<T> *p_rightRotation(Node<T> *);
  64.  
  65.     Node<T> *_leftRotation(Node<T> *);
  66.  
  67.     Node<T> *add_p(Node<T> *, T);
  68.  
  69.     Node<T> *remove_p(Node<T> *, T);
  70.  
  71.     void clear_p(Node<T>*&);
  72.  
  73.     Node<T> *find_p(Node<T> *, T);
  74.  
  75.     void prefix_p(Node<T>*);
  76.  
  77.     void infix_p(Node<T>*);
  78.  
  79.     void postfix_p(Node<T>*);
  80. };
  81.  
  82. template<typename T>
  83. class Node {
  84.     T val_p;
  85.     Node *left_p;
  86.     Node *right_p;
  87.     int height_p;
  88.  
  89.     explicit Node(T _val = T()) : val_p(_val), left_p(nullptr), right_p(nullptr), height_p(1) {};
  90.  
  91.     friend class AVL_Tree<T>;
  92. };
  93.  
  94. template<typename T>
  95. AVL_Tree<T>::AVL_Tree() {
  96.     root = new Node<T>();
  97.     treeSize = 0;
  98. }
  99.  
  100. template<typename T>
  101. int AVL_Tree<T>::height(Node<T> *vertex) {
  102.     if (vertex == nullptr) return 0;
  103.     return vertex->height_p;
  104. }
  105.  
  106. template<typename T>
  107. Node<T> *AVL_Tree<T>::p_rightRotation(Node<T> *vertex) {
  108.     Node<T> *newVertex = vertex->left_p;
  109.     vertex->left_p = newVertex->right_p;
  110.     newVertex->right_p = vertex;
  111.     vertex->height_p = 1 + max(height(vertex->left_p), height(vertex->right_p));
  112.     newVertex->height_p = 1 + max(height(newVertex->left_p), height(newVertex->right_p));
  113.     return newVertex;
  114. }
  115.  
  116. template<typename T>
  117. Node<T> *AVL_Tree<T>::_leftRotation(Node<T> *vertex) {
  118.     Node<T> *newVertex = vertex->right_p;
  119.     vertex->right_p = newVertex->left_p;
  120.     newVertex->left_p = vertex;
  121.     vertex->height_p = 1 + max(height(vertex->left_p), height(vertex->right_p));
  122.     newVertex->height_p = 1 + max(height(newVertex->left_p), height(newVertex->right_p));
  123.     return newVertex;
  124. }
  125.  
  126. template<typename T>
  127. Node<T> *AVL_Tree<T>::add_p(Node<T> *vertex, T x) {
  128.     if (vertex == nullptr || root->val_p == 0) {
  129.         auto *temp = new Node<T>(x);
  130.         return temp;
  131.     }
  132.     if (x < vertex->val_p) vertex->left_p = add_p(vertex->left_p, x);
  133.     else if (x > vertex->val_p) vertex->right_p = add_p(vertex->right_p, x);
  134.     vertex->height_p = 1 + max(height(vertex->left_p), height(vertex->right_p));
  135.     int bal = height(vertex->left_p) - height(vertex->right_p);
  136.     if (bal > 1) {
  137.         if (x < vertex->left_p->val_p) {
  138.             return p_rightRotation(vertex);
  139.         } else {
  140.             vertex->left_p = _leftRotation(vertex->left_p);
  141.             return p_rightRotation(vertex);
  142.         }
  143.     } else if (bal < -1) {
  144.         if (x > vertex->right_p->val_p) {
  145.             return _leftRotation(vertex);
  146.         } else {
  147.             vertex->right_p = p_rightRotation(vertex->right_p);
  148.             return _leftRotation(vertex);
  149.         }
  150.     }
  151.     return vertex;
  152. }
  153.  
  154. template<typename T>
  155. Node<T> *AVL_Tree<T>::remove_p(Node<T> *vertex, T x) {
  156.     if (vertex == nullptr) return nullptr;
  157.     if (x < vertex->val_p) {
  158.         vertex->left_p = remove_p(vertex->left_p, x);
  159.     } else if (x > vertex->val_p) {
  160.         vertex->right_p = remove_p(vertex->right_p, x);
  161.     } else {
  162.         Node<T> *r = vertex->right_p;
  163.         if (vertex->right_p == nullptr) {
  164.             Node<T> *l = vertex->left_p;
  165.             delete (vertex);
  166.             vertex = l;
  167.         } else if (vertex->left_p == nullptr) {
  168.             delete (vertex);
  169.             vertex = r;
  170.         } else {
  171.             while (r->left_p != nullptr) r = r->left_p;
  172.             vertex->val_p = r->val_p;
  173.             vertex->right_p = remove_p(vertex->right_p, r->val_p);
  174.         }
  175.     }
  176.     if (vertex == nullptr) return vertex;
  177.     vertex->height_p = 1 + max(height(vertex->left_p), height(vertex->right_p));
  178.     int bal = height(vertex->left_p) - height(vertex->right_p);
  179.     if (bal > 1) {
  180.         if (height(vertex->left_p) >= height(vertex->right_p)) {
  181.             return p_rightRotation(vertex);
  182.         } else {
  183.             vertex->left_p = _leftRotation(vertex->left_p);
  184.             return p_rightRotation(vertex);
  185.         }
  186.     } else if (bal < -1) {
  187.         if (height(vertex->right_p) >= height(vertex->left_p)) {
  188.             return _leftRotation(vertex);
  189.         } else {
  190.             vertex->right_p = p_rightRotation(vertex->right_p);
  191.             return _leftRotation(vertex);
  192.         }
  193.     }
  194.     return vertex;
  195. }
  196.  
  197. template<typename T>
  198. Node<T> *AVL_Tree<T>::find_p(Node<T> *vertex, T x) {
  199.     if (vertex == nullptr) return nullptr;
  200.     T k = vertex->val_p;
  201.     if (k == x) return vertex;
  202.     if (k > x) return find_p(vertex->left_p, x);
  203.     if (k < x) return find_p(vertex->right_p, x);
  204.     return nullptr;
  205. }
  206.  
  207. template<typename T>
  208. void AVL_Tree<T>::clear_p(Node<T>*&vertex) {
  209.     if(vertex != nullptr) {
  210.         clear_p(vertex->left_p);
  211.         clear_p(vertex->right_p);
  212.         delete vertex;
  213.     }
  214.     vertex = nullptr;
  215. }
  216.  
  217. template<typename T>
  218. void AVL_Tree<T>::prefix_p(Node<T> * vertex) {
  219.     if (vertex == nullptr)
  220.         return;
  221.  
  222.     cout << vertex->val_p << " ";
  223.     prefix_p(vertex->left_p);
  224.     prefix_p(vertex->right_p);
  225. }
  226.  
  227. template<typename T>
  228. void AVL_Tree<T>::infix_p(Node<T> * vertex) {
  229.     if (vertex == nullptr)
  230.         return;
  231.  
  232.     infix_p(vertex->left_p);
  233.     cout << vertex->val_p << " ";
  234.     infix_p(vertex->right_p);
  235. }
  236.  
  237. template<typename T>
  238. void AVL_Tree<T>::postfix_p(Node<T> * vertex) {
  239.     if (vertex == nullptr)
  240.         return;
  241.  
  242.     postfix_p(vertex->left_p);
  243.     postfix_p(vertex->right_p);
  244.     cout << vertex->val_p << " ";
  245. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement