Multiway Search Trees

Definition

3-way trees

  • Elements:

    • left_element
    • right_element
  • References

    • left_tree: nodes which their elements are less than left_element
    • middle_tree: nodes which their elements are between left_element and right_element
    • right_tree: nodes which theire elements are greater than right_element
template<typename Type>
class ThreeWayNode {
    private:
        Type left_element, right_element;
        ThreeWayNode *left_tree, *middle_tree, *right_tree;

    public:
        ThreeWayNode();

        bool isFull() const;

        // traversal methods
        void in_order_traversal();
        void pre_order_traversal();
        void post_order_traversal();

        void insert(Type);
};

Traversal

In-order traversal

Pre-order traversal

Post-order traversal

Multi way Node

template<typename Type, int N>
class MultiWayNode {
    private:
        Type elements[N];
        MultiWayNode *[N];

    public:
};

In [ ]: