Trinary Search Tree

Question

I'm probably not the first to think this up, but here we go. An trinary search tree is a generalization of a binary search tree in the sense that instead of a comparison function returning true or false, it will return -1 for less than, 1 for greater than, and 0 for equivalent. Once equivalence is found, a search along the "equivalence branch" will be made until equality if found. An example is where

compare (const std::string& a, const std::string& b)

outputs -1 if a.length() < b.length(), 1 if a.length() > b.length(), and 0 if a.length() == b.length(). Inserting a node shall always be at the bottom of the equivalence branch (if any).

The time complexity of a search in a trinary search tree is O(logN) + O(M), where M is the length of the equivalence branch (if any) of the target value (I think). Hence a trinary search tree is less efficient than a binary search tree, but nevertheless it is good practice (and fun!) to write one up.

It does have the advantage of allowing for using tricky types (for the node values) where it is not clear what a comparison function such that both < and > being false implying equality would be. I cannot yet think of such a class that would fall in this category, but there is should be examples out there. In the example below, lexicographical ordering would work for strings to allow using a binary tree instead of a trinary tree, but let's assume that such an ordering does not exist for strings, and we have to resort to using the above comparison function and thus using a trinary tree.

At any rate, here is my (fully compiling) implementation of a Trinary Search Tree. All tests conducted have passed. I tried to be as up-to-date in the C++ language as I could. Anyone reviewing this need not read every function I've defined here, but reading a handful and critiquing them is welcomed, especially the move constructor, move assignment operator, and such.

#include <iostream>
#include <string>
#include <memory>
#include <functional>

template <typename T, typename Comparator>
class TrinaryTree {
    public:
        enum TreeTraversal {Preorder, Postorder, Inorder1, Inorder2};
    private:
        class Node {
            private:
                TrinaryTree& trinaryTree;  // Reference data member because every TrinaryTree::Node belongs to a TrinaryTree.
                T value;
                std::shared_ptr<Node> left = nullptr, center = nullptr, right = nullptr, parent = nullptr;  // 'parent' is actually not needed here, but if one were to apply a red-black tree type of reordering for optimization purposes, then it would be needed.  But for removing the root of the tree, 'parent' is useful for identify if a node is the root or not.
                friend class TrinaryTree;
            public:
                Node (TrinaryTree& tree, const T& t) : trinaryTree(tree), value(t) {}
                Comparator getComparator() const {return trinaryTree.comparator;}
                inline std::shared_ptr<Node> insert (TrinaryTree&, const T&, std::shared_ptr<Node>&);
                inline std::shared_ptr<Node> search (const T&, std::shared_ptr<Node>&);
                inline std::shared_ptr<Node> remove (const T&, std::shared_ptr<Node>&);
            private:
                Node (const Node&);
                Node (Node&&);
                Node& operator= (const Node&);
                Node& operator= (Node&&);
                inline std::shared_ptr<Node> findMaxNode (const std::shared_ptr<Node>&);    
                inline std::shared_ptr<Node> removeMaxNode (std::shared_ptr<Node>&, std::shared_ptr<Node>&); 
                bool isRoot() const {return parent == nullptr;}
        };
        template <TreeTraversal, typename = void> struct ExecuteActionHelper;
    private:
        std::shared_ptr<Node> root;
        Comparator comparator;
    public:
        TrinaryTree (const Comparator& comp = Comparator()) : root(nullptr), comparator(comp) {}
        TrinaryTree (const TrinaryTree<T, Comparator>& other) : root(std::shared_ptr<Node>(new Node(*other.root))) {std::cout << "\nTrinaryTree copy constructor called.\n";}  // 'root(std::shared_ptr<Node>(other.root))' would also copy the entire tree, but it would be a shallow copy (no new nodes are being instantiated).
        TrinaryTree (TrinaryTree<T, Comparator>&& other) : root(other.root) {other.root = nullptr;  std::cout << "\nTrinaryTree move constructor called.\n";}
        TrinaryTree& operator= (const TrinaryTree&);
        TrinaryTree& operator= (TrinaryTree&&);
        std::shared_ptr<Node> insert (const T& t) {return root->insert(*this, t, root);}
        std::shared_ptr<Node> remove (const T& t) {return root->remove(t, root);}
        std::shared_ptr<Node> search (const T& t) {std::shared_ptr<Node> node = root->search (t, root);  std::cout << node->value << " found.\n";  return node;}
        template <TreeTraversal Tr = Preorder, typename F = std::function<void(T)>> void executeAction (const F& f) const {executeActionHelper<Tr> (root, f);}
        inline void display() const;
        void replaceRoot (std::shared_ptr<Node> node) {root = node;  root->parent = nullptr;}
    private:
        inline void displayNodeAndChildren (const std::shared_ptr<Node>&) const;
        template <TreeTraversal Tr, typename F> void executeActionHelper (const std::shared_ptr<Node>& node, const F& f) const {ExecuteActionHelper<Tr>::template execute(node, f);}
};

template <typename T, typename Comparator>
template <typename P>
struct TrinaryTree<T, Comparator>::ExecuteActionHelper<TrinaryTree<T, Comparator>::Preorder, P> {
    template <typename F>
    static void execute (const std::shared_ptr<TrinaryTree<T, Comparator>::Node>& node, const F& f) {
        if (!node)
            return;
        f(node->value);
        execute (node->left, f);
        execute (node->center, f);
        execute (node->right, f);
    }
};

template <typename T, typename Comparator>
template <typename P>
struct TrinaryTree<T, Comparator>::ExecuteActionHelper<TrinaryTree<T, Comparator>::Postorder, P> {
    template <typename F>
    static void execute (const std::shared_ptr<TrinaryTree<T, Comparator>::Node>& node, const F& f) {
        if (!node)
            return;
        execute (node->left, f);
        execute (node->center, f);
        execute (node->right, f);
        f(node->value);
    }
};

template <typename T, typename Comparator>
template <typename P>
struct TrinaryTree<T, Comparator>::ExecuteActionHelper<TrinaryTree<T, Comparator>::Inorder1, P> {
    template <typename F>
    static void execute (const std::shared_ptr<TrinaryTree<T, Comparator>::Node>& node, const F& f) {
        if (!node)
            return;
        execute (node->left, f);
        f(node->value);
        execute (node->center, f);
        execute (node->right, f);
    }
};

template <typename T, typename Comparator>
template <typename P>
struct TrinaryTree<T, Comparator>::ExecuteActionHelper<TrinaryTree<T, Comparator>::Inorder2, P> {
    template <typename F>
    static void execute (const std::shared_ptr<TrinaryTree<T, Comparator>::Node>& node, const F& f) {
        if (!node)
            return;
        execute (node->left, f);
        execute (node->center, f);
        f(node->value);
        execute (node->right, f);
    }
};

template <typename T, typename Comparator>
inline std::shared_ptr<typename TrinaryTree<T, Comparator>::Node> TrinaryTree<T, Comparator>::Node::insert (TrinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
    if (!node) {
        std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
        node = newNode;  // This assignment can only work if node is passed by reference.
        return newNode;
    }
    const int result = getComparator()(t, node->value);
    if (result == 0) {
        node->center = insert (tree, t, node->center);
        node->center->parent = node;
    }
    else if (result < 0) {
        node->left = insert (tree, t, node->left);
        node->left->parent = node;
    }
    else {
        node->right = insert (tree, t, node->right);
        node->right->parent = node;
    }
    return node;  // So if node is not empty, then the same node is returned, causing no value change in the four assignment lines above.  If using std::unique_ptr instead of std::shared_ptr, this line will have to change to return std::move(node), which will remove the root of the tree (tested).
}

template <typename T, typename Comparator>
inline std::shared_ptr<typename TrinaryTree<T, Comparator>::Node> TrinaryTree<T, Comparator>::Node::search (const T& t, std::shared_ptr<Node>& node) {
    const int result = getComparator()(t, node->value);
    if (result == 0)
        return (t == node->value) ? node : search (t, node->center);
    else if (result < 0)
        return search (t, node->left);
    else
        return search (t, node->right);
}

template <typename T, typename Comparator>
inline std::shared_ptr<typename TrinaryTree<T, Comparator>::Node> TrinaryTree<T, Comparator>::Node::findMaxNode (const std::shared_ptr<Node>& node) {
    if (!node)
        return nullptr;
    if (!node->right)
        return node;  // If node has a central node, then return node will still give a node with maximal value since the central node has compares equal to it.
    return (findMaxNode(node->right));
}

template <typename T, typename Comparator>
inline std::shared_ptr<typename TrinaryTree<T, Comparator>::Node> TrinaryTree<T, Comparator>::Node::removeMaxNode (std::shared_ptr<Node>& node, std::shared_ptr<Node>& maxNode) {
    if (node == maxNode) {
        if (!maxNode->center) {
            if (maxNode->left)
                maxNode->left->parent = node;
            return maxNode->left;  // Just as in the Binary Tree case.
        }
        maxNode->center->left = maxNode->left;  // But if maxNode has a central node, then that central node is equivalent in value to it and thus is greater than maxNode's leftNode (if it exists).  Thus we return maxNode->center instead, but first it must inherit a left node, namely maxNode->left since it is replacing maxNode.
        maxNode->center->parent = maxNode->parent;  // maxNode->center's new parent is maxNode->parent.
        return maxNode->center;
    }
    node->right = removeMaxNode (node->right, maxNode);
    return node;
}

template <typename T, typename Comparator>
inline std::shared_ptr<typename TrinaryTree<T, Comparator>::Node> TrinaryTree<T, Comparator>::Node::remove (const T& t, std::shared_ptr<Node>& node) {
    const int result = getComparator()(t, node->value);
    if (result < 0)
        node->left = remove (t, node->left);
    else if (result > 0)
        node->right = remove (t, node->right);
    else {
        if (!node->left && !node->center && !node->right)  // If node has no children, return nullptr.
            return nullptr;
        if (node->center) {  // If node has a central child, simply replace it with that child (since it compares equal to it, so the tree is still order-preserved).
            node->center->left = node->left;
            node->center->right = node->right;
            if (node->isRoot())
                trinaryTree.replaceRoot(node->center);
            return node->center;  // The subtree at node has node->center removed because node->center cannot have any left or right child.  node is automatically deleted since its use_count is now zero.
        }
        if (node->left && !node->center && !node->right) {  // If one child only, return that child.
            if (node->isRoot())
                trinaryTree.replaceRoot(node->left);
            return node->left;
        }
        if (!node->left && !node->center && node->right) {
            if (node->isRoot())
                trinaryTree.replaceRoot(node->right);
            return node->right;
        }
        // So now we've reached the last case, where node has two children and they are the left and right node.  This is very similar to the binary tree case where the node being removed has two children, but removeMaxNode's definition is a bit trickier.
        std::shared_ptr<Node> maxNode = findMaxNode(node->left);
        maxNode->left = removeMaxNode(node->left, maxNode);
        maxNode->center = node->center;
        maxNode->right = node->right;
        if (node->isRoot())
            trinaryTree.replaceRoot(maxNode);
        return maxNode;
    }
    return node;
}

template <typename T, typename Comparator>
inline void TrinaryTree<T, Comparator>::display() const {
    displayNodeAndChildren(root);  
    if (root) 
        std::cout << "Tree Root = " << root->value << "\n\n";
    else
        std::cout << "There is no root.\n";
}

template <typename T, typename Comparator>
inline void TrinaryTree<T, Comparator>::displayNodeAndChildren (const std::shared_ptr<Node>& node) const {
    if (!node) {
        std::cout << '\n';
        return;
    }
    const T& t = node->value;
    std::cout << t << '\n';
    std::cout << t << "'s left = "; 
    displayNodeAndChildren (node->left);
    std::cout << t << "'s right = "; 
    displayNodeAndChildren (node->right);
    std::cout << t << "'s center = ";
    displayNodeAndChildren (node->center);
}

template <typename T, typename Comparator>
TrinaryTree<T, Comparator>& TrinaryTree<T, Comparator>::operator= (const TrinaryTree<T, Comparator>& other) {  // TrinaryTree assignment operator.
    std::cout << "TrinaryTree assignment operator called.\n";
    if (this == &other)
        return *this;
    root = std::shared_ptr<Node>(new Node(*other.root));
//  Below works too, calling the Node assignment operator on the root, while the Node copy constructor for the remaining nodes is called.
//  root = std::make_shared<Node>(*this, T{});
//  *root = *other.root;  // Calls the Node assignment operator.
    return *this;
}

