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
|
class NamesBinaryTree { // Storage of names in alphabetically order in a binary tree so that looking up names will be as efficient as possible
private:
class Node; // The way to forward declare a nested class, which is required for defining a member function pointer of NamesBinaryTree::Node in the next line.
typedef int (NamesBinaryTree::Node::*stringComparisonFunction) (const std::string&, const std::string&);
enum Colour {RED, BLACK};
class Node {
private:
NamesBinaryTree& namesBinaryTree; // reference data member because a Node must be part of a NamesBinaryTree
std::pair<std::string, Person*> personInfo; // for values of type other than std::pair<std::string, Person*> use T and template<T> the class
Node *left;
Node *right;
Node *parent;
Colour colour;
friend class NamesBinaryTree;
public:
Node (NamesBinaryTree& tree): namesBinaryTree (tree), colour (RED) {
// if (!isRoot() && (parent->colour == BLACK)) colour = RED;
// else if (parent && (parent->colour == RED)) colour = BLACK;
}
std::pair<std::string, Person*> PersonInfo () const {return personInfo;}
inline Node* insertNode (NamesBinaryTree& tree, Node*& node, Person* person, stringComparisonFunction sCF);
inline const Node* searchNode (const Node* node, const std::string& name, stringComparisonFunction sCF); // searchNode can no longer be declared const ever since the stringComparisonFunction parameter was put in. I'm not sure why because the stringComparisonFunction sCF is still not changing any data members of Node.
inline void destroySubtree (Node* node); // I currently see no reason to destroy any subtree of entireCircleTree.
inline int countNodesFrom (const Node* node) const;
inline void displayNodeAndChildren (const Node* node) const;
inline Node* findMaxNode (Node* node) const; // Declaring const Node* node gives problems.
inline Node* removeMaxNode (Node* node, Node* maxNode);
inline Node* removeNode (Node*& node, const Person* person, stringComparisonFunction sCF); // Removing names should actually never be done in entireCircleTree (entireCircle only grows or stays the same, but never shrinks). But p.247-256 in "Jumping into C++" (Allain) does give the code for it.
bool isRoot () const {return !parent;}
bool isLeftChild () const {return parent->left == this;}
bool isRightChild () const {return parent->right == this;}
// Member functions of NamesBinaryTree::Node that member function pointer stringComparisonFunction can point to:
inline int std_string_compare (const std::string&, const std::string&); // this uses std::string::compare
inline int caseSensitiveCompare (const std::string&, const std::string&) {return NOT_FOUND;} // not yet defined
inline int caseInsensitiveCompare (const std::string&, const std::string&) {return NOT_FOUND;} // not yet defined. Use tolower (#include <ctype.h>) on every letter and then use std::string::compare. An example is: http://www.cplusplus.com/reference/list/list/sort/
inline int mergedIntoOneWordCaseSensitiveCompare (const std::string&, const std::string&) {return NOT_FOUND;} // not yet defined
inline int mergedIntoOneWordCaseInsensitiveCompare (const std::string&, const std::string&) {return NOT_FOUND;} // not yet defined (remove all ' ' characters, and then use tolower (#include <ctype.h>) on every letter and then use std::string::compare)
};
Node *root; // root Node of the tree
public:
NamesBinaryTree (): root (nullptr) {}
~NamesBinaryTree () {root->destroySubtree (root);}
typedef Node NamesNode; // This is needed to declare Node outside of NamesBinaryTree since Node is a private nested class (so use NamesBinaryTreeNode::NamesNode *node, though auto *node = ... would also work too).
Node* insert (Person* person, stringComparisonFunction sCF) {
Node* insertedNode = root->insertNode (*this, root, person, sCF);
redBlackTreeCase1 (insertedNode); // Configures the tree into a red-black tree after the above insertion to maximize tree balancing.
return insertedNode;
}
const Node* search (const std::string& name, stringComparisonFunction sCF) const {return root->searchNode (root, name, sCF);}
Node* remove (const Person* person, stringComparisonFunction sCF) {return root->removeNode (root, person, sCF);}
int numNodes () const {return root->countNodesFrom (root);}
void displayTree () const;
// Red-black tree implementation methods
inline Node* grandparent (Node* node);
inline Node* uncle (Node* node);
inline void redBlackTreeCase1 (Node *node);
inline void redBlackTreeCase2 (Node *node);
inline void redBlackTreeCase3 (Node *node);
inline void redBlackTreeCase4 (Node *node);
inline void redBlackTreeCase5 (Node *node);
inline void rotateLeft (Node* node);
inline void rotateRight (Node* node);
};
|