Advertisement
smatskevich

Seminar 11

Nov 28th, 2022
769
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.99 KB | None | 0 0
  1. #include <cassert>
  2. #include <iostream>
  3.  
  4. struct AVLNode {
  5.   int Key;
  6.   int Height = 1;  // Высота дерева. 1 для листа.
  7.   int Count = 1;  // Количество узлов в поддереве, включая сам узел.
  8.   AVLNode* Left = nullptr;
  9.   AVLNode* Right = nullptr;
  10.  
  11.   explicit AVLNode(int key) : Key(key) {}
  12.   ~AVLNode() { delete Left; delete Right; }
  13. };
  14.  
  15. int GetHeight(AVLNode* node) {
  16.   return node ? node->Height : 0;
  17. }
  18.  
  19. int GetCount(AVLNode* node) {
  20.   return node ? node->Count : 0;
  21. }
  22.  
  23. void UpdateHeight(AVLNode* node) {
  24.   assert(node);
  25.   node->Height = std::max(GetHeight(node->Left), GetHeight(node->Right)) + 1;
  26. }
  27.  
  28. void UpdateCount(AVLNode* node) {
  29.   assert(node);
  30.   node->Count = GetCount(node->Left) + GetCount(node->Right) + 1;
  31. }
  32.  
  33. int Balance(AVLNode* node) {
  34.   assert(node);
  35.   return GetHeight(node->Left) - GetHeight(node->Right);
  36. }
  37.  
  38. class AVLTree {
  39.  public:
  40.   ~AVLTree() { delete root; }
  41.   void Print() const { Print(root, 0); }
  42.   int Add(int key);
  43.   int Size() const { return GetCount(root); }
  44.   int KStat(int k) const {
  45.     assert(k >= 0 && k < GetCount(root));
  46.     return KStat(k, root);
  47.   }
  48.  
  49.  private:
  50.   AVLNode* root = nullptr;
  51.  
  52.   static int Add(int key, AVLNode*& node);
  53.   static void Print(AVLNode* node, int tabs);
  54.   static void RotateLeft(AVLNode*& node);
  55.   static void RotateRight(AVLNode*& node);
  56.   static void FixBalance(AVLNode*& node);
  57.   static int KStat(int k, AVLNode* node);
  58. };
  59.  
  60. int AVLTree::Add(int key) {
  61.   return Add(key, root);
  62. }
  63.  
  64. // Тут можно вернуть статистику добавленного элемента
  65. int AVLTree::Add(int key, AVLNode*& node) {
  66.   if (!node) {
  67.     node = new AVLNode(key);
  68.     return 0;
  69.   }
  70.   int stat = 0;
  71.   if (node->Key < key) {
  72.     stat = Add(key, node->Right) + GetCount(node->Left) + 1;
  73.   } else {
  74.     stat = Add(key, node->Left);
  75.   }
  76.   // Восстановим высоту и баланс.
  77.   UpdateHeight(node);
  78.   UpdateCount(node);
  79.   FixBalance(node);
  80.   return stat;
  81. }
  82.  
  83. void AVLTree::RotateLeft(AVLNode*& node) {
  84.   AVLNode* right = node->Right;
  85.   node->Right = right->Left;
  86.   right->Left = node;
  87.   node = right;
  88.  
  89.   UpdateHeight(node->Left);
  90.   UpdateCount(node->Left);
  91.   UpdateHeight(node);
  92.   UpdateCount(node);
  93. }
  94.  
  95. void AVLTree::RotateRight(AVLNode*& node) {
  96.   AVLNode* left = node->Left;
  97.   node->Left = left->Right;
  98.   left->Right = node;
  99.   node = left;
  100.  
  101.   UpdateHeight(node->Right);
  102.   UpdateCount(node->Right);
  103.   UpdateHeight(node);
  104.   UpdateCount(node);
  105. }
  106.  
  107. void AVLTree::FixBalance(AVLNode*& node) {
  108.   int balance = Balance(node);
  109.   if (balance == -2) {
  110.     if (Balance(node->Right) == 1) {
  111.       RotateRight(node->Right);
  112.     }
  113.     RotateLeft(node);
  114.   } else if (balance == 2) {
  115.     if (Balance(node->Left) == -1) {
  116.       RotateLeft(node->Left);
  117.     }
  118.     RotateRight(node);
  119.   }
  120. }
  121.  
  122. int AVLTree::KStat(int k, AVLNode* node) {
  123.   if (GetCount(node->Left) == k) {
  124.     return node->Key;
  125.   }
  126.   if (GetCount(node->Left) > k) {
  127.     return KStat(k, node->Left);
  128.   }
  129.   return KStat(k - GetCount(node->Left) - 1, node->Right);
  130. }
  131.  
  132. void AVLTree::Print(AVLNode* node, int tabs) {
  133.   if (node->Right) Print(node->Right, tabs + 1);
  134.   for (int i = 0; i < tabs; ++i) std::cout << "\t";
  135.   std::cout << node->Key << "(" << node->Count << ")" << std::endl;
  136.   if (node->Left) Print(node->Left, tabs + 1);
  137. }
  138.  
  139. // [.............3333333388888888................]
  140. //               u       r
  141.  
  142. int main1() {
  143.   AVLTree tree;
  144.   tree.Add(5);
  145.   tree.Add(6);
  146.   tree.Print();
  147.   std::cout << "===============\n";
  148.   tree.Add(8);
  149.   tree.Print();
  150.   std::cout << "===============\n";
  151.   tree.Add(9);
  152.   tree.Print();
  153.   std::cout << "===============\n";
  154.   tree.Add(14);
  155.   tree.Print();
  156.   std::cout << "===============\n";
  157.   tree.Add(7);
  158.   tree.Print();
  159.   std::cout << "===============\n";
  160.   std::cout << tree.KStat(0) << std::endl;
  161.   std::cout << tree.KStat(1) << std::endl;
  162.   std::cout << tree.KStat(2) << std::endl;
  163.   std::cout << tree.KStat(3) << std::endl;
  164.   std::cout << tree.KStat(4) << std::endl;
  165.   std::cout << tree.KStat(5) << std::endl;
  166.   return 0;
  167. }
  168.  
  169. struct Node {
  170.   int Data;
  171.   int Count = 1;  // Количество узлов в поддереве, включая сам узел.
  172.   Node* Left = nullptr;
  173.   Node* Right = nullptr;
  174.  
  175.   explicit Node(int data) : Data(data) {}
  176.   ~Node() { delete Left; delete Right; }
  177. };
  178.  
  179. int GetCount(Node* node) {
  180.   return node ? node->Count : 0;
  181. }
  182. class TreeByImplicitKey {
  183.  public:
  184.   ~TreeByImplicitKey() { delete root; }
  185.   void Print() const { Print(root, 0); }
  186.   // Добавить узел data в позицию pos.
  187.   void Add(int data, int pos) { Add(data, pos, root); }
  188.   int Size() const { return GetCount(root); }
  189.   int KStat(int k) const {
  190.     assert(k >= 0 && k < GetCount(root));
  191.     return KStat(k, root);
  192.   }
  193.  
  194.  private:
  195.   Node* root = nullptr;
  196.  
  197.   static void Add(int data, int pos, Node*& node);
  198.   static void Print(Node* node, int tabs);
  199.   static int KStat(int k, Node* node);
  200. };
  201.  
  202. void TreeByImplicitKey::Add(int data, int pos, Node*& node) {
  203.   if (!node) {
  204.     node = new Node(data);
  205.     return;
  206.   }
  207.   if (GetCount(node->Left) >= pos) {
  208.     Add(data, pos, node->Left);
  209.   } else {
  210.     Add(data, pos - GetCount(node->Left) - 1, node->Right);
  211.   }
  212. }
  213.  
  214. void TreeByImplicitKey::Print(Node* node, int tabs) {
  215.   if (node->Right) Print(node->Right, tabs + 1);
  216.   for (int i = 0; i < tabs; ++i) std::cout << "\t";
  217.   std::cout << node->Data << "(" << node->Count << ")" << std::endl;
  218.   if (node->Left) Print(node->Left, tabs + 1);
  219. }
  220.  
  221. int main() {
  222.   TreeByImplicitKey tree;
  223.   tree.Add(5, 0);
  224.   tree.Add(6, 1);
  225.   tree.Print();
  226.   std::cout << "===============\n";
  227.   tree.Add(8, 0);
  228.   tree.Print();
  229.   std::cout << "===============\n";
  230.   tree.Add(9, 2);
  231.   tree.Print();
  232.   std::cout << "===============\n";
  233.   tree.Add(14, 3);
  234.   tree.Print();
  235.   std::cout << "===============\n";
  236.   tree.Add(7, 1);
  237.   tree.Print();
  238.   std::cout << "===============\n";
  239.   return 0;
  240. }
  241.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement