south/school - Change 4MYKIMUNWPTZBZB4YLGVGWJW6WVSWGU7B3AI2BGGD3MQ6MIJRN4QC

second attempt at pushing rbt changes

Created by South on April 14, 2021

4MYKIMUNWPTZBZB4YLGVGWJW6WVSWGU7B3AI2BGGD3MQ6MIJRN4QC

Dependencies

In channels

main

Change contents

Replacement in red-black/red_black_tree_tests.cpp at line 3 [4.40]

B:BD[4.72] → [4.72:145]

int main() {  
    // TODO(student): write at least 1000 lines of test

[4.72]

[4.145]

int main() {
    // red = 0, black = 1
    RedBlackTree<int> tree;
    tree.insert(2);
    tree.insert(1);
    tree.insert(3);
    tree.insert(4);
    tree.insert(5);
    std::cout << tree.contains(4) << "\n";
    std::cout << tree.find_min() << "\n";
    std::cout << tree.find_max() << "\n";
    tree.print_tree();
    auto root = tree.get_root();
    std::cout << tree.color(root) << "\n";

Insertion in red-black/red_black_tree_tests.cpp at line 18 [4.40]
[4.151]
[4.151]
Insertion in red-black/red_black_tree.h at line 2 [4.187]
[3.26]
[4.240]
```
#include <iostream>
#include <stdexcept>
```
Replacement in red-black/red_black_tree.h at line 13 [4.187]
B:BD[3.145] → [3.145:172]
```
            Color colour;
```
[3.145]
[3.172]
```
            Color color;
```
Insertion in red-black/red_black_tree.h at line 16 [4.187]
[3.223]
[3.223]
```
            Node* parent;
```
Replacement in red-black/red_black_tree.h at line 20 [4.187]
B:BD[3.284] → [3.284:313]
```
            , colour(BLACK)
```
[3.284]
[3.313]
```
            , color(BLACK)
```

Replacement in red-black/red_black_tree.h at line 22 [4.187]

B:BD[3.342] → [3.342:375]

            , right(nullptr) {}

[3.342]

[3.375]

            , right(nullptr)
            , parent(nullptr) {}

Replacement in red-black/red_black_tree.h at line 25 [4.187]

B:BD[3.377] → [3.377:460]

            Node(const T& item, Color color, Node* left_child, Node* right_child)

[3.377]

[3.460]

            Node(const T& item, Color colour, Node* left_child, Node* right_child, Node* node_parent)

Replacement in red-black/red_black_tree.h at line 27 [4.187]
B:BD[3.486] → [3.486:515]
```
            , colour(color)
```
[3.486]
[3.515]
```
            , color(colour)
```

Replacement in red-black/red_black_tree.h at line 29 [4.187]

B:BD[3.547] → [3.547:584]

            , right(right_child) {}

[3.547]

[3.584]

            , right(right_child)
            , parent(node_parent) {}

Insertion in red-black/red_black_tree.h at line 34 [4.187]

[3.621]


        Node* copy(Node* node) const {
            if (node == nullptr)
                return nullptr;
            else
                return new Node(node->data, node->color, copy(node->left), copy(node->right), node->parent);
        }
        void display(Node* root, std::ostream& out, unsigned int counter = 0) const {
            if (m_root == nullptr) {
                out << "<empty>\n";
            } else if (root == nullptr) {
                out << "";
            } else {
                display(root->right, out, counter + 1);
                for (unsigned int i = 0; i < counter; i++) out << "  ";
                char c = root->color ? 'b' : 'r';
                out << c << root->data << "\n";
                display(root->left, out, counter + 1);
            }
        }

Insertion in red-black/red_black_tree.h at line 56 [4.187]

[3.623]

        void left_rotate(Node* x) {
            Node* y = x->right;
            x->right = y->left;
            if (y->left != nullptr) {
                y->left->parent = x;
            }
            y->parent = x->parent;
            if (x->parent == nullptr) {
                m_root = y;
            } else if (x == x->parent->left) {
                x->parent->left = y;
            } else {
                x->parent->right = y;
            }
            y->left = x;
            x->parent = y;
        }
        void right_rotate(Node* x) {
            Node* y = x->left;
            x->left = y->right;
            if (y->right != nullptr) {
                y->right->parent = x;
            }
            y->parent = x->parent;
            if (x->parent == nullptr) {
                m_root = y;
            } else if (x == x->parent->right) {
                x->parent->right = y;
            } else {
                x->parent->left = y;
            }
            y->right = x;
            x->parent = y;
        }

Replacement in red-black/red_black_tree.h at line 94 [4.187]

B:BD[3.681] → [3.681:815]

        RedBlackTree(const RedBlackTree& tree);
        ~RedBlackTree();
        RedBlackTree& operator=(const RedBlackTree& rhs);

[3.681]

[3.815]

        
        RedBlackTree(const RedBlackTree& tree) : m_root(nullptr) {
            m_root = copy(tree.m_root);
        }
        ~RedBlackTree() {
            make_empty(m_root);
        }
        RedBlackTree& operator=(const RedBlackTree& rhs) {
            if (this == &rhs)
                return *this;
            make_empty(m_root);
            m_root = copy(rhs.m_root);
            return *this;
        }

Replacement in red-black/red_black_tree.h at line 116 [4.187]

B:BD[3.947] → [3.947:985]

                return node->colour;

[3.947]

[3.985]

                return node->color;

Insertion in red-black/red_black_tree.h at line 160 [4.187]

[3.2209]


        void insert(const T& item) {
            if (contains(item)) {
                return;
            } else {
                Node* new_node = new Node(item);
                if (m_root == nullptr) {
                    m_root = new_node;
                } else {
                    Node* temp = m_root;
                    Node* running_parent;
                    // the default node color is black but newly inserted nodes are red so we must update here
                    new_node->color = RED;
                    while (temp != nullptr) {
                        running_parent = temp;
                        if (item < temp->data)
                            temp = temp->left;
                        else if (item > temp->data)
                            temp = temp->right;
                    }

Replacement in red-black/red_black_tree.h at line 181 [4.187]

B:BD[3.2211] → [3.2211:2248]

        void insert(const T& item);

[3.2211]

[3.2248]

                    new_node->parent = running_parent;
                    if (item > running_parent->data)
                        running_parent->right = new_node;
                    else 
                        running_parent->left = new_node;
                    
                    if (new_node->parent->parent == nullptr)
                        return;
                    
                    insert_fix(new_node);
                }
            }
        }
        void insert_fix(Node* node) {
            Node* uncle;
            while (node->parent->color == RED) {
                if (node->parent == node->parent->parent->right) {
                    uncle = node->parent->parent->left;
                    if (uncle->color == RED) {
                        uncle->color = BLACK;
                        node->parent->color = BLACK;
                        node->parent->parent->color = RED;
                        node = node->parent->parent;
                    } else {
                        if (node == node->parent->left) {
                            node = node->parent;
                            right_rotate(node);
                        }
                        node->parent->color = BLACK;
                        node->parent->parent->color = RED;
                        left_rotate(node->parent->parent);
                    }
                } else {
                    uncle = node->parent->parent->right;

Insertion in red-black/red_black_tree.h at line 217 [4.187]

[3.2250]

                    if (uncle->color == RED) {
                        uncle->color = BLACK;
                        node->parent->color = BLACK;
                        node->parent->parent->color = RED;
                        node = node->parent->parent;
                    } else {
                        if (node == node->parent->right) {
                            node = node->parent;
                            left_rotate(node);
                        }
                        node->parent->color = BLACK;
                        node->parent->parent->color = RED;
                        right_rotate(node->parent->parent);
                    }
                }
                if (node == m_root)
                    break;
            }
            m_root->color = BLACK;
        }

Insertion in red-black/red_black_tree.h at line 239 [4.187]

[3.2287]


        void make_empty(Node* &node) {
            if (node != nullptr) {
                make_empty(node->left);
                make_empty(node->right);
                delete node;
            }
            node = nullptr;
        }
        void print_tree(std::ostream& out=std::cout) const {
            Node* temp = m_root;
            display(temp, out);
        }

Replacement in avl-bst/binary_search_tree.h at line 27 [2.1208]
B:BD[2.1737] → [2.1737:1776]
```
        Node* copy(Node* node) const{
```
[2.1737]
[2.1776]
```
        Node* copy(Node* node) const {
```

second attempt at pushing rbt changes

Dependencies

In channels

Change contents

Replacement in red-black/red_black_tree_tests.cpp at line 3 [4.40]

Insertion in red-black/red_black_tree_tests.cpp at line 18 [4.40]

Insertion in red-black/red_black_tree.h at line 2 [4.187]

Replacement in red-black/red_black_tree.h at line 13 [4.187]

Insertion in red-black/red_black_tree.h at line 16 [4.187]

Replacement in red-black/red_black_tree.h at line 20 [4.187]