data_structures::tree_234::Tree234 Class Reference

2-3-4 tree class More...

Collaboration diagram for data_structures::tree_234::Tree234:

Public Member Functions
	Tree234 (const Tree234 &)=delete
	Tree234 (const Tree234 &&)=delete
Tree234 &	operator= (const Tree234 &)=delete
Tree234 &	operator= (const Tree234 &&)=delete
void	Insert (int64_t item)
	Insert item to tree. More...
bool	Remove (int64_t item)
	Remove item from tree. More...
void	Traverse ()
	In-order traverse. More...
void	Print (const char *file_name=nullptr)
	Print tree into a dot file. More...

Private Member Functions
void	InsertPreSplit (int64_t item)
	A insert implementation of pre-split. More...
void	InsertPostMerge (int64_t item)
	A insert implementation of post-merge. More...
Node *	Insert (Node *tree, int64_t item)
	A helper function used by post-merge insert. More...
Node *	MergeNode (Node *dst_node, Node *node)
	A helper function used during post-merge insert. More...
void	MergeNodeNotFull (Node *dst_node, Node *node)
	Merge node to a not-full target node. More...
Node *	SplitNode (Node *node)
	Split a 4-node to 1 parent and 2 children, and return the parent node. More...
int64_t	GetTreeMaxItem (Node *tree)
	Get the max item of the tree. More...
int64_t	GetTreeMinItem (Node *tree)
	Get the min item of the tree. More...
bool	TryLeftRotate (Node *parent, Node *to_child)
	A handy function to try if we can do a left rotate to the target node. More...
bool	TryRightRotate (Node *parent, Node *to_child)
	A handy function to try if we can do a right rotate to the target node. More...
void	RightRotate (Node *parent, int8_t index)
	Do the actual right rotate operation. More...
void	LeftRotate (Node *parent, int8_t index)
	Do the actual left rotate operation. More...
bool	RemovePreMerge (Node *node, int64_t item)
	Main function implement the pre-merge remove operation. More...
Node *	Merge (Node *parent, int8_t index)
	Merge the item at index of the parent node, and its left and right child. More...
void	DeleteNode (Node *tree)
	Recursive release the tree. More...
void	Traverse (Node *tree)
	In-order traverse the tree, print items. More...
void	PrintNode (std::ofstream &ofs, Node *node, int64_t parent_index, int64_t index, int8_t parent_child_index)
	Print the tree to a dot file. You can convert it to picture with graphviz. More...

Private Attributes
Node *	root_ {nullptr}
	root node of the tree

Detailed Description

2-3-4 tree class

Member Function Documentation

DeleteNode()

void data_structures::tree_234::Tree234::DeleteNode ( Node *  tree )

private

Recursive release the tree.

Parameters

tree	root node of the tree to delete

                                   {
    if (!tree) {
        return;
    }
    for (int8_t i = 0; i <= tree->GetCount(); i++) {
        DeleteNode(tree->GetChild(i));
    }
 
    delete tree;
}

Here is the call graph for this function:

GetTreeMaxItem()

int64_t data_structures::tree_234::Tree234::GetTreeMaxItem ( Node *  tree )

private

Get the max item of the tree.

Parameters

tree	the tree we will get item from

Returns

max item of the tree

                                          {
    assert(tree);
    int64_t max = 0;
 
    while (tree) {
        max = tree->GetMaxItem();
        tree = tree->GetRightmostChild();
    }
 
    return max;
}

Here is the call graph for this function:

GetTreeMinItem()

int64_t data_structures::tree_234::Tree234::GetTreeMinItem ( Node *  tree )

private

Get the min item of the tree.

Parameters

tree	the tree we will get item from

Returns

min item of the tree

                                          {
    assert(tree);
    int64_t min = 0;
 
    while (tree) {
        min = tree->GetMinItem();
        tree = tree->GetLeftmostChild();
    }
 
    return min;
}

Here is the call graph for this function:

Insert() [1/2]

void data_structures::tree_234::Tree234::Insert

