C++ RedBlack Tree with Tree Traversal

implement following function. Add 4 traversal methods with prefect print( PreOrder, InOrder, PostOrder and LevelOrder).

-----------header-----------------

#pragma once #include #include #include #include

typedef unsigned char uint_8; namespace VGP244 { template class RBTree { enum class Color :uint_8 { Red, Black }; typedef void visitorFP(T const&);

struct RBNode { T data; Color color; std::shared_ptr left, right, parent; RBNode() :data(T()), color(Color::Red) {} RBNode(T val) :data(val), color(Color::Red) {}

void InOrderTraversal(visitorFP& v) { if (left) left->InOrderTraversal(v); v(data); if (right) right->InOrderTraversal(v); } };

typedef std::shared_ptr RBNodePtr; typedef std::shared_ptr RBNodeCPtr;

RBNodePtr root; void left_rotate(RBNodePtr) {} // to be done by students void right_rotate(RBNodePtr) {} // to be done by students. void insert(RBNodePtr && in) { //insert in the binary in the usual way treeInsert(root, in); assert(in && in->parent && root); // Now restore the red-block property RBNodePtr x = in; in->color = Color::Red; // this is not needed since default is red. while (x != root && x->parent->color == Color::Red) { if (x->parent == x->parent->parent->left) { RBNodePtr y = x->parent->parent->right; // right uncle if (y->color == Color::Red) //case 1: change the colors { x->parent->color = Color::Black; y->color = Color::Black; x->parent->parent->color = Color::Red; // Move x up the tree to get prepared for next iteration x = x->parent->parent; } else // y is a black node { if (x == x->parent->right) // x is to the right child { // case 2: move x up and rotate x = x->parent; left_rotate(x); } else // x is the left child { // case 3: change color and rotate right x->parent->color = Color::Black; x->parent->parent->color = Color::Red; right_rotate(x->parent->parent); } } } else // do the same as above, but this time for right side { RBNodePtr y = x->parent->parent->left; // left uncle if (y->color == Color::Red) //case 1: change the colors { x->parent->color = Color::Black; y->color = Color::Black; x->parent->parent->color = Color::Red; // Move x up the tree to get prepared for next iteration x = x->parent->parent; } else // y is a black node { if (x == x->parent->left) // x is to the left child { // case 2: move x up and rotate x = x->parent; right_rotate(x); } else // x is the right child { // case 3: change color and rotate right x->parent->color = Color::Black; x->parent->parent->color = Color::Red; left_rotate(x->parent->parent); } } } } }

// generic binary tree insert. To be done by students void treeInsert(RBNodePtr r, RBNodePtr in) {} static RBNodePtr constructNode(T val) { RBNodePtr node = std::make_shared(val); return node; }

bool query(T const& val) const {} // to be implemented by students void left_rotation(RBNodePtr pivot) {}// to be implemented by students void right_rotation(RBNodePtr pivot) {}// to be implemented by students

public: RBTree() : root(nullptr) {} void insert(T val) { insert(constructNode(val)); } bool remove(T val) { return false; } // THis is bonus point of 5 if you implement this. bool search(T val) const { return query(val); // return *(result->get()) != T(); }

void prettyprint() {} // to be implemented by students

void InOrderTraversal(visitorFP & v) { if (root) root->InOrderTraversal(v); } };

} // namespace VGP244

-----------------main.cpp-----------------------

#include #include #include "RBTree.h"

using namespace VGP244;

size_t numNodes{ 0 }; template void IncrementCounter(T & t) { ++numNodes; } int main() { std::array testArr{ 56, 8, 27, -4, 89, -45, 101, 54, 81, -34, -12, 92, 71, -50, 7 };

RBTree testRBTree;

// insert the array, one by one in the tree: for (auto a : testArr) testRBTree.insert(a);

std::cout << "Print the tree: "; testRBTree.prettyprint(); // doing some traversal on our tree: testRBTree.InOrderTraversal(IncrementCounter); std::cout << "NumNodes = " << numNodes << std::endl;

return 0; }