C++版本的二叉搜索树(LLRB平衡)

andalousie

不久前我曾发布过一个未平衡的二叉搜索树，时至今日，我觉得是时候发布一个基本平衡的左偏红黑树(LLRB)来取代原来的二叉树了。仍将沿用原来的queue.h和main.cpp，只是基于原来的BST做了修改。不多说了，下面分享代码。
BST.h

1. #if !defined (BST_H)
   
2. #defind BST_H
   
3. #include "queue.h"
   
4. 
   
5. template<typename Index, typename Value>
   
6. class BST
   
7. {
   
8. private:
   
9.         const bool RED;
   
10.         const bool BLACK;
    
11.         struct Node
    
12.         {
    
13.                 Node(Index k, Value v, int n, bool cl)
    
14.                 :key(k), val(v), N(n),
    
15.                  left(0), right(0), color(cl)
    
16.                 {}
    
17.                 Index key;
    
18.                 Value val;
    
19.                 Node *left, *right;
    
20.                 bool  color; // color of parent link
    
21.                 int   N;
    
22.         };
    
23.         Node *root;
    
24.         bool isRed(Node* x)
    
25.         {
    
26.                 if(!x) return false;
    
27.                 return x->color = RED;
    
28.         }
    
29. 
    
30.         Node* rotateLeft(Node* h)
    
31.         {
    
32.                 assert (isRed(h->right));
    
33.                 Node *x = h->right;
    
34.                 h->right = x->left;
    
35.                 x->left = h;
    
36.                 x->color = h->color;
    
37.                 h->color = RED;
    
38.                 x->N = h->N;
    
39.                 h->N = 1 + size(h->left)
    
40.                         + size(h->right);
    
41.                 return x;
    
42.         }
    
43. 
    
44.         Node* rotateRight(Node* h)
    
45.         {
    
46.                 assert (isRed(h->left));
    
47.                 Node *x = h->left;
    
48.                 h->left = x->right;
    
49.                 x->right = h;
    
50.                 x->color = h->color;
    
51.                 h->color = RED;
    
52.                 x->N = h->N;
    
53.                 h->N = 1 + size(h->left)
    
54.                         + size(h->right);
    
55.                 return x;
    
56.         }
    
57. 
    
58.         Node* moveRedLeft(Node* h)
    
59.         { // Assuming that h is red and both h->left and h->left->left
    
60.           // are black, make h->left or one of its children red.
    
61.                 flipColors(h);
    
62.                 if (isRed(h->right->left))
    
63.                 {
    
64.                         h->right = rotateRight(h->right);
    
65.                         h = rotateLeft(h);
    
66.                 }
    
67.                 return h;
    
68.         }
    
69. 
    
70.         void flipColors(Node* h)
    
71.         {
    
72.                 h->color = !h->color;
    
73.                 h->left->color = !h->left->color;
    
74.                 h->right->color = !h->right->color;
    
75.         }
    
76. 
    
77.         Node* balance(Node* h)
    
78.         {
    
79.                 assert(h);
    
80.                 if (isRed(h->right) && !isRed(h->left)) h = rotateLeft(h);
    
81.                 if (isRed(h->left) && isRed(h->left->left)) h = rotateRight(h);
    
82.                 if (isRed(h->left) && isRed(h->right)) flipColors(h);
    
83. 
    
84.                 h->N = size(h->left) + size(h->right) + 1;
    
85.                 return h;
    
86.         }
    
87. public:
    
88.         BST(): RED(true), BLACK(false), root(0){}
    
89.         int    size() {        return size(root);        }
    
90.         bool isEmpty() { return !root; }
    
91.         Index min()        { return min(root)->key; }
    
92. 
    
93.         Index floor(Index key)
    
94.         {
    
95.                 Node *x = floor(root, key);
    
96.                 if(!x) return 0;
    
97.                 return x->key;
    
98.         }
    
99. 
    
100.         Value get(Index key) { return get(root, key); }
     
101. 
     
102.         void put(Index key, Value val)
     
103.         { // Search for key. Update value if found; grow table if new.
     
104.                 root = put(root, key, val);
     
105.                 root->color = BLACK;
     
106.         }
     
107. 
     
108.         Value select(int k) { return select(root, k)->key; }
     
109. 
     
110.         int rank(Index key) { return rank(key, root); }
     
111. 
     
112.         void delMin()
     
113.         {   // if both children of root are black, set root to red
     
114.                 if (!isRed(root->left) && !isRed(root->right))
     
115.                         root->color = RED;
     
116.                 root = delMin(root);
     
117.                 if (!isEmpty()) root->color = BLACK;
     
118.         }
     
119. 
     
120.         // delete the key-value pair with the given key
     
121.         void del(Index key)
     
122.         {   // if both children of root are black, set root to red
     
123.                 if (!isRed(root->left) && !isRed(root->right))
     
124.                         root->color = RED;
     
125.                 root = del(root, key);
     
126.                 if (!isEmpty()) root->color = BLACK;
     
127.         }
     
128. 
     
129.         void iterate()
     
130.         {
     
131.                 Queue<Index> q;
     
132.                 inorder(root, q);
     
133.                 while(!q.empty())
     
134.                 {
     
135.                         Index key =  q.pop();
     
136.                         std::cout << get(key);
     
137.                 }
     
138.         }
     
139. private:
     
140.         int   size(Node *x)
     
141.         {
     
142.                 if(!x) return 0;
     
143.                 else   return x->N;
     
144.         }
     
145. 
     
146.         Node* min(Node* x)
     
147.         {
     
148.                 if(!(x->left)) return x;
     
149.                 return min(x->left);
     
150.         }
     
151. 
     
152.         Node* floor(Node* x, Index& key)
     
153.         {
     
154.                 if(!x) return 0;
     
155.                 int cmp = compare(key, x->key);
     
156. 
     
157.                 if (cmp == 0) return x;
     
158. 
     
159.                 if (cmp < 0) return floor(x->left, key);
     
160. 
     
161.                 Node* t = floor(x->right, key);
     
162.                 if(t) return t;
     
163.                 else return x;
     
164.         }
     
165.         
     
166.         Value get(Node *x, Index& key)
     
167.         { // Return value associated with key in the subtree rooted at x;
     
168.           // return null if key not present in subtree rooted at x.
     
169.                 if (!x) return 0;
     
170.                 int cmp = compare(key, x->key);
     
171.                 if (cmp < 0) return get(x->left, key);
     
172.                 else if (cmp > 0) return get(x->right, key);
     
173.                 else return x->val;
     
174.         }
     
175.         
     
176.         Node* put(Node* h, Index key, Value val)
     
177.         {
     
178.                 if(!h)
     
179.                 {
     
180.                         h = new Node(key, val, 1, RED);
     
181.                         return h;
     
182.                 }
     
183.                 int cmp = compare(key, h->key);
     
184.                 if(cmp < 0)
     
185.                         h->left  = put(h->left, key, val);
     
186.                 else if(cmp > 0)
     
187.                         h->right = put(h->right, key, val);
     
188.                 else
     
189.                         h->val = val;
     
190. 
     
191.                 return balance(h);
     
192.         }
     
193. 
     
194.         Node* select(Node* x, int& k)
     
195.         {   // Return Node containing key of rank k.
     
196.                 if(!x) return 0;
     
197.                 int t = size(x->left);
     
198.                 if (t > k) return select(x->left, k);
     
199.                 else if (t < k) return select(x->right, k-t-1);
     
200.                 else return x;
     
201.         }
     
202. 
     
203.         int   rank(Index& key, Node* x)
     
204.         {
     
205.                 if(!x) return 0;
     
206.                 int cmp = compare(key, x->key);
     
207.                 if (cmp < 0) return rank(key, x->left);
     
208.                 else if (cmp > 0) return 1 + size(x->left) + rank(key, x->right);
     
209.                 else return size(x->left);
     
210.         }
     
211. 
     
212.         Node* delMin(Node* h)
     
213.         {
     
214.                 if (!(h->left)) return 0;
     
215.                 if (!isRed(h->left) && !isRed(h->left->left))
     
216.                         h = moveRedLeft(h);
     
217.                 h->left = delMin(h->left);
     
218.                 return balance(h);
     
219.         }
     
220. 
     
221.         Node* del(Node* h, Index& key)
     
222.         {
     
223.                 if(!h) return 0;
     
224.                 int cmp = compare(key, h->key);
     
225.                 /* search for key */
     
226.                 if (cmp < 0)
     
227.                 {
     
228.                         if (!isRed(h->left) && !isRed(h->left->left))
     
229.                                 h = moveRedLeft(h);
     
230.                         h->left = del(h->left, key);
     
231.                 }
     
232.                 else
     
233.                 {
     
234.                         if (isRed(h->left))
     
235.                                 h = rotateRight(h);
     
236.                         if (!cmp && (!h->right))
     
237.                                 return 0;
     
238.                         if (!isRed(h->right) && !isRed(h->right->left))
     
239.                                 h = moveRedLeft(h);
     
240.                         if (!cmp)
     
241.                         {
     
242.                                 /* replace with successor */
     
243.                                 Node* x = min(h->right);
     
244.                                 h->key = x->key;
     
245.                                 h->val = x->val;
     
246.                                 h->right = delMin(h->right);
     
247.                         }
     
248.                         else h->right = del(h->right, key);
     
249.                 }
     
250.                 return balance(h);
     
251.         }
     
252.         
     
253.         int   compare(Index& v, Index& w) const
     
254.         {
     
255.                 if(v > w)      return  1;
     
256.                 else if(v < w) return -1;
     
257.                 return 0;
     
258.         }
     
259. 
     
260.         void inorder(Node* x, Queue<Index>& q)
     
261.         {
     
262.                 if(!x) return;
     
263.                 inorder(x->left, q);
     
264.                 q.push(x->key);
     
265.                 inorder(x->right, q);
     
266.         }
     
267. };
     
268. 
     
269. #endif

复制代码

仍然采用中序遍历。

andalousie

总感觉在BST的initializer_list上才声明RED和BLACK的值有点晚。而且不能体现C和C++的特点。于是试着改了改代码，应用类内的enum类型。于是去掉后面的声明，并将

1.         const bool RED;
   
2.         const bool BLACK;

复制代码

这两行改成了简单明了的

1.         enum { RED = true, BLACK = false };

复制代码

编译通过，大家可以试一试。注意这个枚举类型是没有枚举名称的~