Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
data_structures::tree_234::Tree234 Class Reference

2-3-4 tree class More...

Collaboration diagram for data_structures::tree_234::Tree234:
[legend]

Public Member Functions

 Tree234 (const Tree234 &)=delete
 
 Tree234 (const Tree234 &&)=delete
 
Tree234operator= (const Tree234 &)=delete
 
Tree234operator= (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.
 
NodeInsert (Node *tree, int64_t item)
 A helper function used by post-merge insert.
 
NodeMergeNode (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.
 
NodeSplitNode (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.
 
NodeMerge (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

Noderoot_ {nullptr}
 root node of the tree
 

Detailed Description

2-3-4 tree class

Constructor & Destructor Documentation

◆ ~Tree234()

data_structures::tree_234::Tree234::~Tree234 ( )
541{ DeleteNode(root_); }
void DeleteNode(Node *tree)
Recursive release the tree.
Definition tree_234.cpp:547
Node * root_
root node of the tree
Definition tree_234.cpp:538

Member Function Documentation

◆ DeleteNode()

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

Recursive release the tree.

Parameters
treeroot node of the tree to delete
547 {
548 if (!tree) {
549 return;
550 }
551 for (int8_t i = 0; i <= tree->GetCount(); i++) {
552 DeleteNode(tree->GetChild(i));
553 }
554
555 delete tree;
556}
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
treethe tree we will get item from
Returns
max item of the tree
1098 {
1099 assert(tree);
1100 int64_t max = 0;
1101
1102 while (tree) {
1103 max = tree->GetMaxItem();
1104 tree = tree->GetRightmostChild();
1105 }
1106
1107 return max;
1108}
T max(T... args)
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
treethe tree we will get item from
Returns
min item of the tree
1115 {
1116 assert(tree);
1117 int64_t min = 0;
1118
1119 while (tree) {
1120 min = tree->GetMinItem();
1121 tree = tree->GetLeftmostChild();
1122 }
1123
1124 return min;
1125}
T min(T... args)
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
itemitem to insert
655{ InsertPreSplit(item); }
void InsertPreSplit(int64_t item)
A insert implementation of pre-split.
Definition tree_234.cpp:585
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
treetree where to insert item
itemitem to insert
Returns
the node that split as the parent when overflow happen
663 {
664 assert(tree != nullptr);
665
666 std::unique_ptr<Node> split_node;
667
668 if (tree->Contains(item)) {
669 // return nullptr indicate current node not overflow
670 return nullptr;
671 }
672
673 Node *next_node = tree->GetNextPossibleChild(item);
674 if (next_node) {
675 split_node.reset(Insert(next_node, item));
676 } else {
677 split_node.reset(new Node(item));
678 }
679
680 if (split_node) {
681 return MergeNode(tree, split_node.get());
682 }
683
684 return nullptr;
685}
Node * MergeNode(Node *dst_node, Node *node)
A helper function used during post-merge insert.
Definition tree_234.cpp:700
void Insert(int64_t item)
Insert item to tree.
Definition tree_234.cpp:655
T get(T... args)
T reset(T... args)
Definition linkedlist_implentation_usingarray.cpp:14
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
itemitem to insert
637 {
638 if (!root_) {
639 root_ = new Node(item);
640 return;
641 }
642
643 Node *split_node = Insert(root_, item);
644
645 // if root has split, then update root_
646 if (split_node) {
647 root_ = split_node;
648 }
649}
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
itemitem to insert
585 {
586 if (!root_) {
587 root_ = new Node(item);
588 return;
589 }
590
591 Node *parent = nullptr;
592 Node *node = root_;
593
594 while (true) {
595 if (!node) {
596 std::unique_ptr<Node> tmp(new Node(item));
597 MergeNodeNotFull(parent, tmp.get());
598 return;
599 }
600
601 if (node->Contains(item)) {
602 return;
603 }
604
605 if (node->IsFull()) {
607
608 Node *cur_node = nullptr;
609
610 if (item < node->GetItem(0)) {
611 cur_node = node->GetChild(0);
612 } else {
613 cur_node = node->GetChild(1);
614 }
615
616 if (!parent) {
617 // for the root node parent is nullptr, we simply assign the
618 // split parent to root_
619 root_ = node;
620 } else {
621 // merge the split parent to its origin parent
622 MergeNodeNotFull(parent, node);
623 }
624
625 node = cur_node;
626 }
627
628 parent = node;
629 node = parent->GetNextPossibleChild(item);
630 }
631}
struct node { int data; int height; struct node *left; struct node *right;} node
for std::queue
Definition avltree.cpp:13
Node * SplitNode(Node *node)
Split a 4-node to 1 parent and 2 children, and return the parent node.
Definition tree_234.cpp:745
void MergeNodeNotFull(Node *dst_node, Node *node)
Merge node to a not-full target node.
Definition tree_234.cpp:730
Definition binary_search_tree.cpp:11
Here is the call graph for this function:

◆ 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
parentthe parent node in this right rotate operation
indexthe pivot item index of this right rotate operation.
869 {
870 Node *left = parent->GetItemLeftChild(index);
871 Node *right = parent->GetItemRightChild(index);
872
873 assert(right && right->Is34Node());
874 assert(left && left->Is2Node());
875
876 left->InsertItemByIndex(left->GetCount(), parent->GetItem(index),
877 right->GetLeftmostChild(), false);
878 parent->SetItem(index, right->GetMinItem());
879 right->RemoveItemByIndex(0, false);
880}
T right(T... args)

◆ 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
parentthe parent node in the merging operation
indexthe item index of the parent node that involved in the merging
Returns
the merged 4-node
895 {
896 assert(parent);
897
898 // bool is_parent_2node = parent->Is2Node();
899
900 Node *left_child = parent->GetItemLeftChild(index);
901 Node *right_child = parent->GetItemRightChild(index);
902
903 assert(left_child->Is2Node() && right_child->Is2Node());
904
905 int64_t item = parent->GetItem(index);
906
907 // 1. merge parent's item and right child to left child
908 left_child->SetItem(1, item);
909 left_child->SetItem(2, right_child->GetItem(0));
910 left_child->SetChild(2, right_child->GetChild(0));
911 left_child->SetChild(3, right_child->GetChild(1));
912
913 left_child->SetCount(3);
914
915 // 2. remove the parent's item
916 parent->RemoveItemByIndex(index, true);
917
918 // 3. delete the unused right child
919 delete right_child;
920
921 return left_child;
922}
Here is the call graph for this function:

◆ 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_nodethe target node we will merge node to, can be type of 2-node, 3-node or 4-node
nodethe source node we will merge from, type must be 2-node
Returns
overflow node of this level
700 {
701 assert(dst_node != nullptr && node != nullptr);
702
703 if (!dst_node->IsFull()) {
704 MergeNodeNotFull(dst_node, node);
705 return nullptr;
706 }
707
708 dst_node = SplitNode(dst_node);
709
710 if (node->GetItem(0) < dst_node->GetItem(0)) {
711 MergeNodeNotFull(dst_node->GetChild(0), node);
712
713 } else {
714 MergeNodeNotFull(dst_node->GetChild(1), node);
715 }
716
717 return dst_node;
718}
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_nodethe target not-full node, that is the type is either 2-node or 3-node, but not 4-node
nodethe source node we will merge from, type must be 2-node
730 {
731 assert(dst_node && node && !dst_node->IsFull() && node->Is2Node());
732
733 int8_t i = dst_node->InsertItem(node->GetItem(0));
734
735 dst_node->SetChild(i, node->GetChild(0));
736 dst_node->SetChild(i + 1, node->GetChild(1));
737}
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_nameoutput 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

1131 {
1132 if (!file_name) {
1133 file_name = "out.dot";
1134 }
1135
1136 std::ofstream ofs;
1137
1138 ofs.open(file_name);
1139 if (!ofs) {
1140 std::cout << "create tree dot file failed, " << file_name << std::endl;
1141 return;
1142 }
1143
1144 ofs << "digraph G {\n";
1145 ofs << "node [shape=record]\n";
1146
1147 int64_t index = 0;
1148
1149 /** @brief This is a helper structure to do a level order traversal to print
1150 * the tree. */
1151 struct NodeInfo {
1152 Node *node; ///< tree node
1153 int64_t index; ///< node index of level order that used when draw the
1154 ///< link between child and parent
1155 };
1156
1158
1159 if (root_) {
1160 // print root node
1161 PrintNode(ofs, root_, -1, index, 0);
1162
1163 NodeInfo ni{};
1164 ni.node = root_;
1165 ni.index = index;
1166
1167 q.push(ni);
1168
1169 while (!q.empty()) {
1170 NodeInfo node_info = q.front();
1171 q.pop();
1172
1173 assert(node_info.node->GetCount() > 0);
1174
1175 if (!node_info.node->IsLeaf()) {
1176 if (node_info.node->GetCount() > 0) {
1177 PrintNode(ofs, node_info.node->GetChild(0), node_info.index,
1178 ++index, 0);
1179 ni.node = node_info.node->GetChild(0);
1180 ni.index = index;
1181 q.push(ni);
1182
1183 PrintNode(ofs, node_info.node->GetChild(1), node_info.index,
1184 ++index, 1);
1185 ni.node = node_info.node->GetChild(1);
1186 ni.index = index;
1187 q.push(ni);
1188 }
1189
1190 if (node_info.node->GetCount() > 1) {
1191 PrintNode(ofs, node_info.node->GetChild(2), node_info.index,
1192 ++index, 2);
1193 ni.node = node_info.node->GetChild(2);
1194 ni.index = index;
1195 q.push(ni);
1196 }
1197
1198 if (node_info.node->GetCount() > 2) {
1199 PrintNode(ofs, node_info.node->GetChild(3), node_info.index,
1200 ++index, 3);
1201 ni.node = node_info.node->GetChild(3);
1202 ni.index = index;
1203 q.push(ni);
1204 }
1205 }
1206 }
1207 }
1208
1209 ofs << "}\n";
1210 ofs.close();
1211}
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.
Definition tree_234.cpp:1226
T close(T... args)
T endl(T... args)
T open(T... args)
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
ofsoutput file stream to print to
nodecurrent node to print
parent_indexcurrent node's parent node index, this is used to draw the link from parent to current node
indexcurrent node's index of level order which is used to name the node in dot file
parent_child_indexthe index that current node in parent's children array, range in [0,4), help to locate the start position of the link between nodes
1227 {
1228 assert(node);
1229
1230 switch (node->GetCount()) {
1231 case 1:
1232 ofs << "node_" << index << " [label=\"<f0> " << node->GetItem(0)
1233 << "\"]\n";
1234 break;
1235 case 2:
1236 ofs << "node_" << index << " [label=\"<f0> " << node->GetItem(0)
1237 << " | <f1> " << node->GetItem(1) << "\"]\n";
1238 break;
1239 case 3:
1240 ofs << "node_" << index << " [label=\"<f0> " << node->GetItem(0)
1241 << " | <f1> " << node->GetItem(1) << "| <f2> "
1242 << node->GetItem(2) << "\"]\n";
1243 break;
1244
1245 default:
1246 break;
1247 }
1248
1249 // draw the edge
1250 if (parent_index >= 0) {
1251 ofs << "node_" << parent_index << ":f"
1252 << (parent_child_index == 0 ? 0 : parent_child_index - 1) << ":"
1253 << (parent_child_index == 0 ? "sw" : "se") << " -> node_" << index
1254 << "\n";
1255 }
1256}

◆ Remove()

bool data_structures::tree_234::Tree234::Remove ( int64_t item)

Remove item from tree.

Parameters
itemitem to remove
Returns
true if item found and removed, false otherwise
929{ return RemovePreMerge(root_, item); }
bool RemovePreMerge(Node *node, int64_t item)
Main function implement the pre-merge remove operation.
Definition tree_234.cpp:937
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
nodethe tree to remove item from
itemitem to remove
Returns
true if remove success, false otherwise
937 {
938 while (node) {
939 if (node->IsLeaf()) {
940 if (node->Contains(item)) {
941 if (node->Is2Node()) {
942 // node must be root
943 delete node;
944 root_ = nullptr;
945 } else {
946 node->RemoveItemByIndex(node->GetItemIndex(item), true);
947 }
948 return true;
949 }
950 return false;
951 }
952
953 // node is internal
954 if (node->Contains(item)) {
955 int8_t index = node->GetItemIndex(item);
956
957 // Here is important!!! What we do next depend on its children's
958 // state. Why?
959 Node *left_child = node->GetItemLeftChild(index);
960 Node *right_child = node->GetItemRightChild(index);
961 assert(left_child && right_child);
962
963 if (left_child->Is2Node() && right_child->Is2Node()) {
964 // both left and right child are 2-node,we should not modify
965 // current node in this situation. Because we are going to do
966 // merge with its children which will move target item to next
967 // layer. so if we replace the item with successor or
968 // predecessor now, when we do the recursive remove with
969 // successor or predecessor, we will result in removing the just
970 // replaced one in the merged node. That's not what we want.
971
972 // we need to convert the child 2-node to 3-node or 4-node
973 // first. First we try to see if any of them can convert to
974 // 3-node by rotate. By using rotate we keep the empty house for
975 // the future insertion which will be more efficient than merge.
976 //
977 // | ? | node | ? |
978 // / | | \
979 // / | | \
980 // / | | \
981 // / | | \
982 // / | | \
983 // / | | \
984 // ? left_child right_child ?
985 //
986
987 // node must be the root
988 if (node->Is2Node()) {
989 // this means we can't avoid merging the target item into
990 // next layer, and this will cause us do different process
991 // compared with other cases
992 Node *new_root = Merge(node, index);
993 delete root_;
994 root_ = new_root;
995 node = root_;
996
997 // now node point to the
998 continue;
999 }
1000
1001 // here means we can avoid merging the target item into next
1002 // layer. So we convert one of its left or right child to 3-node
1003 // and then do the successor or predecessor swap and recursive
1004 // remove the next layer will successor or predecessor.
1005 do {
1006 if (index > 0) {
1007 // left_child has left-sibling, we check if we can do a
1008 // rotate
1009 Node *left_sibling = node->GetItemLeftChild(index - 1);
1010 if (left_sibling->Is34Node()) {
1011 RightRotate(node, index - 1);
1012 break;
1013 }
1014 }
1015
1016 if (index < node->GetCount() - 1) {
1017 // right_child has right-sibling, we check if we can do
1018 // a rotate
1019 Node *right_sibling =
1020 node->GetItemRightChild(index + 1);
1021 if (right_sibling->Is34Node()) {
1022 LeftRotate(node, index + 1);
1023 break;
1024 }
1025 }
1026
1027 // we do a merge. We avoid merging the target item, which
1028 // may trigger another merge in the recursion process.
1029 if (index > 0) {
1030 Merge(node, index - 1);
1031 break;
1032 }
1033
1034 Merge(node, index + 1);
1035
1036 } while (false);
1037 }
1038
1039 // refresh the left_child and right_child since they may be invalid
1040 // because of merge
1041 left_child = node->GetItemLeftChild(index);
1042 right_child = node->GetItemRightChild(index);
1043
1044 if (left_child->Is34Node()) {
1045 int64_t predecessor_item = GetTreeMaxItem(left_child);
1046 node->SetItem(node->GetItemIndex(item), predecessor_item);
1047
1048 node = left_child;
1049 item = predecessor_item;
1050 continue;
1051 }
1052
1053 if (right_child->Is34Node()) {
1054 int64_t successor_item = GetTreeMinItem(right_child);
1055 node->SetItem(node->GetItemIndex(item), successor_item);
1056 node = right_child;
1057 item = successor_item;
1058 continue;
1059 }
1060 }
1061
1062 Node *next_node = node->GetNextPossibleChild(item);
1063
1064 if (next_node->Is34Node()) {
1065 node = next_node;
1066 continue;
1067 }
1068
1069 if (TryRightRotate(node, next_node)) {
1070 node = next_node;
1071 continue;
1072 }
1073
1074 if (TryLeftRotate(node, next_node)) {
1075 node = next_node;
1076 continue;
1077 }
1078
1079 // get here means both left sibling and right sibling of next_node is
1080 // 2-node, so we do merge
1081 int8_t child_index = node->GetChildIndex(next_node);
1082 if (child_index > 0) {
1083 node = Merge(node, child_index - 1);
1084 } else {
1085 node = Merge(node, child_index);
1086 }
1087
1088 } // while
1089
1090 return false;
1091}
Node * Merge(Node *parent, int8_t index)
Merge the item at index of the parent node, and its left and right child.
Definition tree_234.cpp:895
int64_t GetTreeMinItem(Node *tree)
Get the min item of the tree.
Definition tree_234.cpp:1115
bool TryLeftRotate(Node *parent, Node *to_child)
A handy function to try if we can do a left rotate to the target node.
Definition tree_234.cpp:778
int64_t GetTreeMaxItem(Node *tree)
Get the max item of the tree.
Definition tree_234.cpp:1098
void LeftRotate(Node *parent, int8_t index)
Do the actual left rotate operation.
Definition tree_234.cpp:869
void RightRotate(Node *parent, int8_t index)
Do the actual right rotate operation.
Definition tree_234.cpp:845
bool TryRightRotate(Node *parent, Node *to_child)
A handy function to try if we can do a right rotate to the target node.
Definition tree_234.cpp:813
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
parentthe parent node in this right rotate operation
indexthe pivot item index of this right rotate operation.
845 {
846 Node *left = parent->GetItemLeftChild(index);
847 Node *right = parent->GetItemRightChild(index);
848
849 assert(left && left->Is34Node());
850 assert(right && right->Is2Node());
851
852 right->InsertItemByIndex(0, parent->GetItem(index),
853 left->GetRightmostChild(), true);
854 parent->SetItem(index, left->GetMaxItem());
855 left->RemoveItemByIndex(left->GetCount() - 1, true);
856}

◆ 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
nodethe node to split, it must be a 4-node
Returns
split parent node
745 {
746 assert(node->GetCount() == 3);
747
748 Node *left = node;
749
750 Node *right = new Node(node->GetItem(2));
751 right->SetChild(0, node->GetChild(2));
752 right->SetChild(1, node->GetChild(3));
753
754 Node *parent = new Node(node->GetItem(1));
755 parent->SetChild(0, left);
756 parent->SetChild(1, right);
757
758 left->SetCount(1);
759
760 return parent;
761}

◆ Traverse() [1/2]

void data_structures::tree_234::Tree234::Traverse ( )

In-order traverse.

In-order traverse the tree, print items.

Parameters
treetree to traverse
562 {
565}
void Traverse()
In-order traverse.
Definition tree_234.cpp:562
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
treetree to traverse
567 {
568 if (!node) {
569 return;
570 }
571
572 int8_t i = 0;
573 for (i = 0; i < node->GetCount(); i++) {
574 Traverse(node->GetChild(i));
575 std::cout << node->GetItem(i) << ", ";
576 }
577
578 Traverse(node->GetChild(i));
579}
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
parentthe parent node in this left rotate operation
to_childthe 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.
778 {
779 int to_child_index = parent->GetChildIndex(to_child);
780
781 // child is right most, can not do left rotate to it
782 if (to_child_index >= parent->GetCount()) {
783 return false;
784 }
785
786 Node *right_sibling = parent->GetChild(to_child_index + 1);
787
788 // right sibling is 2-node. can not do left rotate.
789 if (right_sibling->Is2Node()) {
790 return false;
791 }
792
793 LeftRotate(parent, to_child_index);
794
795 return true;
796}
Here is the call graph for this function:

◆ 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
parentthe parent node in this right rotate operation
to_childthe 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.
813 {
814 int8_t to_child_index = parent->GetChildIndex(to_child);
815
816 // child is left most, can not do right rotate to it
817 if (to_child_index <= 0) {
818 return false;
819 }
820
821 Node *left_sibling = parent->GetChild(to_child_index - 1);
822
823 // right sibling is 2-node. can not do left rotate.
824 if (left_sibling->Is2Node()) {
825 return false;
826 }
827
828 RightRotate(parent, to_child_index - 1);
829
830 return true;
831}
Here is the call graph for this function:

Member Data Documentation

◆ root_

Node* data_structures::tree_234::Tree234::root_ {nullptr}
private

root node of the tree

538{nullptr}; ///< root node of the tree

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