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 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
|
// rbtree.cpp
#include <iostream>
#include <iomanip>
#include "rbtree.h"
using std::cout;
using std::setw;
using std::endl;
void RBTree::reverseInOrderPrint(Node *x, int depth) {
if ( x != nil ) {
reverseInOrderPrint(x->right, depth+1);
cout << setw(depth*4+4) << x->color << " ";
cout << *(x->key) << " " << *(x->value) << endl;
reverseInOrderPrint(x->left, depth+1);
}
}
RBTree::RBTree()
{
nil = new Node();
root = nil;
}
RBTree::~RBTree()
{
//delete[] root;
}
void RBTree::rbInsert(const string& key_given, const string& value_given)
{
if(root != nil)
cout << *(root -> key) << " <- root key at beginning of insert function" << endl;
Node* input_node = new Node(key_given, value_given, nil);
Node* target = root;
Node* target_parent = nil;
// A loop used to set target to point to where we want to insert the new node and target_parent to point to its parent
while(target != nil)
{
target_parent = target;
// If the input node key is alphabetically before target's key then move to the left child
if(input_node -> key -> compare(*(target -> key)) < 0)
target = target -> left;
// Otherwise move to the right child
else
target = target -> right;
}
input_node -> parent = target_parent;
// If the list is empty then make the new node root
if(target_parent == nil)
root = input_node;
// Else if its key comes before its parent's key alphabetically then make it the left child of target_parent
else if(input_node -> key -> compare(*(target_parent -> key)) < 0)
target_parent -> left = input_node;
// Else make it the right child of target_parent
else
target_parent -> right = input_node;
input_node -> left = nil;
input_node -> right = nil;
input_node -> color = 'R';
/*rbInsertFixup(input_node);*/
cout << *(root -> key) << " <- root key at end of insert function" << endl;
}
//void RBTree::rbInsertFixup(
RBTree::Node::Node()
{
parent = NULL;
left = NULL;
right = NULL;
color = 'B';
key = NULL;
value = NULL;
}
RBTree::Node::Node(const string& key_given, const string& value_given, Node* nil_pntr)
{
parent = nil_pntr;
left = nil_pntr;
right = nil_pntr;
color = 'R';
key = &key_given;
value = &value_given;
}
RBTree::Node::~Node()
{
if(left != NULL)
delete left;
if(right != NULL)
delete right;
}
int main()
{
RBTree tree;
string x = "Seth";
string y = "My Birthday";
//tree.rbInsert(x, y);
//tree.rbInsert("Dana", "Her Birthday");
tree.rbInsert("Zack", "His Birthday");
tree.rbInsert("Terri", "Her Birthdays");
tree.rbInsert("Zzck", "HBD");
return 0;
}
}
|