Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
2-3-4 tree class More...
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. | |
bool | Remove (int64_t item) |
Remove item from tree. | |
void | Traverse () |
In-order traverse. | |
void | Print (const char *file_name=nullptr) |
Print tree into a dot file. | |
Private Member Functions | |
void | InsertPreSplit (int64_t item) |
A insert implementation of pre-split. | |
void | InsertPostMerge (int64_t item) |
A insert implementation of post-merge. | |
Node * | Insert (Node *tree, int64_t item) |
A helper function used by post-merge insert. | |
Node * | MergeNode (Node *dst_node, Node *node) |
A helper function used during post-merge insert. | |
void | MergeNodeNotFull (Node *dst_node, Node *node) |
Merge node to a not-full target node. | |
Node * | SplitNode (Node *node) |
Split a 4-node to 1 parent and 2 children, and return the parent node. | |
int64_t | GetTreeMaxItem (Node *tree) |
Get the max item of the tree. | |
int64_t | GetTreeMinItem (Node *tree) |
Get the min item of the tree. | |
bool | TryLeftRotate (Node *parent, Node *to_child) |
A handy function to try if we can do a left rotate to the target node. | |
bool | TryRightRotate (Node *parent, Node *to_child) |
A handy function to try if we can do a right rotate to the target node. | |
void | RightRotate (Node *parent, int8_t index) |
Do the actual right rotate operation. | |
void | LeftRotate (Node *parent, int8_t index) |
Do the actual left rotate operation. | |
bool | RemovePreMerge (Node *node, int64_t item) |
Main function implement the pre-merge remove operation. | |
Node * | Merge (Node *parent, int8_t index) |
Merge the item at index of the parent node, and its left and right child. | |
void | DeleteNode (Node *tree) |
Recursive release the tree. | |
void | Traverse (Node *tree) |
In-order traverse the tree, print items. | |
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. | |
Private Attributes | |
Node * | root_ {nullptr} |
root node of the tree | |
2-3-4 tree class
data_structures::tree_234::Tree234::~Tree234 | ( | ) |
|
private |
Recursive release the tree.
tree | root node of the tree to delete |
|
private |
Get the max item of the tree.
tree | the tree we will get item from |
|
private |
Get the min item of the tree.
tree | the tree we will get item from |
void data_structures::tree_234::Tree234::Insert | ( | int64_t | item | ) |
Insert item to tree.
item | item to insert |
A helper function used by post-merge insert.
tree | tree where to insert item |
item | item to insert |
|
private |
A insert implementation of post-merge.
item | item to insert |
|
private |
A insert implementation of pre-split.
item | item to insert |
|
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.
parent | the parent node in this right rotate operation |
index | the pivot item index of this right rotate operation. |
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.
parent | the parent node in the merging operation |
index | the item index of the parent node that involved in the merging |
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.
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 |
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.
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 |
void data_structures::tree_234::Tree234::Print | ( | const char * | file_name = nullptr | ) |
Print tree into a dot file.
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
|
private |
Print the tree to a dot file. You can convert it to picture with graphviz.
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 |
bool data_structures::tree_234::Tree234::Remove | ( | int64_t | item | ) |
Remove item from tree.
item | item to remove |
|
private |
Main function implement the pre-merge remove operation.
node | the tree to remove item from |
item | item to remove |
|
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.
parent | the parent node in this right rotate operation |
index | the pivot item index of this right rotate operation. |
Split a 4-node to 1 parent and 2 children, and return the parent node.
node | the node to split, it must be a 4-node |
void data_structures::tree_234::Tree234::Traverse | ( | ) |
In-order traverse.
In-order traverse the tree, print items.
tree | tree to traverse |
|
private |
In-order traverse the tree, print items.
tree | tree to traverse |
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.
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 |
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.
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 |
|
private |
root node of the tree