Advertisement
OIQ

Untitled

OIQ
Nov 8th, 2021
731
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.36 KB | None
  1. #include <iostream>
  2.  
  3. template <class ValueType>
  4. class RBTree {
  5. public:
  6.     RBTree() {
  7.         nil_ = new RBNode{ValueType(), true, nullptr, nullptr, nullptr};
  8.         root_ = nil_;
  9.         size_ = 0;
  10.     }
  11.  
  12.     RBTree(const RBTree& other) {
  13.         nil_ = new RBNode{ValueType(), true, nullptr, nullptr, nullptr};
  14.         root_ = nil_;
  15.         size_ = other.size_;
  16.         if (other.root_ == other.nil_) {
  17.             return;
  18.         }
  19.         root_ = new RBNode{other.root_->value, other.root_->isBlack, nil_, nil_, nullptr};
  20.         deepCopy(other.root_, root_, other.nil_);
  21.     }
  22.  
  23.     RBTree& operator=(const RBTree& other) {
  24.         if (this == &other) {
  25.             return *this;
  26.         }
  27.         if (root_ != nil_) {
  28.             clear(root_);
  29.         }
  30.  
  31.         if (root_ != nil_) {
  32.             delete root_;
  33.         }
  34.         delete nil_;
  35.  
  36.         nil_ = new RBNode{ValueType(), true, nullptr, nullptr, nullptr};
  37.         size_ = other.size_;
  38.  
  39.         if (other.root_ != other.nil_) {
  40.             root_ = new RBNode{other.root_->value, other.root_->isBlack, nil_, nil_, nullptr};
  41.             deepCopy(other.root_, root_, other.nil_);
  42.         } else {
  43.             root_ = nil_;
  44.         }
  45.         return *this;
  46.     }
  47.  
  48.     ~RBTree() {
  49.         clear(root_);
  50.         if (root_ != nil_) {
  51.             delete root_;
  52.         }
  53.         delete nil_;
  54.     }
  55.  
  56.     size_t size() const {
  57.         return size_;
  58.     }
  59.  
  60.     bool empty() const {
  61.         return root_ == nil_;
  62.     }
  63.  
  64.     void insert(const ValueType& value) {
  65.         RBNode* node = new RBNode{value, false, nil_, nil_, nullptr};
  66.         if (root_ == nil_) {
  67.             root_ = node;
  68.             shuffleInsert(root_);
  69.             size_++;
  70.             return;
  71.         }
  72.  
  73.         RBNode* current = root_;
  74.         RBNode* tmp = nullptr;
  75.  
  76.         while (current != nil_) {
  77.             tmp = current;
  78.             if (current->value < node->value) {
  79.                 current = current->right;
  80.             } else if (node->value < current->value) {
  81.                 current = current->left;
  82.             } else {
  83.                 delete node;
  84.                 return;
  85.             }
  86.         }
  87.  
  88.         node->parent = tmp;
  89.         if (tmp->value < node->value) {
  90.             tmp->right = node;
  91.         } else {
  92.             tmp->left = node;
  93.         }
  94.         size_++;
  95.         shuffleInsert(node);
  96.     }
  97.  
  98.     void erase(const ValueType& value) {
  99.         RBNode* node = root_;
  100.         RBNode* current = nil_;
  101.         RBNode* tmp_x;
  102.         RBNode* tmp_y;
  103.         while (node != nil_) {
  104.             if (!(node->value < value || value < node->value)) {
  105.                 current = node;
  106.             }
  107.  
  108.             if (node->value < value) {
  109.                 node = node->right;
  110.             } else {
  111.                 node = node->left;
  112.             }
  113.         }
  114.  
  115.         if (current == nil_) {
  116.             return;
  117.         }
  118.  
  119.         tmp_y = current;
  120.         bool y_original_color = tmp_y->isBlack;
  121.         if (current->left == nil_) {
  122.             tmp_x = current->right;
  123.             rbTransplant(current, current->right);
  124.         } else if (current->right == nil_) {
  125.             tmp_x = current->left;
  126.             rbTransplant(current, current->left);
  127.         } else {
  128.             tmp_y = minimum(current->right);
  129.             y_original_color = tmp_y->isBlack;
  130.             tmp_x = tmp_y->right;
  131.             if (tmp_y->parent == current) {
  132.                 tmp_x->parent = tmp_y;
  133.             } else {
  134.                 rbTransplant(tmp_y, tmp_y->right);
  135.                 tmp_y->right = current->right;
  136.                 tmp_y->right->parent = tmp_y;
  137.             }
  138.  
  139.             rbTransplant(current, tmp_y);
  140.             tmp_y->left = current->left;
  141.             tmp_y->left->parent = tmp_y;
  142.             tmp_y->isBlack = current->isBlack;
  143.         }
  144.         delete current;
  145.         size_--;
  146.         if (y_original_color) {
  147.             shuffleDelete(tmp_x);
  148.         }
  149.     }
  150.  
  151.     ValueType* lower_bound(const ValueType& value) const {  // NOLINT
  152.         RBNode* current = root_;
  153.         ValueType* result = nullptr;
  154.  
  155.         while (current != nil_) {
  156.             if (value < current->value) {
  157.                 result = &current->value;
  158.                 current = current->left;
  159.             } else if (current->value < value) {
  160.                 current = current->right;
  161.             } else {
  162.                 return &current->value;
  163.             }
  164.         }
  165.  
  166.         return result;
  167.     }
  168.  
  169.     ValueType* find(const ValueType& value) const {
  170.         RBNode* current = root_;
  171.         // ValueType* result = nullptr;
  172.         while (current != nil_) {
  173.             if (current->value < value) {
  174.                 current = current->right;
  175.             } else if (value < current->value) {
  176.                 current = current->left;
  177.             } else {
  178.                 return &current->value;
  179.             }
  180.         }
  181.  
  182.         return nullptr;
  183.     }
  184.  
  185.     ValueType* traversal() const {
  186.         ValueType* nodes = new ValueType[size_];
  187.         int index = 0;
  188.         fill(nodes, root_, &index);
  189.  
  190.         return nodes;
  191.     }
  192.  
  193. private:
  194.     struct RBNode {
  195.         ValueType value;
  196.         bool isBlack;
  197.         RBNode* left;
  198.         RBNode* right;
  199.         RBNode* parent;
  200.     };
  201.  
  202.     RBNode* root_;
  203.     RBNode* nil_;
  204.     size_t size_;
  205.  
  206.     void shuffleInsert(RBNode* node) {
  207.         if (node == root_) {
  208.             root_->isBlack = true;
  209.             return;
  210.         }
  211.  
  212.         while (!node->parent->isBlack) {
  213.             if (node->parent == node->parent->parent->left) {
  214.                 if (node->parent->parent->right && !node->parent->parent->right->isBlack) {
  215.                     node->parent->isBlack = true;
  216.                     node->parent->parent->right->isBlack = true;
  217.                     node->parent->parent->isBlack = false;
  218.                     node = node->parent->parent;
  219.                 } else {
  220.                     if (node->parent->value < node->value) {
  221.                         node = node->parent;
  222.                         leftRotate(node);
  223.                     }
  224.                     node->parent->isBlack = true;
  225.                     node->parent->parent->isBlack = false;
  226.                     rightRotate(node->parent->parent);
  227.                 }
  228.             } else {
  229.                 if (node->parent->parent->left && !node->parent->parent->left->isBlack) {
  230.                     node->parent->isBlack = true;
  231.                     node->parent->parent->left->isBlack = true;
  232.                     node->parent->parent->isBlack = false;
  233.                     node = node->parent->parent;
  234.                 } else {
  235.                     if (node->value < node->parent->value) {
  236.                         node = node->parent;
  237.                         rightRotate(node);
  238.                     }
  239.                     node->parent->isBlack = true;
  240.                     node->parent->parent->isBlack = false;
  241.                     leftRotate(node->parent->parent);
  242.                 }
  243.             }
  244.  
  245.             if (node == root_) {
  246.                 break;
  247.             }
  248.         }
  249.  
  250.         root_->isBlack = true;
  251.     }
  252.  
  253.     void shuffleDelete(RBNode* node) {
  254.         RBNode* uncle;
  255.         while (node != root_ && node->isBlack) {
  256.             if (node == node->parent->left) {
  257.                 uncle = node->parent->right;
  258.                 if (!uncle->isBlack) {
  259.                     uncle->isBlack = true;
  260.                     node->parent->isBlack = false;
  261.                     leftRotate(node->parent);
  262.                     uncle = node->parent->right;
  263.                 }
  264.  
  265.                 if (uncle->left->isBlack && uncle->right->isBlack) {
  266.                     uncle->isBlack = false;
  267.                     node = node->parent;
  268.                 } else {
  269.                     if (uncle->right->isBlack) {
  270.                         uncle->left->isBlack = true;
  271.                         uncle->isBlack = false;
  272.                         rightRotate(uncle);
  273.                         uncle = node->parent->right;
  274.                     }
  275.  
  276.                     uncle->isBlack = node->parent->isBlack;
  277.                     node->parent->isBlack = true;
  278.                     uncle->right->isBlack = true;
  279.                     leftRotate(node->parent);
  280.                     node = root_;
  281.                 }
  282.             } else {
  283.                 uncle = node->parent->left;
  284.                 if (!uncle->isBlack) {
  285.                     uncle->isBlack = true;
  286.                     node->parent->isBlack = false;
  287.                     rightRotate(node->parent);
  288.                     uncle = node->parent->left;
  289.                 }
  290.  
  291.                 if (uncle->right->isBlack && uncle->left->isBlack) {
  292.                     uncle->isBlack = false;
  293.                     node = node->parent;
  294.                 } else {
  295.                     if (uncle->left->isBlack) {
  296.                         uncle->right->isBlack = true;
  297.                         uncle->isBlack = false;
  298.                         leftRotate(uncle);
  299.                         uncle = node->parent->left;
  300.                     }
  301.  
  302.                     uncle->isBlack = node->parent->isBlack;
  303.                     node->parent->isBlack = true;
  304.                     uncle->left->isBlack = true;
  305.                     rightRotate(node->parent);
  306.                     node = root_;
  307.                 }
  308.             }
  309.         }
  310.         node->isBlack = true;
  311.     }
  312.  
  313.     void leftRotate(RBNode* node) {
  314.         RBNode* node_right = node->right;
  315.         node->right = node_right->left;
  316.  
  317.         if (node->right != nil_) {
  318.             node->right->parent = node;
  319.         }
  320.  
  321.         node_right->parent = node->parent;
  322.         if (!node->parent) {
  323.             root_ = node_right;
  324.         } else if (node == node->parent->left) {
  325.             node->parent->left = node_right;
  326.         } else {
  327.             node->parent->right = node_right;
  328.         }
  329.  
  330.         node_right->left = node;
  331.         node->parent = node_right;
  332.     }
  333.  
  334.     void rightRotate(RBNode* node) {
  335.         RBNode* node_left = node->left;
  336.         node->left = node_left->right;
  337.  
  338.         if (node->left != nil_) {
  339.             node->left->parent = node;
  340.         }
  341.  
  342.         node_left->parent = node->parent;
  343.         if (!node->parent) {
  344.             root_ = node_left;
  345.         } else if (node == node->parent->left) {
  346.             node->parent->left = node_left;
  347.         } else {
  348.             node->parent->right = node_left;
  349.         }
  350.  
  351.         node_left->right = node;
  352.         node->parent = node_left;
  353.     }
  354.  
  355.     void clear(RBNode* node) {
  356.         if (node == nil_) {
  357.             return;
  358.         }
  359.  
  360.         clear(node->left);
  361.         clear(node->right);
  362.  
  363.         if (node->left != nil_) {
  364.             delete node->left;
  365.         }
  366.         if (node->right != nil_) {
  367.             delete node->right;
  368.         }
  369.     }
  370.  
  371.     void dfs(RBNode* node) {
  372.         if (node == nil_) {
  373.             return;
  374.         }
  375.         dfs(node->left);
  376.         std::cout << node->value << std::endl;
  377.         dfs(node->right);
  378.     }
  379.  
  380.     RBNode* minimum(RBNode* node) {
  381.         while (node->left != nil_) {
  382.             node = node->left;
  383.         }
  384.         return node;
  385.     }
  386.  
  387.     void rbTransplant(RBNode* node_u, RBNode* node_v) {
  388.         if (node_u->parent == nullptr) {
  389.             root_ = node_v;
  390.         } else if (node_u == node_u->parent->left) {
  391.             node_u->parent->left = node_v;
  392.         } else {
  393.             node_u->parent->right = node_v;
  394.         }
  395.         node_v->parent = node_u->parent;
  396.     }
  397.  
  398.     void deepCopy(const RBNode* other, RBNode* node, const RBNode* nil) {
  399.         if (other == nil) {
  400.             return;
  401.         }
  402.         if (other->left != nil) {
  403.             node->left = new RBNode{other->left->value, other->left->isBlack, nil_, nil_, nullptr};
  404.             node->left->parent = node;
  405.         }
  406.         deepCopy(other->left, node->left, nil);
  407.  
  408.         if (other->right != nil) {
  409.             ValueType number = other->right->value;
  410.             node->right = new RBNode{number, other->right->isBlack, nil_, nil_, nullptr};
  411.             node->right->parent = node;
  412.         }
  413.         deepCopy(other->right, node->right, nil);
  414.     }
  415.  
  416.     void fill(ValueType* nodes, RBNode* node, int* index) const {
  417.         if (node == nil_) {
  418.             return;
  419.         }
  420.  
  421.         fill(nodes, node->left, index);
  422.         nodes[*index] = node->value;
  423.         (*index)++;
  424.         fill(nodes, node->right, index);
  425.     }
  426. };
  427.  
Advertisement
RAW Paste Data Copied
Advertisement