Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
2-3-4 tree node class More...
Public Member Functions | |
Node (int64_t item) | |
Node constructor. | |
int8_t | GetCount () |
Get the item count that current saved in the node. | |
void | SetCount (int8_t c) |
Set the item count of the node. | |
bool | IsLeaf () |
Check if node is a leaf. | |
bool | IsFull () |
Check if node is a full (4-node) | |
bool | Is2Node () |
Check if node is a 2-node. | |
bool | Is34Node () |
Check if node is a 3-node or 4-node, this is useful when we delete item from 2-3-4 tree. | |
bool | Contains (int64_t item) |
Check if item is in the node. | |
int8_t | GetItemIndex (int64_t item) |
Get the index of the item in the node, 0-based. | |
int64_t | GetMaxItem () |
Get max item (rightmost) in the current node. | |
int64_t | GetMinItem () |
get min item (leftmost) in the current node | |
int64_t | GetItem (int8_t index) |
Get item of the \index index. | |
void | SetItem (int8_t index, int64_t new_item) |
Set item value at position of index. | |
int | InsertItem (int item) |
Insert item to the proper position of the node and return the position index. | |
void | InsertItemByIndex (int8_t index, int64_t item, Node *with_child, bool to_left=true) |
Insert a value to the index position. | |
Node * | RemoveItemByIndex (int8_t index, bool keep_left) |
Insert a value to the index position. | |
int8_t | GetChildIndex (Node *child) |
Get the child's index of the children array. | |
Node * | GetChild (int8_t index) |
Get the child pointer at position of index. | |
void | SetChild (int8_t index, Node *child) |
Set child pointer to the position of index. | |
Node * | GetRightmostChild () |
Get rightmose child of the current node. | |
Node * | GetLeftmostChild () |
Get leftmose child of the current node. | |
Node * | GetItemLeftChild (int8_t item_index) |
Get left child of item at item_index. | |
Node * | GetItemRightChild (int8_t item_index) |
Get right child of item at item_index. | |
Node * | GetNextPossibleChild (int64_t item) |
Get next node which is possibly contains item. | |
Private Attributes | |
std::array< int64_t, 3 > | items |
store items | |
std::array< Node *, 4 > | children |
store the children pointers | |
int8_t | count = 0 |
track the current item count | |
2-3-4 tree node class
|
inlineexplicit |
Node constructor.
item | the first value we insert to the node |
|
inline |
|
inline |
Get the child pointer at position of index.
index | index of child to get |
|
inline |
|
inline |
|
inline |
Get item of the \index index.
index | the item index to get |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Insert item to the proper position of the node and return the position index.
This is a helper function we use during insertion. Please mind that when insert a item, we aslo need to take care of two child pointers. One is the original child pointer at the insertion position. It can be placed as new item's either left child or right child. And the other is the new child that should be added. For our dedicated situation here, we choose to use the original child as the new item's left child, and add a null pointer to its right child. So after use the function, please update these two children pointer manually.
item | value to be inserted to the node |
|
inline |
Insert a value to the index position.
index | index where to insert item |
item | value to insert |
with_child | new added child pointer |
to_left | true indicate adding with_child to new item's left child, otherwise to right child |
|
inline |
|
inline |
|
inline |
Check if node is a full (4-node)
|
inline |
Check if node is a leaf.
|
inline |
Insert a value to the index position.
index | index of the item to remove |
keep_left | which child of the item to keep, true keep the left child, false keep the right child |
|
inline |
Set child pointer to the position of index.
index | children index |
child | pointer to set |
|
inline |
Set the item count of the node.
This is only used when we spliting and merging node where we need to do some raw operation manually. In common inserting and removing operation the count is maintained automatically.
c | the count to set |
|
inline |
Set item value at position of index.
index | the index of the item to set |
new_item | item value |