template <typename T, typename Comparator>
TrinaryTree<T, Comparator>& TrinaryTree<T, Comparator>::operator= (TrinaryTree<T, Comparator>&& other) {  // TrinaryTree move assignment operator.
    std::cout << "\nTrinaryTree move assignment operator called.\n";
    if (this == &other)
        return *this;
    root = other.root;
    other.root = nullptr;
    return *this;
}

template <typename T, typename Comparator>
TrinaryTree<T, Comparator>::Node::Node (const TrinaryTree<T, Comparator>::Node& other) : trinaryTree(other.trinaryTree), value(other.value) {  // Node copy constructor.
    std::cout << "Node copy constructor called.\n";
    if (other.left) left = std::shared_ptr<Node>(new Node(*other.left));  // Each child invokes the Node copy constructor recursively.  New shared_ptrs are created, thereby resulting in a deep TrinaryTree copy, rather than a shallow copy.
    if (other.center) center = std::shared_ptr<Node>(new Node(*other.center));
    if (other.right) right = std::shared_ptr<Node>(new Node(*other.right));
//  These work too (tested), but they don't call the Node copy constructor recursively (the "Node copy constructor called" line does not show up), and the result are shallow copies of the nodes instead of deep copies.
//  if (other.left) {left = std::shared_ptr<Node>(other.left);}
//  if (other.center) {center = std::shared_ptr<Node>(other.center);}
//  if (other.right) {right = std::shared_ptr<Node>(other.right);}
}

template <typename T, typename Comparator>
typename TrinaryTree<T, Comparator>::Node& TrinaryTree<T, Comparator>::Node::operator= (const TrinaryTree<T, Comparator>::Node& other) {  // Node assignment operator.
    std::cout << "Node assignment operator called.\n";
    if (this == &other)
        return *this;
    value = other.value;
    if (other.left) left = std::shared_ptr<Node>(new Node(*other.left));  // Node copy constructor called.  Previously owned node is deleted automatically.
    if (other.center) center = std::shared_ptr<Node>(new Node(*other.center));
    if (other.right) right = std::shared_ptr<Node>(new Node(*other.right));
    return *this;
}

template <typename T, typename Comparator>
TrinaryTree<T, Comparator>::Node::Node (TrinaryTree<T, Comparator>::Node&& other) : trinaryTree(other.trinaryTree), value(other.value),
        left(std::shared_ptr<Node>(new Node(*other.left))), center(std::shared_ptr<Node>(new Node(*other.center))), right(std::shared_ptr<Node>(new Node(*other.right))) {  // Node move constructor.
    other.left = nullptr;
    other.center = nullptr;
    other.right = nullptr;
}

template <typename T, typename Comparator>
typename TrinaryTree<T, Comparator>::Node& TrinaryTree<T, Comparator>::Node::operator= (TrinaryTree<T, Comparator>::Node&& other) {  // Node move assignment operator.
    if (this == &other)
        return *this;
    value = other.value;
    left = std::shared_ptr<Node>(new Node(*other.left));
    center = std::shared_ptr<Node>(new Node(*other.center));
    right = std::shared_ptr<Node>(new Node(*other.right));
    other.left = nullptr;
    other.center = nullptr;
    other.right = nullptr;
    return *this;
}

// Testing
struct StringLengthComparator {
    int operator ()(const std::string& a, const std::string& b) const {
        return (a.length() < b.length()) ? -1 : (a.length() > b.length()) ? 1 : 0;
    }
};

const std::string names[] = {"Mahnoor", "Aiman", "Zarish", "Ifrah", "Zumer", "Theebika", "Zoya", "Nabela", "Afrah", "Ashna", "Saleha"};

TrinaryTree<std::string, StringLengthComparator> makeTrinaryTree() {
    TrinaryTree<std::string, StringLengthComparator> tree;
    for (const std::string& s : names)
        tree.insert(s);
    return tree;
}

