bbst node¶
ソースコード¶
1using namespace std;
2
3// BBSTNode
4namespace titan23 {
5
6 template<typename NodePtr>
7 class BBSTNode {
8 public:
9 static NodePtr rotate_right(NodePtr node) {
10 NodePtr u = node->left;
11 u->par = node->par;
12 node->left = u->right;
13 if (u->right) u->right->par = node;
14 u->right = node;
15 node->par = u;
16 node->update();
17 u->update();
18 return u;
19 }
20
21 static NodePtr rotate_left(NodePtr node) {
22 NodePtr u = node->right;
23 u->par = node->par;
24 node->right = u->left;
25 if (u->left) u->left->par = node;
26 u->left = node;
27 node->par = u;
28 node->update();
29 u->update();
30 return u;
31 }
32
33 static NodePtr rotate_LR(NodePtr node) {
34 node->left = rotate_left(node->left);
35 return rotate_right(node);
36 }
37
38 static NodePtr rotate_RL(NodePtr node) {
39 node->right = rotate_right(node->right);
40 return rotate_left(node);
41 }
42
43 static NodePtr _min(NodePtr node) {
44 while (node->left) node = node->left;
45 return node;
46 }
47
48 static NodePtr _max(NodePtr node) {
49 while (node->right) node = node->right;
50 return node;
51 }
52
53 static NodePtr _next(NodePtr node) {
54 NodePtr now = node;
55 NodePtr pre = nullptr;
56 bool flag = now->right == pre;
57 while (now->right == pre) {
58 pre = now;
59 now = now->par;
60 }
61 if (!now) return nullptr;
62 return (flag && pre == now->left) ? now : now->right->_min();
63 }
64
65 static NodePtr _prev(NodePtr node) {
66 NodePtr now = node;
67 NodePtr pre = nullptr;
68 bool flag = now->left == pre;
69 while (now->left == pre) {
70 pre = now;
71 now = now->par;
72 }
73 if (!now) return nullptr;
74 return (flag && pre == now->right) ? now : now->right->_max();
75 }
76 };
77}
仕様¶
Warning
doxygenfile: Cannot find file “titan_cpplib/data_structures/bbst_node.cpp