This is a basic RED-BLACK Tree program which works fine for most part other than the insertion and Deletion. I tried a debugger but am still unable to find the problem. The preorder is E C B A D I G F H K, where as it is supposed to be E B A C D H F G I K. The postorder is A B D C F H G K I E, where as it is supposed to be A C B E G K I H F D. And the inorder is A B C D E F G H I K
#include <iostream>
#include <cstdlib>
using namespace std;
template <typename keytype, typename valuetype> //one lesson try to fit for of the functions from the private so that the access can be easier
class RBTree{
private:
struct Node{
bool color; //color is true for red and false for black
int size;
Node *left, *right, *parent;
keytype key;
valuetype val;
};
Node* root;
Node* newNode(keytype k, valuetype v, bool color = true){ //usually starts with the root and then the leaves can be placed to the left and right
Node *newRBNode = new Node;
newRBNode->color = color;
newRBNode->key = k;
newRBNode->left = NULL;
newRBNode->right = NULL;
newRBNode->parent = NULL;
newRBNode->size = 1; //size 1 as it is 1 leaf initially
newRBNode->val = v;
return newRBNode;
}
void clearMemory(Node *current) {
if (current == NULL){ //uses recursion to go through the tree and delete the leaves
return;
}
clearMemory(current->left);
if (current->left != NULL){
free(current->left);
}
clearMemory(current->right);
if (current->right != NULL){
free(current->right);
}
}
int size(Node* current){
if (current == NULL){
return 0;
}
return current->size;
}
Node* leftRotate(Node* current){
Node* y = current->right;
current->right = y->left;
y->left = current;
y->color = y->left->color;
y->left->color = true;
current->size = size(current->left) + size(current->right) + 1;
y->size = size(y->left) + size(y->right) + 1;
return y;
}
Node* rightRotate(Node* current){ //conventional rotation from textbook and updates the size
Node* y = current->left;
current->left = y->right;
y->right = current;
y->color = y->right->color;
y->right->color = true;
current->size = size(current->left) + size(current->right) + 1;
y->size = size(y->left) + size(y->right) + 1;
return y;
}
Node* copy(Node* current){ //uses recursion to copy
Node* node = newNode(current->key, current->val, current->color);
if (current->left != NULL){
node->left = copy(current->left);
}
if(current->right != NULL){
node->right = copy(current->right);
}
node->size = current->size;
return node;
}
void colorFlip(Node* current){
current->color = !(current->color); //flips the color of the parent and the children (usually one red and two blacks)
current->left->color = !(current->left->color);
current->right->color = !(current->right->color);
}
bool isRed(Node* current){ //needs fixing
if (current == NULL){
return false;
}
return (current->color);
}
Node* Insertion(Node* current, keytype key, valuetype val){ //Messed up
if (current == NULL){
Node* test = newNode(key, val);
return test;
}
if (isRed(current->left) && isRed(current->right)){
colorFlip(current);
}
if (key < current->key){
current->left = Insertion(current->left, key, val);
}
else if (key > current->key){
current->right = Insertion(current->right, key, val);
}
else if (current->key == key){
current->val = val;
}
if (isRed(current->right)){ //if right node is red before the introduced rode then rotation happens
current = leftRotate(current);
}
if (isRed(current->left) && isRed(current->left->left)){ //conflict happens and the rotation starts
current = rightRotate(current);
}
if(isRed(current->right)){ //fixes up the whole tree after deletion
current = leftRotate(current);
}
if (isRed(current->left) && isRed(current->left->left)){
current = rightRotate(current);
}
if (isRed(current->left) && isRed(current->right)){
colorFlip(current);
}
current->size = size(current->left) + size(current->right) + 1;
return current;
}
Node* Deletion(Node* current, keytype key){ //Gotta fix it
if (key < current->key){ //uses the textboob delete fixation function
if (!isRed(current->left) && !isRed(current->left->left)){
colorFlip(current);
if (isRed(current->right->left)){
current->right = rightRotate(current->right);
current = leftRotate(current);
colorFlip(current);
}
}
current->left = Deletion(current->left, key);
}
else {
if (isRed(current->left)){
current = rightRotate(current);
}
if ((key == current->key) && (current->right == NULL)){
return NULL;
}
if(!isRed(current->right) && !isRed(current->right->left)){
colorFlip(current);
if (isRed(current->left->left)){
current = rightRotate(current);
colorFlip(current);
}
}
if (current->key == key){
Node* y = current->right;
while(y->left != NULL){
y = y->left;
}
current->key = y->key;
current->val = y->val;
current->right = Deletion(current->right, current->key);
}
else{
current->right = Deletion(current->right, key);
}
}
if(isRed(current->right)){ //fixes up the whole tree after deletion
current = leftRotate(current);
}
if (isRed(current->left) && isRed(current->left->left)){
current = rightRotate(current);
}
if (isRed(current->left) && isRed(current->right)){
colorFlip(current);
}
current->size = size(current->left) + size(current->right) + 1;
return current;
}
valuetype* findVal(Node* current, keytype key){
if (current == NULL){
return NULL;
}
else if (current->key == key){
return &(current->val);
}
else if(current->key > key){
return findVal(current->left, key);
}
else if(current->key < key){
return findVal(current->right, key);
}
return NULL;
}
keytype Position(Node* current, int sample){
int pos = size(current->left) + 1;
if (pos == sample){
return current->key;
}
else if(sample < pos){
return Position(current->left, sample);
}
else{
return Position(current->right, sample-pos);
}
}
int Rank(Node* current, keytype key){
if(current == NULL){
return 0;
}
else if(current->key > key){
return Rank(current->left, key);
}
else if(current->key < key){
return (size(current->left) + 1 + Rank(current->right, key));
}
else if(current->key == key){
return (current->size - size(current->right));
}
else{
return 0;
}
}
keytype* find_sucessor(Node* current, keytype K){
Node* successor = NULL;
while(current){
if (current->key > K){
successor = current;
current = current->left;
}
else{
current = current->right;
}
}
return &(successor->key);
}
keytype* find_predecessor(Node* current, keytype K){
Node* predecessor = NULL;
while(current){
if (current->key >= K){
current = current->left;
}
else{
predecessor = current;
current = current->right;
}
}
return &(predecessor->key);
}
void print_preorder(Node* current){
if (current == NULL){
return;
}
cout << current->key << " ";
print_preorder(current->left);
print_preorder(current->right);
}
void print_postorder(Node* current){
if (current == NULL){
return;
}
print_postorder(current->left);
print_postorder(current->right);
cout << current->key << " ";
}
void print_inorder(Node* current){
if (current == NULL){
return;
}
print_inorder(current->left);
cout << current->key << " ";
print_inorder(current->right);
}
public:
RBTree(){
root = NULL;
}
RBTree(keytype k[], valuetype v[], int S){ //black children all of them
root = NULL; //wrong gsfsdfsdf
int middle = (S-1)/2;
// for (int i = middle; i > 0; i--){ //insert from half till zero then half to full
// root = Insertion(root, k[i], v[i]);
// root->color = false;
// }
// for (int i = 0; i < S; i++){
// root = Insertion(root, k[i], v[i]);
// root->color = false; //false is black and true is red
// }
root = Insertion(root, k[middle], v[middle]);
root->color = false;
for (int i = 1; i <= middle; i++){
root = Insertion(root, k[middle-i], v[middle-i]);
root->color = false;
root = Insertion(root, k[middle+i], v[middle+i]);
root->color = false;
}
if (((2*middle)) != (S-1)){
root = Insertion(root, k[S-1], v[S-1]);
root->color = false;
}
}
RBTree(const RBTree<keytype, valuetype> &A){
root = copy(A.root);
}
RBTree<keytype, valuetype>& operator=(const RBTree<keytype, valuetype> &A){
root = copy(A.root);
return *this;
}
~RBTree(){
clearMemory(root);
free(root);
}
valuetype* search(keytype k){
return findVal(root,k);
}
void insert(keytype k, valuetype v){
root = Insertion(root, k, v);
root->color = false;
}
int remove(keytype k){
if (search(k) == NULL){
return 0;
}
int node = size(root);
root = Deletion(root, k);
return (node - size(root));
}
int rank(keytype k){
return Rank(root,k);
}
keytype select(int pos){
return Position(root, pos);
}
keytype* successor(keytype k){
return find_sucessor(root, k);
}
keytype* predecessor(keytype k){
return find_predecessor(root, k);
}
int size(){
return size(root);
}
void preorder(){
print_preorder(root);
cout << endl;
}
void inorder(){
print_inorder(root);
cout << endl;
}
void postorder(){
print_postorder(root);
cout << endl;
}
};
When I try to insert: A","B","C","D","E","F","G","H","I","K", I get the inorder correctly. But the postorder and preorder are incorrect. What do I do so that 3 of the views can be outputted correctly? I really appreciate your help.
Aucun commentaire:
Enregistrer un commentaire