int main() {
    TrinaryTree<std::string, StringLengthComparator> tree = makeTrinaryTree();
    tree.display();

    for (const std::string& s : names)
        const auto node = tree.search(s);  // Now do whatever with 'node'.

    const std::function<void(std::string)> action = [](const std::string& str) {std::cout << str << ' ';};
    std::cout << "\nPreorder traversal with action at each node:\n     ";
    tree.executeAction(action);  // The default tree traversal.
    std::cout << "\nPostorder traversal with action at each node:\n     ";
    tree.executeAction<TrinaryTree<std::string, StringLengthComparator>::Postorder>(action);
    std::cout << "\nInorder1 traversal with action at each node:\n     ";
    tree.executeAction<TrinaryTree<std::string, StringLengthComparator>::Inorder1>(action);
    std::cout << "\nInorder2 traversal with action at each node:\n     ";
    tree.executeAction<TrinaryTree<std::string, StringLengthComparator>::Inorder2>(action);

//  tree.remove("Theebika");  std::cout << "\n\nTheebika removed:\n";  tree.display();  // Removing a node with no children (passed).
//  tree.remove("Zarish");  std::cout << "\n\nZarish removed:\n";  tree.display();  // Removing a node with central child only (passed).
//  tree.remove("Aiman");  std::cout << "\n\nAiman removed:\n";  tree.display();  // Removing a node with central child only (passed).
    tree.remove("Mahnoor");  tree.display();  // Removing the root of the tree (which has a left and right child but no central child, and where maxNode has a central child).  Test passed.

    const std::string names2[] = {"Mahnoor", "Nabela", "Theebika", "MaryTylerMoore", "Ifrah", "Zoya"};
    TrinaryTree<std::string, StringLengthComparator> tree2;
    for (const std::string& s : names2)
        tree2.insert(s);
    std::cout << "\n\nSecond tree:\n\n";
    tree2.display();

    tree2.remove("Mahnoor");  // Removing a node with only a left and right child, and is also the root (passed).
    tree2.display();

    TrinaryTree<std::string, StringLengthComparator> newTree1(tree);  // Invokes TrinaryTree copy constructor.
    newTree1.display();

    TrinaryTree<std::string, StringLengthComparator> newTree2;
    newTree2 = tree;  // Invokes TrinaryTree assignment constructor.
    newTree2.display(); 

    TrinaryTree<std::string, StringLengthComparator> newTree3;
    newTree3 = std::move(newTree1);
    std::cout << "newTree3 after move assignment:\n";
    newTree3.display();
    std::cout << "\nnewTree1 after move assignment:\n";
    newTree1.display();  // newTree1 has nothing left but its root.

    TrinaryTree<std::string, StringLengthComparator> newTree4 (std::move(makeTrinaryTree()));
    std::cout << "newTree4 after move constructor call:\n";
    newTree4.display();
}

Answer 1

In all, this code is not bad at all. And generically, no it's not new, but is a particular instance of an m-ary tree with \$m = 3\$. Here are some things that may help you improve it.

Separate declaration from definition

This could work as a header-only template but it's a bit difficult to discern the interface because most of the functions are defined inline. That's not a technical error, but I would probably separate the two, even if they are still in the same file. It makes the code longer but easier to use, in my opinion.

Allow variadic functions

The code currently has an executeAction function which is a nice idea, but is unfortunately limited because it can't accept arguments. So I would suggest rewriting executeActionHelper as this:

template <TreeTraversal Tr, typename F, typename ...Args> decltype(auto) executeActionHelper (const std::shared_ptr<Node>& node, const F& f, Args&&... args) const {ExecuteActionHelper<Tr>::template execute(node, f, std::forward<Args>(args)...);}

If you make all of the corresponding changes in execute and executeAction, the result is that you can now do things like this:

auto action = [](const std::string& str, std::ostream& out)->void { out << str << ' ';};
std::cout << "\nPreorder traversal with action at each node:\n     ";
tree.executeAction(action, std::cout);

Rethink the relationship between tree and node

Every well-formed non-nullptr Node is also a tree, so I'd suggest that the trinaryTree member of Node is not needed. I'd also make Node much simpler, moving most of its functionality to the TrinaryTree instead. It might look something like this:

struct Node {
    std::shared_ptr<Node> left, center, right;
    T value;
};

Consider making the tree more generic

As mentioned earlier, this is a specific instance of an m-ary tree for which \$m = 3\$. This suggests that one way to make this more generic would be to create an array of child nodes and pass in \$m\$ as a template parameter.