95 lines
2.9 KiB
C++
95 lines
2.9 KiB
C++
#ifndef TREES_HPP
|
|
#define TREES_HPP
|
|
|
|
#include <fstream>
|
|
#include <memory>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
// Namespace for different implementations of trees
|
|
namespace tree_implementation
|
|
{
|
|
// General nodes for Tree
|
|
struct TreeNode
|
|
{
|
|
std::string key;
|
|
std::string color;
|
|
std::shared_ptr<TreeNode> leftChild;
|
|
std::shared_ptr<TreeNode> rightChild;
|
|
std::shared_ptr<TreeNode> parent;
|
|
TreeNode(std::string word);
|
|
};
|
|
|
|
// General list for Tree
|
|
class TreeList
|
|
{
|
|
public:
|
|
std::shared_ptr<TreeNode> head;
|
|
TreeList(void);
|
|
void InsertAtStart(std::string word);
|
|
void InsertAtEnd(std::string word);
|
|
void InsertAtPosition(std::string word);
|
|
void Remove(std::string word);
|
|
void Print(void);
|
|
protected:
|
|
;
|
|
private:
|
|
;
|
|
};
|
|
|
|
// Base Tree class
|
|
class TreeInterface
|
|
{
|
|
public:
|
|
TreeList tree;
|
|
TreeInterface(void);
|
|
void Search(std::string key);
|
|
std::shared_ptr<TreeNode> GetNodeWithWord(std::string wordToFind);
|
|
void InOrderTreeTraversal(std::shared_ptr<TreeNode> viewedNode);
|
|
void InOrderTreeTraversal(std::shared_ptr<TreeNode> viewedNode, std::ofstream* file);
|
|
void PrintParentKey(std::string key);
|
|
void PrintLeftChild(std::string key);
|
|
void PrintRightChild(std::string key);
|
|
protected:
|
|
bool IsNodeSearchSuccessful(std::shared_ptr<TreeNode> foundNode, std::string key);
|
|
virtual void Insert(std::shared_ptr<TreeNode> z);
|
|
virtual void InsertWordList(std::vector<std::string>* newWordList) = 0;
|
|
virtual void PrintPathToRoot(std::string key) = 0;
|
|
private:
|
|
std::shared_ptr<TreeNode> GetNodeWithWord(std::shared_ptr<TreeNode> viewedNode, std::string wordToFind);
|
|
};
|
|
|
|
// Binary Search Tree operations
|
|
class BinarySearchTree : public TreeInterface
|
|
{
|
|
public:
|
|
void Insert(std::string keyToInsert);
|
|
void InsertWordList(std::vector<std::string>* newWordList);
|
|
void PrintPathToRoot(std::string key);
|
|
protected:
|
|
;
|
|
private:
|
|
;
|
|
};
|
|
|
|
// Red-Black Tree operations
|
|
class RedBlackTree : public TreeInterface
|
|
{
|
|
public:
|
|
void Insert(std::string keyToInsert);
|
|
void InsertWordList(std::vector<std::string>* newWordList);
|
|
void PrintPathToRoot(std::string key);
|
|
void PrintColor(std::string key);
|
|
void PrintParentColor(std::string key);
|
|
void PrintUncleColor(std::string key);
|
|
protected:
|
|
;
|
|
private:
|
|
void InsertFixup(std::shared_ptr<TreeNode> z);
|
|
std::shared_ptr<TreeNode> GetUncleNode(std::shared_ptr<TreeNode> startNode);
|
|
void LeftRotate(std::shared_ptr<TreeNode> x);
|
|
void RightRotate(std::shared_ptr<TreeNode> x);
|
|
};
|
|
}
|
|
|
|
#endif |