红黑树(依照4阶B树C++实现)

理解Javascript的柯里化

我在编写红黑树的时候类比这2-3-4树的原理来书写

语言标准：C++11

在Ubuntu 18.04上通过编译和测试

从刚开始只听说过这个概念，到学习，再到编出代码，然后在进行测试，最后完成代码一共花了大概三天时间

一棵红黑树要满足以下性质

代码中理解CPU结构及工作原理

 我已经实现了AVL树（见博客随笔https://www.cnblogs.com/luyl/p/12253298.html），但由于红黑树的统计性能优异，使用范围更广，所以就想着把红黑树实现一遍

红黑树代码如下

  1 /*
  2  * BinarySearchTree.h
  3  *  添加元素时需自己做判断元素是否合法
  4  *  Created on: 2020年1月29日
  5  *      Author: LuYonglei
  6  */
  7 
  8 #ifndef SRC_BINARYSEARCHTREE_H_
  9 #define SRC_BINARYSEARCHTREE_H_
 10 #include <queue>
 11 
 12 const bool RED = false;
 13 const bool BLACK = true;
 14 
 15 template<typename Element>
 16 class BinarySearchTree {
 17 public:
 18 
 19     BinarySearchTree(int (*cmp)(Element e1, Element e2)); //比较函数指针
 20 
 21     virtual ~BinarySearchTree();
 22 
 23     int size(); //元素的数量
 24 
 25     bool isEmpty(); //是否为空
 26 
 27     void clear() {
 28         //清空所有元素
 29         NODE *node = root_;
 30         root_ = nullptr;
 31         using namespace std;
 32         queue<NODE*> q;
 33         q.push(node);
 34         while (!q.empty()) {
 35             NODE *tmp = q.front();
 36             if (tmp->left != nullptr)
 37                 q.push(tmp->left);
 38             if (tmp->right != nullptr)
 39                 q.push(tmp->right);
 40             delete tmp;
 41             q.pop();
 42         }
 43     }
 44 
 45     void add(Element e) {
 46         //添加元素
 47         add(e, cmp_);
 48     }
 49 
 50     void remove(Element e) {
 51         //删除元素
 52         remove(Node(e, cmp_));
 53     }
 54 
 55     bool contains(Element e) {
 56         //是否包含某元素
 57         return Node(e, cmp_) != nullptr;
 58     }
 59 
 60     void preorderTraversal(bool (*visitor)(Element &e)) {
 61         //前序遍历
 62         if (visitor == nullptr)
 63             return;
 64         bool stop = false; //停止标志，若stop为true，则停止遍历
 65         preorderTraversal(root_, stop, visitor);
 66     }
 67 
 68     void inorderTraversal(bool (*visitor)(Element &e)) {
 69         //中序遍历
 70         if (visitor == nullptr)
 71             return;
 72         bool stop = false; //停止标志，若stop为true，则停止遍历
 73         inorderTraversal(root_, stop, visitor);
 74     }
 75 
 76     void postorderTraversal(bool (*visitor)(Element &e)) {
 77         //后序遍历
 78         if (visitor == nullptr)
 79             return;
 80         bool stop = false; //停止标志，若stop为true，则停止遍历
 81         postorderTraversal(root_, stop, visitor);
 82     }
 83 
 84     void levelOrderTraversal(bool (*visitor)(Element &e)) {
 85         //层序遍历，迭代实现
 86         if (visitor == nullptr)
 87             return;
 88         levelOrderTraversal(root_, visitor);
 89     }
 90 
 91     int height() {
 92         //树的高度
 93         return height(root_);
 94     }
 95 
 96     bool isComplete() {
 97         //判断是否是完全二叉树
 98         return isComplete(root_);
 99     }
100 
101 private:
102 
103     int size_;
104 
105     typedef struct _Node {
106         Element e;
107         _Node *parent;
108         _Node *left;
109         _Node *right;
110         bool color_;
111         _Node(Element e_, _Node *parent_) :
112                 e(e_), parent(parent_), left(nullptr), right(nullptr), color_(
113                         RED) {
114             //节点构造函数
115         }
116 
117         inline bool isLeaf() {
118             return (left == nullptr && right == nullptr);
119         }
120 
121         inline bool hasTwoChildren() {
122             return (left != nullptr && right != nullptr);
123         }
124 
125         inline bool isLeftChild() {
126             //判断节点是否是父亲节点的左子结点
127             return parent != nullptr && parent->left == this;
128         }
129 
130         inline bool isRightChild() {
131             //判断节点是否是父亲节点的右子结点
132             return parent != nullptr && parent->right == this;
133         }
134 
135         inline _Node* sibling() {
136             //返回兄弟节点
137             if (this->parent != nullptr) {
138                 if (this->isLeftChild())
139                     return this->parent->right;
140                 else
141                     return this->parent->left;
142             }
143             return nullptr;
144         }
145 
146     } NODE;
147 
148     NODE *root_;
149 
150     int (*cmp_)(Element e1, Element e2); //为实现树的排序的个性化配置，私有成员保存一个比较函数指针
151 
152     NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) {
153         //返回e元素所在的节点
154         NODE *node = root_;
155         while (node != nullptr) {
156             int cmp = cmp_(e, node->e);
157             if (cmp == 0) //找到了元素
158                 return node;
159             if (cmp > 0) { //待寻找元素大于节点存储的元素
160                 node = node->right;
161             } else { //待寻找元素小于节点存储的元素
162                 node = node->left;
163             }
164         }
165         return nullptr;
166     }
167 
168     NODE* predecessor(NODE *node) {
169         //返回node的前驱节点
170         if (node == nullptr)
171             return nullptr;
172         //前驱节点在左子树
173         NODE *tmp = node->left;
174         if (tmp != nullptr) {
175             while (tmp->right != nullptr)
176                 tmp = tmp->right;
177             return tmp;
178         }
179         //从父节点，祖父节点中寻找前驱节点
180         while (node->parent != nullptr && node == node->parent->left) {
181             node = node->parent;
182         }
183         return node->parent;
184     }
185 
186     NODE* successor(NODE *node) {
187         //返回node的后继节点
188         if (node == nullptr)
189             return nullptr;
190         //后继节点在右子树
191         NODE *tmp = node->right;
192         if (tmp != nullptr) {
193             while (tmp->left != nullptr)
194                 tmp = tmp->left;
195             return tmp;
196         }
197         //从父节点，祖父节点中寻找后继节点
198         while (node->parent != nullptr && node == node->parent->right) {
199             node = node->parent;
200         }
201         return node->parent;
202     }
203 
204     bool colorOf(NODE *node) {
205         //返回节点的颜色
206         return node == nullptr ? BLACK : node->color_;
207     }
208 
209     bool isBlack(NODE *node) {
210         //node是否为黑色
211         return node == nullptr ? true : node->color_ == BLACK;
212     }
213 
214     bool isRed(NODE *node) {
215         //node是否为红色
216         return node == nullptr ? false : node->color_ == RED;
217     }
218 
219     NODE* color(NODE *node, bool color) {
220         //对节点染色
221         if (node == nullptr)
222             return node;
223         node->color_ = color;
224         return node;
225     }
226 
227     NODE* red(NODE *node) {
228         //把节点染成红色
229         return color(node, RED);
230     }
231 
232     NODE* black(NODE *node) {
233         //把节点染成黑色
234         return color(node, BLACK);
235     }
236 
237     void afterRotate(NODE *gNode, NODE *pNode, NODE *child) {
238         //在左旋转与右旋转中统一调用
239         pNode->parent = gNode->parent;
240         if (gNode->isLeftChild())
241             gNode->parent->left = pNode;
242         else if (gNode->isRightChild())
243             gNode->parent->right = pNode;
244         else
245             //此时gNode->parent 为nullptr，gNode为root节点
246             root_ = pNode;
247         if (child != nullptr)
248             child->parent = gNode;
249         gNode->parent = pNode;
250 
251     }
252 
253     void rotateLeft(NODE *gNode) {
254         //对gNode进行左旋转
255         NODE *pNode = gNode->right;
256         NODE *child = pNode->left;
257         gNode->right = child;
258         pNode->left = gNode;
259         afterRotate(gNode, pNode, child);
260 
261     }
262 
263     void rotateRight(NODE *gNode) {
264         //对gNode进行右旋转
265         NODE *pNode = gNode->left;
266         NODE *child = pNode->right;
267         gNode->left = child;
268         pNode->right = gNode;
269         afterRotate(gNode, pNode, child);
270 
271     }
272 
273     void afterAdd(NODE *node) {
274         //添加node之后的操作
275         NODE *parentNode = node->parent;
276         //没有父节点时，新添加的节点是root_或者上溢到root_
277         if (parentNode == nullptr) {
278             black(node);
279             return;
280         }
281         //1.当父亲节点为黑色节点时，不做任何处理,直接返回
282         if (isBlack(parentNode))
283             return;
284         NODE *uncleNode = parentNode->sibling();
285         NODE *grandNode = red(parentNode->parent);
286         if (isRed(uncleNode)) {
287             //2.uncle节点是红色,(上溢,只需要染色)
288             black(parentNode);
289             black(uncleNode);
290             //祖父节点当作是新添加的节点
291             afterAdd(grandNode);
292             return;
293         }
294         //3.uncle节点是黑色或者uncle节点为null
295         if (parentNode->isLeftChild()) {
296             if (node->isLeftChild()) {
297                 //LL
298                 black(parentNode);
299             } else {
300                 //LR
301                 black(node);
302                 rotateLeft(parentNode);
303             }
304             rotateRight(grandNode);
305         } else {
306             if (node->isLeftChild()) {
307                 //RL
308                 black(node);
309                 rotateRight(parentNode);
310             } else {
311                 //RR
312                 black(parentNode);
313             }
314             rotateLeft(grandNode);
315         }
316     }
317 
318     void add(Element e, int (*cmp_)(Element e1, Element e2)) {
319         //当树为空时，添加的节点作为树的根节点
320         if (root_ == nullptr) {
321             root_ = new NODE(e, nullptr);
322             size_++;
323             afterAdd(root_);
324             return;
325         }
326         //当添加的节点不是第一个节点
327         NODE *parent = root_;
328         NODE *node = root_;
329         int cmp = 0; //比较结果
330         while (node != nullptr) {
331             parent = node; //保存父节点
332             cmp = cmp_(e, node->e); //由函数指针来比较
333             if (cmp > 0) {
334                 node = node->right; //添加的元素大于节点中的元素
335             } else if (cmp < 0) {
336                 node = node->left; //添加的元素小于节点中的元素
337             } else {
338                 node->e = e; //相等时就覆盖
339                 return; //添加的元素等于节点中的元素,直接返回
340             }
341         }
342         //判断要插入父节点的哪个位置
343         NODE *newNode = new NODE(e, parent); //为新元素创建节点
344         if (cmp > 0) {
345             parent->right = newNode; //添加的元素大于节点中的元素
346         } else {
347             parent->left = newNode; //添加的元素小于节点中的元素
348         }
349         size_++;
350         afterAdd(newNode);
351     }
352 
353     void afterRemove(NODE *node, NODE *replacement) {
354         //删除node之后的操作
355         //node是要被释放内存的节点，replacement是替代的节点
356         //1.如果删除的是红色节点，直接删掉即可
357         if (isRed(node))        //此处代表删除的节点为红色叶子节点
358             return;
359 
360         if (isRed(replacement)) {
361             //2.如果删除的节点是黑色节点,且替代的节点为红色节点
362             //此处代表删除的节点的度为1,且要删除的节点含有一个红色子节点
363             black(replacement);
364             return;
365         }
366         //3.如果删除的节点是黑色节点,且替代的节点为黑色节点(nullptr)
367         //此处代表要删除的是黑色叶子节点或根节点
368         NODE *parentNode = node->parent;
369         //如果删除的是根节点
370         if (parentNode == nullptr)
371             return;
372 
373         //此时node为叶子节点
374         //但想获得他的兄弟节点不能调用sibling()，因为在调用afterRemove()之前，若node为parent的left就已经将parent的left置为nullptr
375         //若node为parent的right就已经将parent的right置为nullptr,此时再调用sibling()就会得不到准确的信息
376         bool left = parentNode->left == nullptr || node->isLeftChild();
377         NODE *siblingNode = left ? parentNode->right : parentNode->left;
378         if (left) {
379             //被删除的节点在左边，兄弟节点在右边
380             if (isRed(siblingNode)) {
381                 //兄弟节点是红色，要转化成兄弟节点是黑色
382                 black(siblingNode);
383                 red(parentNode);
384                 rotateLeft(parentNode);
385                 //更换兄弟
386                 siblingNode = parentNode->right;
387             }
388             //以下代码处理兄弟节点是黑色(兄弟节点必然为黑色)
389             if (isBlack(siblingNode->left) && isBlack(siblingNode->right)) {
390                 //兄弟节点没有红色子节点，父节点要向下和兄弟节点合并
391                 bool parentIsBlack = isBlack(parentNode);
392                 black(parentNode);
393                 red(siblingNode);
394                 if (parentIsBlack) {
395                     //如果父亲节点是黑色，会产生下溢
396                     afterRemove(parentNode, nullptr);
397                 }
398             } else {
399                 //兄弟节点至少有一个红色子节点,向兄弟节点借元素
400                 //兄弟节点的右边是黑色的，兄弟要先旋转
401                 if (isBlack(siblingNode->right)) {
402                     rotateRight(siblingNode);
403                     siblingNode = parentNode->right;
404                 }
405                 color(siblingNode, colorOf(parentNode));
406                 black(parentNode);
407                 black(siblingNode->right);
408                 rotateLeft(parentNode);
409             }
410         } else {
411             //被删除的节点在右边，兄弟节点在左边
412             if (isRed(siblingNode)) {
413                 //兄弟节点是红色，要转化成兄弟节点是黑色
414                 black(siblingNode);
415                 red(parentNode);
416                 rotateRight(parentNode);
417                 //更换兄弟
418                 siblingNode = parentNode->left;
419             }
420             //以下代码处理兄弟节点是黑色(兄弟节点必然为黑色)
421             if (isBlack(siblingNode->left) && isBlack(siblingNode->right)) {
422                 //兄弟节点没有红色子节点，父节点要向下和兄弟节点合并
423                 bool parentIsBlack = isBlack(parentNode);
424                 black(parentNode);
425                 red(siblingNode);
426                 if (parentIsBlack) {
427                     //如果父亲节点是黑色，会产生下溢
428                     afterRemove(parentNode, nullptr);
429                 }
430             } else {
431                 //兄弟节点至少有一个红色子节点,向兄弟节点借元素
432                 //兄弟节点的左边是黑色的，兄弟要先旋转
433                 if (isBlack(siblingNode->left)) {
434                     rotateLeft(siblingNode);
435                     siblingNode = parentNode->left;
436                 }
437                 color(siblingNode, colorOf(parentNode));
438                 black(parentNode);
439                 black(siblingNode->left);
440                 rotateRight(parentNode);
441             }
442         }
443 
444     }
445 
446     void remove(NODE *node_) {
447         //删除某一节点
448         if (node_ == nullptr)
449             return;
450         size_--;
451         //优先删除度为2的节点
452         if (node_->hasTwoChildren()) {
453             NODE *pre = successor(node_); //找到node_的后继节点
454             node_->e = pre->e; //用后继节点的值覆盖度为2的节点的值
455             //删除后继节点(后继节点的度只能为1或0)
456             node_ = pre;
457         }
458         //此时node_的度必然为0或1
459         NODE *replacement = node_->left != nullptr ? node_->left : node_->right;
460         if (replacement != nullptr) {            //node_的度为1
461             replacement->parent = node_->parent;
462             if (node_->parent == nullptr)            //度为1的根节点
463                 root_ = replacement;
464             else if (node_->parent->left == node_)
465                 node_->parent->left = replacement;
466             else
467                 node_->parent->right = replacement;
468             afterRemove(node_, replacement);
469             delete node_;
470         } else if (node_->parent == nullptr) {            //node_是叶子节点，也是根节点
471             root_ = nullptr;
472             afterRemove(node_, nullptr);
473             delete node_;
474         } else {            //node_是叶子节点，但不是根节点
475             if (node_->parent->left == node_)
476                 node_->parent->left = nullptr;
477             else
478                 node_->parent->right = nullptr;
479             afterRemove(node_, nullptr);
480             delete node_;
481         }
482     }
483 
484     void preorderTraversal(NODE *node, bool &stop,
485             bool (*visitor)(Element &e)) {
486         //递归实现前序遍历
487         if (node == nullptr || stop == true)
488             return;
489         stop = visitor(node->e);
490         preorderTraversal(node->left, stop, visitor);
491         preorderTraversal(node->right, stop, visitor);
492     }
493 
494     void inorderTraversal(NODE *node, bool &stop, bool (*visitor)(Element &e)) {
495         //递归实现中序遍历
496         if (node == nullptr || stop == true)
497             return;
498         inorderTraversal(node->left, stop, visitor);
499         if (stop == true)
500             return;
501         stop = visitor(node->e);
502         inorderTraversal(node->right, stop, visitor);
503     }
504 
505     void postorderTraversal(NODE *node, bool &stop,
506             bool (*visitor)(Element &e)) {
507         //递归实现后序遍历
508         if (node == nullptr || stop == true)
509             return;
510         postorderTraversal(node->left, stop, visitor);
511         postorderTraversal(node->right, stop, visitor);
512         if (stop == true)
513             return;
514         stop = visitor(node->e);
515     }
516 
517     void levelOrderTraversal(NODE *node, bool (*visitor)(Element &e)) {
518         if (node == nullptr)
519             return;
520         using namespace std;
521         queue<NODE*> q;
522         q.push(node);
523         while (!q.empty()) {
524             NODE *node = q.front();
525             if (visitor(node->e) == true)
526                 return;
527             if (node->left != nullptr)
528                 q.push(node->left);
529             if (node->right != nullptr)
530                 q.push(node->right);
531             q.pop();
532         }
533     }
534 
535     int height(NODE *node) {
536         //某一节点的高度
537         if (node == nullptr)
538             return 0;
539         using namespace std;
540         queue<NODE*> q;
541         q.push(node);
542         int height = 0;
543         int levelSize = 1; //每一层起始的节点个数
544         while (!q.empty()) {
545             NODE *node = q.front();
546             levelSize--;
547             if (node->left != nullptr)
548                 q.push(node->left);
549             if (node->right != nullptr)
550                 q.push(node->right);
551             q.pop();
552             if (levelSize == 0) {
553                 height++;
554                 levelSize = q.size();
555             }
556         }
557         return height;
558     }
559 
560     bool isComplete(NODE *node) {
561         if (node == nullptr)
562             return false;
563         using namespace std;
564         queue<NODE*> q;
565         q.push(node);
566         bool leaf = false; //判断接下来的节点是否为叶子节点
567         while (!q.empty()) {
568             NODE *node = q.front();
569             if (leaf && !node->isLeaf()) //判断叶子节点
570                 return false;
571             if (node->left != nullptr) {
572                 q.push(node->left);
573             } else if (node->right != nullptr) { //node->left == nullptr && node->right != nullptr
574                 return false;
575             }
576             if (node->right != nullptr) {
577                 q.push(node->right);
578             } else { //node->right==nullptr
579                 leaf = true;
580             }
581             q.pop();
582         }
583         return true;
584     }
585 
586 };
587 
588 template<typename Element>
589 BinarySearchTree<Element>::BinarySearchTree(int (*cmp)(Element e1, Element e2)) :
590         size_(0), root_(nullptr), cmp_(cmp) {
591     //树的构造函数
592 }
593 
594 template<typename Element>
595 BinarySearchTree<Element>::~BinarySearchTree() {
596     // 析构函数
597     clear();
598 }
599 
600 template<typename Element>
601 inline int BinarySearchTree<Element>::size() {
602     //返回元素个数
603     return size_;
604 }
605 
606 template<typename Element>
607 inline bool BinarySearchTree<Element>::isEmpty() {
608     //判断是否为空树
609     return size_ == 0;
610 }
611 
612 #endif /* SRC_BINARYSEARCHTREE_H_ */

