TheAlgorithms/C++ 1.0.0
All the 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
Definition at line 323 of file tree_234.cpp.
data_structures::tree_234::Tree234::~Tree234 | ( | ) |
Definition at line 541 of file tree_234.cpp.
|
private |
Recursive release the tree.
tree | root node of the tree to delete |
Definition at line 547 of file tree_234.cpp.
|
private |
Get the max item of the tree.
tree | the tree we will get item from |
Definition at line 1098 of file tree_234.cpp.
|
private |
Get the min item of the tree.
tree | the tree we will get item from |
Definition at line 1115 of file tree_234.cpp.
void data_structures::tree_234::Tree234::Insert | ( | int64_t | item | ) |
Insert item to tree.
item | item to insert |
Definition at line 655 of file tree_234.cpp.
A helper function used by post-merge insert.
tree | tree where to insert item |
item | item to insert |
Definition at line 663 of file tree_234.cpp.
|
private |
A insert implementation of post-merge.
item | item to insert |
Definition at line 637 of file tree_234.cpp.
|
private |
A insert implementation of pre-split.
item | item to insert |
Definition at line 585 of file tree_234.cpp.
|
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. |
Definition at line 869 of file tree_234.cpp.
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 |
Definition at line 895 of file tree_234.cpp.
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 |
Definition at line 700 of file tree_234.cpp.
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 |
Definition at line 730 of file tree_234.cpp.
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
Definition at line 1131 of file tree_234.cpp.
|
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 |
Definition at line 1226 of file tree_234.cpp.
bool data_structures::tree_234::Tree234::Remove | ( | int64_t | item | ) |
Remove item from tree.
item | item to remove |
Definition at line 929 of file tree_234.cpp.
|
private |
Main function implement the pre-merge remove operation.
node | the tree to remove item from |
item | item to remove |
Definition at line 937 of file tree_234.cpp.
|
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. |
Definition at line 845 of file tree_234.cpp.
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 |
Definition at line 745 of file tree_234.cpp.
void data_structures::tree_234::Tree234::Traverse | ( | ) |
In-order traverse.
In-order traverse the tree, print items.
tree | tree to traverse |
Definition at line 562 of file tree_234.cpp.
|
private |
In-order traverse the tree, print items.
tree | tree to traverse |
Definition at line 567 of file tree_234.cpp.
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 |
Definition at line 778 of file tree_234.cpp.
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 |
Definition at line 813 of file tree_234.cpp.
|
private |