(

int64_t

item

)

Insert item to tree.

Parameters

item	item to insert

{ InsertPreSplit(item); }

Here is the call graph for this function:

Insert() [2/2]

Node * data_structures::tree_234::Tree234::Insert ( Node *  tree, int64_t  item  )

private

A helper function used by post-merge insert.

Parameters

tree	tree where to insert item
item	item to insert

Returns

the node that split as the parent when overflow happen

                                              {
    assert(tree != nullptr);
 
    std::unique_ptr<Node> split_node;
 
    if (tree->Contains(item)) {
        // return nullptr indicate current node not overflow
        return nullptr;
    }
 
    Node *next_node = tree->GetNextPossibleChild(item);
    if (next_node) {
        split_node.reset(Insert(next_node, item));
    } else {
        split_node.reset(new Node(item));
    }
 
    if (split_node) {
        return MergeNode(tree, split_node.get());
    }
 
    return nullptr;
}

Here is the call graph for this function:

InsertPostMerge()

void data_structures::tree_234::Tree234::InsertPostMerge ( int64_t  item )

private

A insert implementation of post-merge.

Parameters

item	item to insert

                                          {
    if (!root_) {
        root_ = new Node(item);
        return;
    }
 
    Node *split_node = Insert(root_, item);
 
    // if root has split, then update root_
    if (split_node) {
        root_ = split_node;
    }
}

Here is the call graph for this function:

InsertPreSplit()

void data_structures::tree_234::Tree234::InsertPreSplit ( int64_t  item )

private

A insert implementation of pre-split.

Parameters

item	item to insert

                                         {
    if (!root_) {
        root_ = new Node(item);
        return;
    }
 
    Node *parent = nullptr;
    Node *node = root_;
 
    while (true) {
        if (!node) {
            std::unique_ptr<Node> tmp(new Node(item));
            MergeNodeNotFull(parent, tmp.get());
            return;
        }
 
        if (node->Contains(item)) {
            return;
        }
 
        if (node->IsFull()) {
            node = SplitNode(node);
 
            Node *cur_node = nullptr;
 
            if (item < node->GetItem(0)) {
                cur_node = node->GetChild(0);
            } else {
                cur_node = node->GetChild(1);
            }
 
            if (!parent) {
                // for the root node parent is nullptr, we simply assign the
                // split parent to root_
                root_ = node;
            } else {
                // merge the split parent to its origin parent
                MergeNodeNotFull(parent, node);
            }
 
            node = cur_node;
        }
 
        parent = node;
        node = parent->GetNextPossibleChild(item);
    }
}

LeftRotate()

void data_structures::tree_234::Tree234::LeftRotate ( Node *  parent, int8_t  index  )

private

Do the actual left rotate operation.

Given parent node, and the pivot item index, the left rotate operation is uniquely identified. The function assume the requirements are fulfilled and won't do any extra check. This function is call by TryLeftRotate(), and the condition checking should be done before call it.

Parameters

parent	the parent node in this right rotate operation
index	the pivot item index of this right rotate operation.

                                                   {
    Node *left = parent->GetItemLeftChild(index);
    Node *right = parent->GetItemRightChild(index);
 
    assert(right && right->Is34Node());
    assert(left && left->Is2Node());
 
    left->InsertItemByIndex(left->GetCount(), parent->GetItem(index),
                            right->GetLeftmostChild(), false);
    parent->SetItem(index, right->GetMinItem());
    right->RemoveItemByIndex(0, false);
}

Merge()

Node * data_structures::tree_234::Tree234::Merge ( Node *  parent, int8_t  index  )

private

Merge the item at index of the parent node, and its left and right child.

the left and right child node must be 2-node. The 3 items will be merged into a 4-node. In our case the parent can be a 2-node iff it is the root. Otherwise, it must be 3-node or 4-node.

Parameters

parent	the parent node in the merging operation
index	the item index of the parent node that involved in the merging

Returns