main方法如下

 1 /*
 2  * main.cpp
 3  *
 4  *  Created on: 2020年1月29日
 5  *      Author: LuYonglei
 6  */
 7 
 8 #include "BinarySearchTree.h"
 9 #include <iostream>
10 
11 using namespace std;
12 
13 template<typename Element>
14 int compare(Element e1, Element e2) {
15     //比较函数,相同返回0,e1<e2返回-1,e1>e2返回1
16     return e1 == e2 ? 0 : (e1 < e2 ? -1 : 1);
17 }
18 
19 template<typename Elemnet>
20 bool visitor(Elemnet &e) {
21     cout << e << " ";
22     return false; //若返回true，则在遍历时会退出
23 }
24 
25 int main(int argc, char **argv) {
26     BinarySearchTree<double> a(compare);
27     a.add(55);
28     a.add(87);
29     a.add(56);
30     a.add(74);
31     a.add(96);
32     a.add(22);
33     a.add(62);
34     a.add(20);
35     a.add(70);
36     a.add(68);
37     a.add(90);
38     a.add(50);
39     a.remove(55);
40     a.remove(87);
41     a.remove(56);
42     a.inorderTraversal(visitor);
43     cout << endl;
44 //    cout << a.isComplete() << endl;
45 //    a.remove(7);
46 //    a.clear();
47     a.levelOrderTraversal(visitor);
48     cout << endl;
49 //    cout<<a.contains(0)<<endl;
50 }

RestTemplate—Spring提供的轻量Http Rest 风格API调用工具