-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathRBT.h
76 lines (61 loc) · 1.42 KB
/
RBT.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
* A0118400X
* Shen Juanli
* for CS3230 PJ2 @NUS
* 2013.10
*
*/
#ifndef __RBT_H__
#define __RBT_H__
#include <string>
using namespace std;
enum COLOR {RED = true, BLACK = false};
enum SIDE {LEFT = 0, RIGHT = 1};
typedef string KeyType;
typedef string TelType;
class RBT
{
private:
class Node
{
public:
COLOR color;
KeyType key;
TelType tel;
Node* children[2];
Node* parent;
Node(KeyType key, TelType tel) : key(key), tel(tel), color(RED), parent(nil)
{
children[LEFT] = nil;
children[RIGHT] = nil;
};
Node() : color(BLACK), parent(NULL)
{
children[LEFT] = NULL;
children[RIGHT] = NULL;
};
};
public:
Node* root;
static Node* nil;
RBT() : root(nil) {};
inline bool isRed(Node* node);
inline bool isBlack(Node* node);
inline bool hasRedChild(Node* node);
Node* Minimum(Node* node);
Node* Successor(Node* node);
long Height(Node* node);
long Height();
TelType Search(KeyType key);
void Insert(KeyType key, TelType tel);
void Delete(KeyType key);
Node* Locate(KeyType key);
void Rotate(Node* node, SIDE side);
void InsertFixup(Node* node);
void DeleteFixup(Node* node);
void Print(Node* node, int depth);
void Print();
int CheckBalance(Node* node);
void CheckBalance();
};
#endif // __RBT_H__