Project3/RBT.cpp at main · gracetholl/Project3 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include "RBT.h"
#include <iostream>
void RBT::leftRotate(RBTNode* &root, RBTNode* &node) { // left rotation for balance
    RBTNode* right = node->right;
    node->right = right->left;
    if (node->right != nullptr)
        node->right->parent = node;
    right->parent = node->parent;
    if(node->parent == nullptr)
        root = right;
    else if(node == node->parent->left)
        node->parent->left = right;
    else
        node->parent->right = right;
    right->left = node;
    node->parent = right;

}
void RBT::rightRotate(RBTNode* &root, RBTNode* &node) { // right rotation for balance
    RBTNode* left = node->left;
    node->left = left->right;
    if (node->left != nullptr)
        node->left->parent = node;
    left->parent = node->parent;
    if(node->parent == nullptr)
        root = left;
    else if(node == node->parent->right)
        node->parent->right = left;
    else
        node->parent->left = left;
    left->right = node;
    node->parent = left;

}
RBTNode* RBT::basicInsert(RBTNode* root, Species key) { // insert nodes into tree
    if (root == nullptr) {
        RBTNode* t = new RBTNode(key);
        return t;
    }
    if (key.GetName() > root->s.GetName()) {
        root->right = basicInsert(root->right, key);
        root->right->parent = root;
    }
    else {
        root->left = basicInsert(root->left, key);
        root->left->parent = root;
    }
    return root;

}
void RBT::fixTree(RBTNode* &newNode) { // code inspired by tree problem solving lecture
 if(newNode->parent == nullptr) {
     newNode->setRed(false);
     return;
 }
 if(!(newNode->parent->isRed())) {
     return;
 }
    RBTNode* parent = newNode->parent;
    RBTNode* grandparent = parent->parent;
    RBTNode* uncle;
 if(grandparent->left == parent)
     uncle = grandparent->right;
 else
     uncle = grandparent->left;
 if(uncle != nullptr && uncle->isRed()){
     parent->setRed(false);
     uncle->setRed(false);
     grandparent->setRed(true);
     fixTree(grandparent);
     return;
 }
 if (newNode == parent->right && parent == grandparent->left) {
     rightRotate(root, parent);
     newNode = parent;
     parent = newNode->parent;
 }
 else if (newNode == parent->left && parent == grandparent->right) {
     leftRotate(root, parent);
     newNode = parent;
     parent = newNode->parent;
 }
 parent->setRed(false);
 grandparent->setRed(true);
 if(newNode == parent->left)
     rightRotate(root, grandparent);
 else
     leftRotate(root, grandparent);
}
RBTNode* RBT::search(RBTNode* root, string key) { // find node based on species name
    if (root == nullptr || root->s.GetName() == key) {
        return root;
    }
    if (key > root->s.GetName())
        return search(root->right, key);
    else
        return search(root->left, key);
}
void RBT::InOrder(RBTNode* root) { // tree traversal
    if(root != nullptr) {
        InOrder(root->left);
        root->s.GetStatus();
        InOrder(root->right);
    }
}
RBTNode* RBT::GetRoot() {
    return root;
}