the merged 4-node

                                               {
    assert(parent);
 
    // bool is_parent_2node = parent->Is2Node();
 
    Node *left_child = parent->GetItemLeftChild(index);
    Node *right_child = parent->GetItemRightChild(index);
 
    assert(left_child->Is2Node() && right_child->Is2Node());
 
    int64_t item = parent->GetItem(index);
 
    // 1. merge parent's item and right child to left child
    left_child->SetItem(1, item);
    left_child->SetItem(2, right_child->GetItem(0));
    left_child->SetChild(2, right_child->GetChild(0));
    left_child->SetChild(3, right_child->GetChild(1));
 
    left_child->SetCount(3);
 
    // 2. remove the parent's item
    parent->RemoveItemByIndex(index, true);
 
    // 3. delete the unused right child
    delete right_child;
 
    return left_child;
}

MergeNode()

Node * data_structures::tree_234::Tree234::MergeNode ( Node *  dst_node, Node *  node  )

private

A helper function used during post-merge insert.

When the inserting leads to overflow, it will split the node to 1 parent and 2 children. The parent will be merged to its origin parent after that. This is the function to complete this task. So the param node is always a 2-node.

Parameters

dst_node	the target node we will merge node to, can be type of 2-node, 3-node or 4-node
node	the source node we will merge from, type must be 2-node

Returns

overflow node of this level

                                                   {
    assert(dst_node != nullptr && node != nullptr);
 
    if (!dst_node->IsFull()) {
        MergeNodeNotFull(dst_node, node);
        return nullptr;
    }
 
    dst_node = SplitNode(dst_node);
 
    if (node->GetItem(0) < dst_node->GetItem(0)) {
        MergeNodeNotFull(dst_node->GetChild(0), node);
 
    } else {
        MergeNodeNotFull(dst_node->GetChild(1), node);
    }
 
    return dst_node;
}

Here is the call graph for this function:

MergeNodeNotFull()

void data_structures::tree_234::Tree234::MergeNodeNotFull ( Node *  dst_node, Node *  node  )

private

Merge node to a not-full target node.

Since the target node is not-full, no overflow will happen. So we have nothing to return.

Parameters

dst_node	the target not-full node, that is the type is either 2-node or 3-node, but not 4-node
node	the source node we will merge from, type must be 2-node

                                                         {
    assert(dst_node && node && !dst_node->IsFull() && node->Is2Node());
 
    int8_t i = dst_node->InsertItem(node->GetItem(0));
 
    dst_node->SetChild(i, node->GetChild(0));
    dst_node->SetChild(i + 1, node->GetChild(1));
}

Here is the call graph for this function:

Print()

void data_structures::tree_234::Tree234::Print

(

const char *

file_name = nullptr

)

Print tree into a dot file.

Parameters

file_name

output file name, if nullptr then use "out.dot" as default

This is a helper structure to do a level order traversal to print the tree.

< tree node

< node index of level order that used when draw the link between child and parent

                                         {
    if (!file_name) {
        file_name = "out.dot";
    }
 
    std::ofstream ofs;
 
    ofs.open(file_name);
    if (!ofs) {
        std::cout << "create tree dot file failed, " << file_name << std::endl;
        return;
    }
 
    ofs << "digraph G {\n";
    ofs << "node [shape=record]\n";
 
    int64_t index = 0;
 
    /** @brief This is a helper structure to do a level order traversal to print
     * the tree. */
    struct NodeInfo {
        Node *node;     ///< tree node
        int64_t index;  ///< node index of level order that used when draw the
                        ///< link between child and parent
    };
 
    std::queue<NodeInfo> q;
 
    if (root_) {
        // print root node
        PrintNode(ofs, root_, -1, index, 0);
 
        NodeInfo ni{};
        ni.node = root_;
        ni.index = index;
 
        q.push(ni);
 
        while (!q.empty()) {
            NodeInfo node_info = q.front();
            q.pop();
 
            assert(node_info.node->GetCount() > 0);
 
            if (!node_info.node->IsLeaf()) {
                if (node_info.node->GetCount() > 0) {
                    PrintNode(ofs, node_info.node->GetChild(0), node_info.index,
                              ++index, 0);
                    ni.node = node_info.node->GetChild(0);
                    ni.index = index;
                    q.push(ni);
 
                    PrintNode(ofs, node_info.node->GetChild(1), node_info.index,
                              ++index, 1);
                    ni.node = node_info.node->GetChild(1);
                    ni.index = index;
                    q.push(ni);
                }
 
                if (node_info.node->GetCount() > 1) {
                    PrintNode(ofs, node_info.node->GetChild(2), node_info.index,
                              ++index, 2);
                    ni.node = node_info.node->GetChild(2);
                    ni.index = index;
                    q.push(ni);
                }
 
                if (node_info.node->GetCount() > 2) {
                    PrintNode(ofs, node_info.node->GetChild(3), node_info.index,
                              ++index, 3);
                    ni.node = node_info.node->GetChild(3);
                    ni.index = index;
                    q.push(ni);
                }
            }
        }
    }
 
    ofs << "}\n";
    ofs.close();
}

Here is the call graph for this function:

PrintNode()

void data_structures::tree_234::Tree234::PrintNode ( std::ofstream &  ofs, Node *  node, int64_t  parent_index, int64_t  index, int8_t  parent_child_index  )

private

Print the tree to a dot file. You can convert it to picture with graphviz.

Parameters

ofs	output file stream to print to
node	current node to print
parent_index	current node's parent node index, this is used to draw the link from parent to current node
index	current node's index of level order which is used to name the node in dot file
parent_child_index	the index that current node in parent's children array, range in [0,4), help to locate the start position of the link between nodes

                                                                  {
    assert(node);
 
    switch (node->GetCount()) {
        case 1:
            ofs << "node_" << index << " [label=\"<f0> " << node->GetItem(0)
                << "\"]\n";
            break;
        case 2:
            ofs << "node_" << index << " [label=\"<f0> " << node->GetItem(0)
                << " | <f1> " << node->GetItem(1) << "\"]\n";
            break;
        case 3:
            ofs << "node_" << index << " [label=\"<f0> " << node->GetItem(0)
                << " | <f1> " << node->GetItem(1) << "| <f2> "
                << node->GetItem(2) << "\"]\n";
            break;
 
        default:
            break;
    }
 
    // draw the edge
    if (parent_index >= 0) {
        ofs << "node_" << parent_index << ":f"
            << (parent_child_index == 0 ? 0 : parent_child_index - 1) << ":"
            << (parent_child_index == 0 ? "sw" : "se") << " -> node_" << index
            << "\n";
    }
}

Remove()

bool data_structures::tree_234::Tree234::Remove

(

int64_t

item

)

Remove item from tree.

Parameters

item	item to remove

Returns

true if item found and removed, false otherwise

{ return RemovePreMerge(root_, item); }

Here is the call graph for this function:

RemovePreMerge()

bool data_structures::tree_234::Tree234::RemovePreMerge ( Node *  node, int64_t  item  )

private

Main function implement the pre-merge remove operation.

Parameters

node	the tree to remove item from
item	item to remove

Returns

true if remove success, false otherwise

                                                     {
    while (node) {
        if (node->IsLeaf()) {
            if (node->Contains(item)) {
                if (node->Is2Node()) {
                    // node must be root
                    delete node;
                    root_ = nullptr;
                } else {
                    node->RemoveItemByIndex(node->GetItemIndex(item), true);
                }
                return true;
            }
            return false;
        }
 
        // node is internal
        if (node->Contains(item)) {
            int8_t index = node->GetItemIndex(item);
 
            // Here is important!!! What we do next depend on its children's
            // state. Why?
            Node *left_child = node->GetItemLeftChild(index);
            Node *right_child = node->GetItemRightChild(index);
            assert(left_child && right_child);
 
            if (left_child->Is2Node() && right_child->Is2Node()) {
                // both left and right child are 2-node,we should not modify
                // current node in this situation. Because we are going to do
                // merge with its children which will move target item to next
                // layer. so if we replace the item with successor or
                // predecessor now, when we do the recursive remove with
                // successor or predecessor, we will result in removing the just
                // replaced one in the merged node. That's not what we want.
 
                // we need to convert the child 2-node to 3-node or 4-node
                // first. First we try to see if any of them can convert to
                // 3-node by rotate. By using rotate we keep the empty house for
                // the future insertion which will be more efficient than merge.
                //
                //            | ? | node | ? |
                //           /    |      |    \
                //          /     |      |     \
                //         /      |      |      \
                //        /       |      |       \
                //       /        |      |        \
                //      /         |      |         \
                //     ?  left_child  right_child   ?
                //
 
                // node must be the root
                if (node->Is2Node()) {
                    // this means we can't avoid merging the target item into
                    // next layer, and this will cause us do different process
                    // compared with other cases
                    Node *new_root = Merge(node, index);
                    delete root_;
                    root_ = new_root;
                    node = root_;
 
                    // now node point to the
                    continue;
                }
 
                // here means we can avoid merging the target item into next
                // layer. So we convert one of its left or right child to 3-node
                // and then do the successor or predecessor swap and recursive
                // remove the next layer will successor or predecessor.
                do {
                    if (index > 0) {
                        // left_child has left-sibling, we check if we can do a
                        // rotate
                        Node *left_sibling = node->GetItemLeftChild(index - 1);
                        if (left_sibling->Is34Node()) {
                            RightRotate(node, index - 1);
                            break;
                        }
                    }
 
                    if (index < node->GetCount() - 1) {
                        // right_child has right-sibling, we check if we can do
                        // a rotate
                        Node *right_sibling =
                            node->GetItemRightChild(index + 1);
                        if (right_sibling->Is34Node()) {
                            LeftRotate(node, index + 1);
                            break;
                        }
                    }
 
                    // we do a merge. We avoid merging the target item, which
                    // may trigger another merge in the recursion process.
                    if (index > 0) {
                        Merge(node, index - 1);
                        break;
                    }
 
                    Merge(node, index + 1);
 
                } while (false);
            }
 
            // refresh the left_child and right_child since they may be invalid
            // because of merge
            left_child = node->GetItemLeftChild(index);
            right_child = node->GetItemRightChild(index);
 
            if (left_child->Is34Node()) {
                int64_t predecessor_item = GetTreeMaxItem(left_child);
                node->SetItem(node->GetItemIndex(item), predecessor_item);
 
                node = left_child;
                item = predecessor_item;
                continue;
            }
 
            if (right_child->Is34Node()) {
                int64_t successor_item = GetTreeMinItem(right_child);
                node->SetItem(node->GetItemIndex(item), successor_item);
                node = right_child;
                item = successor_item;
                continue;
            }
        }
 
        Node *next_node = node->GetNextPossibleChild(item);
 
        if (next_node->Is34Node()) {
            node = next_node;
            continue;
        }
 
        if (TryRightRotate(node, next_node)) {
            node = next_node;
            continue;
        }
 
        if (TryLeftRotate(node, next_node)) {
            node = next_node;
            continue;
        }
 
        // get here means both left sibling and right sibling of next_node is
        // 2-node, so we do merge
        int8_t child_index = node->GetChildIndex(next_node);
        if (child_index > 0) {
            node = Merge(node, child_index - 1);
        } else {
            node = Merge(node, child_index);
        }
 
    }  // while
 
    return false;
}

Here is the call graph for this function:

RightRotate()

void data_structures::tree_234::Tree234::RightRotate ( Node *  parent, int8_t  index  )

private

Do the actual right rotate operation.

Given parent node, and the pivot item index, the right rotate operation is uniquely identified. The function assume the requirements are fulfilled and won't do any extra check. This function is call by TryRightRotate(), and the condition checking should be done before call it.

Parameters

parent	the parent node in this right rotate operation
index	the pivot item index of this right rotate operation.

                                                    {
    Node *left = parent->GetItemLeftChild(index);
    Node *right = parent->GetItemRightChild(index);
 
    assert(left && left->Is34Node());
    assert(right && right->Is2Node());
 
    right->InsertItemByIndex(0, parent->GetItem(index),
                             left->GetRightmostChild(), true);
    parent->SetItem(index, left->GetMaxItem());
    left->RemoveItemByIndex(left->GetCount() - 1, true);
}

SplitNode()

Node * data_structures::tree_234::Tree234::SplitNode ( Node *  node )

private

Split a 4-node to 1 parent and 2 children, and return the parent node.

Parameters

node	the node to split, it must be a 4-node

Returns

split parent node

                                   {
    assert(node->GetCount() == 3);
 
    Node *left = node;
 
    Node *right = new Node(node->GetItem(2));
    right->SetChild(0, node->GetChild(2));
    right->SetChild(1, node->GetChild(3));
 
    Node *parent = new Node(node->GetItem(1));
    parent->SetChild(0, left);
    parent->SetChild(1, right);
 
    left->SetCount(1);
 
    return parent;
}

Traverse() [1/2]

void data_structures::tree_234::Tree234::Traverse

(

)

In-order traverse.

In-order traverse the tree, print items.

Parameters

tree	tree to traverse

                       {
    Traverse(root_);
    std::cout << std::endl;
}

Here is the call graph for this function:

Traverse() [2/2]

void data_structures::tree_234::Tree234::Traverse ( Node *  tree )

private

In-order traverse the tree, print items.

Parameters

tree	tree to traverse

                                 {
    if (!node) {
        return;
    }
 
    int8_t i = 0;
    for (i = 0; i < node->GetCount(); i++) {
        Traverse(node->GetChild(i));
        std::cout << node->GetItem(i) << ", ";
    }
 
    Traverse(node->GetChild(i));
}

Here is the call graph for this function:

TryLeftRotate()

bool data_structures::tree_234::Tree234::TryLeftRotate ( Node *  parent, Node *  to_child  )

private

A handy function to try if we can do a left rotate to the target node.

Given two node, the parent and the target child, the left rotate operation is uniquely identified. The source node must be the right sibling of the target child. The operation can be successfully done if the to_child has a right sibling and its right sibling is not 2-node.

Parameters

parent	the parent node in this left rotate operation
to_child	the target child of this left rotate operation. In our case, this node is always 2-node

Returns

true if we successfully do the rotate. false if the requirements are not fulfilled.

                                                        {
    int to_child_index = parent->GetChildIndex(to_child);
 
    // child is right most, can not do left rotate to it
    if (to_child_index >= parent->GetCount()) {
        return false;
    }
 
    Node *right_sibling = parent->GetChild(to_child_index + 1);
 
    // right sibling is 2-node. can not do left rotate.
    if (right_sibling->Is2Node()) {
        return false;
    }
 
    LeftRotate(parent, to_child_index);
 
    return true;
}

TryRightRotate()

bool data_structures::tree_234::Tree234::TryRightRotate ( Node *  parent, Node *  to_child  )

private

A handy function to try if we can do a right rotate to the target node.

Given two node, the parent and the target child, the right rotate operation is uniquely identified. The source node must be the left sibling of the target child. The operation can be successfully done if the to_child has a left sibling and its left sibling is not 2-node.

Parameters

parent	the parent node in this right rotate operation
to_child	the target child of this right rotate operation. In our case, it is always 2-node

Returns

true if we successfully do the rotate. false if the requirements are not fulfilled.

                                                         {
    int8_t to_child_index = parent->GetChildIndex(to_child);
 
    // child is left most, can not do right rotate to it
    if (to_child_index <= 0) {
        return false;
    }
 
    Node *left_sibling = parent->GetChild(to_child_index - 1);
 
    // right sibling is 2-node. can not do left rotate.
    if (left_sibling->Is2Node()) {
        return false;
    }
 
    RightRotate(parent, to_child_index - 1);
 
    return true;
}

---

The documentation for this class was generated from the following file:

• data_structures/tree_234.cpp