算法导论第十三章 红黑树(2)

  1#ifndef __RED_BLACK_TREE_
  2#define __RED_BLACK_TREE_
  3//使用模板类
  4template< typename TKey, typename TValue >
  5class RBTree
  6{
  7    /************************************************************************/
  8    /* 红黑树结点属性
  9    /************************************************************************/
 10public:
 11    //结点的颜色-枚举
 12    enum RBTreeNodeColor {
 13        RED,    //红色
 14        BLACK    //黑色
 15    };
 16    //结点的属性
 17    struct RBTreeNode {
 18        TKey                Key;
 19        TValue                Value;
 20        RBTreeNodeColor        Color;
 21        RBTreeNode            *Parent;
 22        RBTreeNode            *Left;
 23        RBTreeNode            *Right;
 24        //@brief 红黑树中的哨兵结点T.nil实际上是空结点，为无效结点
 25        //@return 返回某个结点是否为无效结点
 26        //@retval = true 非nil结点
 27        //@retval = false nil结点
 28        inline bool isValid() const {
 29            return (this != m_pNil);
 30        }
 31    };
 32    /************************************************************************/
 33    /* 红黑树公有属性
 34    /************************************************************************/
 35public:
 36    RBTree();    //构造函数
 37    ~RBTree();    //析构函数
 38                  //@brief 插入一个结点
 39    bool Insert(TKey key, TValue value);
 40    //@brief 删除一个结点
 41    bool Delete(TKey key);
 42    //@brief 搜索一个结点
 43    RBTreeNode * Search(TValue const &value);
 44    //@brief 判断红黑树是否为空
 45    bool Empty();
 46    //@brief 显示当前红黑树
 47    void Display() const;
 48    /************************************************************************/
 49    /* 红黑树私有属性
 50    /************************************************************************/
 51private:
 52    //@brief 递归删除所有结点
 53    void _RecursiveReleaseNode(RBTreeNode *node);
 54    //@brief 显示
 55    void _Display(RBTreeNode *node) const;
 56    //@brief 真正的插入函数
 57    void _InsertRBTree(RBTreeNode *node);
 58    //@brief 对插入操作的修复
 59    void _InsertFixup(RBTreeNode *node);
 60    //@brief 左旋
 61    void _LeftRotate(RBTreeNode *node);
 62    //@brief 右旋
 63    void _RightRotate(RBTreeNode *node);
 64    //@brief 真正的删除操作
 65    void _Delete(RBTreeNode *node);
 66    //@brief 专属红黑树的替换操作
 67    void _RB_Transplant(RBTreeNode *unode, RBTreeNode *vnode);
 68    //@brief 对删除操作的修复
 69    void _DeleteFixup(RBTreeNode *node);
 70    //@brief 后继
 71    RBTreeNode * _Successor(RBTreeNode *node);
 72    //@brief 前驱
 73    RBTreeNode * _Predecessor(RBTreeNode *node);
 74    //@brief Maximum
 75    RBTreeNode * _Maximum(RBTreeNode *node);
 76    //@brief Minimum
 77    RBTreeNode * _Minimum(RBTreeNode *node);
 78private:
 79    //红黑树的数据成员
 80    RBTreeNode * m_pRoot;    //根结点
 81    static RBTreeNode    *m_pNil;    //哨兵空结点
 82};
 83
 84#endif//__RED_BLACK_TREE_#ifndef __RED_BLACK_TREE_
 85#define __RED_BLACK_TREE_
 86//使用模板类
 87template< typename TKey, typename TValue >
 88class RBTree
 89{
 90    /************************************************************************/
 91    /* 红黑树结点属性
 92    /************************************************************************/
 93public:
 94    //结点的颜色-枚举
 95    enum RBTreeNodeColor {
 96        RED,    //红色
 97        BLACK    //黑色
 98    };
 99    //结点的属性
100    struct RBTreeNode {
101        TKey                Key;
102        TValue                Value;
103        RBTreeNodeColor        Color;
104        RBTreeNode            *Parent;
105        RBTreeNode            *Left;
106        RBTreeNode            *Right;
107        //@brief 红黑树中的哨兵结点T.nil实际上是空结点，为无效结点
108        //@return 返回某个结点是否为无效结点
109        //@retval = true 非nil结点
110        //@retval = false nil结点
111        inline bool isValid() const {
112            return (this != m_pNil);
113        }
114    };
115    /************************************************************************/
116    /* 红黑树公有属性
117    /************************************************************************/
118public:
119    RBTree();    //构造函数
120    ~RBTree();    //析构函数
121                  //@brief 插入一个结点
122    bool Insert(TKey key, TValue value);
123    //@brief 删除一个结点
124    bool Delete(TKey key);
125    //@brief 搜索一个结点
126    RBTreeNode * Search(TValue const &value);
127    //@brief 判断红黑树是否为空
128    bool Empty();
129    //@brief 显示当前红黑树
130    void Display() const;
131    /************************************************************************/
132    /* 红黑树私有属性
133    /************************************************************************/
134private:
135    //@brief 递归删除所有结点
136    void _RecursiveReleaseNode(RBTreeNode *node);
137    //@brief 显示
138    void _Display(RBTreeNode *node) const;
139    //@brief 真正的插入函数
140    void _InsertRBTree(RBTreeNode *node);
141    //@brief 对插入操作的修复
142    void _InsertFixup(RBTreeNode *node);
143    //@brief 左旋
144    void _LeftRotate(RBTreeNode *node);
145    //@brief 右旋
146    void _RightRotate(RBTreeNode *node);
147    //@brief 真正的删除操作
148    void _Delete(RBTreeNode *node);
149    //@brief 专属红黑树的替换操作
150    void _RB_Transplant(RBTreeNode *unode, RBTreeNode *vnode);
151    //@brief 对删除操作的修复
152    void _DeleteFixup(RBTreeNode *node);
153    //@brief 后继
154    RBTreeNode * _Successor(RBTreeNode *node);
155    //@brief 前驱
156    RBTreeNode * _Predecessor(RBTreeNode *node);
157    //@brief Maximum
158    RBTreeNode * _Maximum(RBTreeNode *node);
159    //@brief Minimum
160    RBTreeNode * _Minimum(RBTreeNode *node);
161private:
162    //红黑树的数据成员
163    RBTreeNode * m_pRoot;    //根结点
164    static RBTreeNode    *m_pNil;    //哨兵空结点
165};
166
167#endif//__RED_BLACK_TREE_#ifndef __RED_BLACK_TREE_
168#define __RED_BLACK_TREE_
169//使用模板类
170template< typename TKey, typename TValue >
171class RBTree
172{
173    /************************************************************************/
174    /* 红黑树结点属性
175    /************************************************************************/
176public:
177    //结点的颜色-枚举
178    enum RBTreeNodeColor {
179        RED,    //红色
180        BLACK    //黑色
181    };
182    //结点的属性
183    struct RBTreeNode {
184        TKey                Key;
185        TValue                Value;
186        RBTreeNodeColor        Color;
187        RBTreeNode            *Parent;
188        RBTreeNode            *Left;
189        RBTreeNode            *Right;
190        //@brief 红黑树中的哨兵结点T.nil实际上是空结点，为无效结点
191        //@return 返回某个结点是否为无效结点
192        //@retval = true 非nil结点
193        //@retval = false nil结点
194        inline bool isValid() const {
195            return (this != m_pNil);
196        }
197    };
198    /************************************************************************/
199    /* 红黑树公有属性
200    /************************************************************************/
201public:
202    RBTree();    //构造函数
203    ~RBTree();    //析构函数
204                  //@brief 插入一个结点
205    bool Insert(TKey key, TValue value);
206    //@brief 删除一个结点
207    bool Delete(TKey key);
208    //@brief 搜索一个结点
209    RBTreeNode * Search(TValue const &value);
210    //@brief 判断红黑树是否为空
211    bool Empty();
212    //@brief 显示当前红黑树
213    void Display() const;
214    /************************************************************************/
215    /* 红黑树私有属性
216    /************************************************************************/
217private:
218    //@brief 递归删除所有结点
219    void _RecursiveReleaseNode(RBTreeNode *node);
220    //@brief 显示
221    void _Display(RBTreeNode *node) const;
222    //@brief 真正的插入函数
223    void _InsertRBTree(RBTreeNode *node);
224    //@brief 对插入操作的修复
225    void _InsertFixup(RBTreeNode *node);
226    //@brief 左旋
227    void _LeftRotate(RBTreeNode *node);
228    //@brief 右旋
229    void _RightRotate(RBTreeNode *node);
230    //@brief 真正的删除操作
231    void _Delete(RBTreeNode *node);
232    //@brief 专属红黑树的替换操作
233    void _RB_Transplant(RBTreeNode *unode, RBTreeNode *vnode);
234    //@brief 对删除操作的修复
235    void _DeleteFixup(RBTreeNode *node);
236    //@brief 后继
237    RBTreeNode * _Successor(RBTreeNode *node);
238    //@brief 前驱
239    RBTreeNode * _Predecessor(RBTreeNode *node);
240    //@brief Maximum
241    RBTreeNode * _Maximum(RBTreeNode *node);
242    //@brief Minimum
243    RBTreeNode * _Minimum(RBTreeNode *node);
244private:
245    //红黑树的数据成员
246    RBTreeNode * m_pRoot;    //根结点
247    static RBTreeNode    *m_pNil;    //哨兵空结点
248};
249
250#endif//__RED_BLACK_TREE_#ifndef __RED_BLACK_TREE_
251#define __RED_BLACK_TREE_
252//使用模板类
253template< typename TKey, typename TValue >
254class RBTree
255{
256    /************************************************************************/
257    /* 红黑树结点属性
258    /************************************************************************/
259public:
260    //结点的颜色-枚举
261    enum RBTreeNodeColor {
262        RED,    //红色
263        BLACK    //黑色
264    };
265    //结点的属性
266    struct RBTreeNode {
267        TKey                Key;
268        TValue                Value;
269        RBTreeNodeColor        Color;
270        RBTreeNode            *Parent;
271        RBTreeNode            *Left;
272        RBTreeNode            *Right;
273        //@brief 红黑树中的哨兵结点T.nil实际上是空结点，为无效结点
274        //@return 返回某个结点是否为无效结点
275        //@retval = true 非nil结点
276        //@retval = false nil结点
277        inline bool isValid() const {
278            return (this != m_pNil);
279        }
280    };
281    /************************************************************************/
282    /* 红黑树公有属性
283    /************************************************************************/
284public:
285    RBTree();    //构造函数
286    ~RBTree();    //析构函数
287                  //@brief 插入一个结点
288    bool Insert(TKey key, TValue value);
289    //@brief 删除一个结点
290    bool Delete(TKey key);
291    //@brief 搜索一个结点
292    RBTreeNode * Search(TValue const &value);
293    //@brief 判断红黑树是否为空
294    bool Empty();
295    //@brief 显示当前红黑树
296    void Display() const;
297    /************************************************************************/
298    /* 红黑树私有属性
299    /************************************************************************/
300private:
301    //@brief 递归删除所有结点
302    void _RecursiveReleaseNode(RBTreeNode *node);
303    //@brief 显示
304    void _Display(RBTreeNode *node) const;
305    //@brief 真正的插入函数
306    void _InsertRBTree(RBTreeNode *node);
307    //@brief 对插入操作的修复
308    void _InsertFixup(RBTreeNode *node);
309    //@brief 左旋
310    void _LeftRotate(RBTreeNode *node);
311    //@brief 右旋
312    void _RightRotate(RBTreeNode *node);
313    //@brief 真正的删除操作
314    void _Delete(RBTreeNode *node);
315    //@brief 专属红黑树的替换操作
316    void _RB_Transplant(RBTreeNode *unode, RBTreeNode *vnode);
317    //@brief 对删除操作的修复
318    void _DeleteFixup(RBTreeNode *node);
319    //@brief 后继
320    RBTreeNode * _Successor(RBTreeNode *node);
321    //@brief 前驱
322    RBTreeNode * _Predecessor(RBTreeNode *node);
323    //@brief Maximum
324    RBTreeNode * _Maximum(RBTreeNode *node);
325    //@brief Minimum
326    RBTreeNode * _Minimum(RBTreeNode *node);
327private:
328    //红黑树的数据成员
329    RBTreeNode * m_pRoot;    //根结点
330    static RBTreeNode    *m_pNil;    //哨兵空结点
331};
332
333#endif//__RED_BLACK_TREE_#ifndef __RED_BLACK_TREE_
334#define __RED_BLACK_TREE_
335//使用模板类
336template< typename TKey, typename TValue >
337class RBTree
338{
339    /************************************************************************/
340    /* 红黑树结点属性
341    /************************************************************************/
342public:
343    //结点的颜色-枚举
344    enum RBTreeNodeColor {
345        RED,    //红色
346        BLACK    //黑色
347    };
348    //结点的属性
349    struct RBTreeNode {
350        TKey                Key;
351        TValue                Value;
352        RBTreeNodeColor        Color;
353        RBTreeNode            *Parent;
354        RBTreeNode            *Left;
355        RBTreeNode            *Right;
356        //@brief 红黑树中的哨兵结点T.nil实际上是空结点，为无效结点
357        //@return 返回某个结点是否为无效结点
358        //@retval = true 非nil结点
359        //@retval = false nil结点
360        inline bool isValid() const {
361            return (this != m_pNil);
362        }
363    };
364    /************************************************************************/
365    /* 红黑树公有属性
366    /************************************************************************/
367public:
368    RBTree();    //构造函数
369    ~RBTree();    //析构函数
370                  //@brief 插入一个结点
371    bool Insert(TKey key, TValue value);
372    //@brief 删除一个结点
373    bool Delete(TKey key);
374    //@brief 搜索一个结点
375    RBTreeNode * Search(TValue const &value);
376    //@brief 判断红黑树是否为空
377    bool Empty();
378    //@brief 显示当前红黑树
379    void Display() const;
380    /************************************************************************/
381    /* 红黑树私有属性
382    /************************************************************************/
383private:
384    //@brief 递归删除所有结点
385    void _RecursiveReleaseNode(RBTreeNode *node);
386    //@brief 显示
387    void _Display(RBTreeNode *node) const;
388    //@brief 真正的插入函数
389    void _InsertRBTree(RBTreeNode *node);
390    //@brief 对插入操作的修复
391    void _InsertFixup(RBTreeNode *node);
392    //@brief 左旋
393    void _LeftRotate(RBTreeNode *node);
394    //@brief 右旋
395    void _RightRotate(RBTreeNode *node);
396    //@brief 真正的删除操作
397    void _Delete(RBTreeNode *node);
398    //@brief 专属红黑树的替换操作
399    void _RB_Transplant(RBTreeNode *unode, RBTreeNode *vnode);
400    //@brief 对删除操作的修复
401    void _DeleteFixup(RBTreeNode *node);
402    //@brief 后继
403    RBTreeNode * _Successor(RBTreeNode *node);
404    //@brief 前驱
405    RBTreeNode * _Predecessor(RBTreeNode *node);
406    //@brief Maximum
407    RBTreeNode * _Maximum(RBTreeNode *node);
408    //@brief Minimum
409    RBTreeNode * _Minimum(RBTreeNode *node);
410private:
411    //红黑树的数据成员
412    RBTreeNode * m_pRoot;    //根结点
413    static RBTreeNode    *m_pNil;    //哨兵空结点
414};
415
416#endif//__RED_BLACK_TREE_#ifndef __RED_BLACK_TREE_
417#define __RED_BLACK_TREE_
418//使用模板类
419template< typename TKey, typename TValue >
420class RBTree
421{
422    /************************************************************************/
423    /* 红黑树结点属性
424    /************************************************************************/
425public:
426    //结点的颜色-枚举
427    enum RBTreeNodeColor {
428        RED,    //红色
429        BLACK    //黑色
430    };
431    //结点的属性
432    struct RBTreeNode {
433        TKey                Key;
434        TValue                Value;
435        RBTreeNodeColor        Color;
436        RBTreeNode            *Parent;
437        RBTreeNode            *Left;
438        RBTreeNode            *Right;
439        //@brief 红黑树中的哨兵结点T.nil实际上是空结点，为无效结点
440        //@return 返回某个结点是否为无效结点
441        //@retval = true 非nil结点
442        //@retval = false nil结点
443        inline bool isValid() const {
444            return (this != m_pNil);
445        }
446    };
447    /************************************************************************/
448    /* 红黑树公有属性
449    /************************************************************************/
450public:
451    RBTree();    //构造函数
452    ~RBTree();    //析构函数
453                  //@brief 插入一个结点
454    bool Insert(TKey key, TValue value);
455    //@brief 删除一个结点
456    bool Delete(TKey key);
457    //@brief 搜索一个结点
458    RBTreeNode * Search(TValue const &value);
459    //@brief 判断红黑树是否为空
460    bool Empty();
461    //@brief 显示当前红黑树
462    void Display() const;
463    /************************************************************************/
464    /* 红黑树私有属性
465    /************************************************************************/
466private:
467    //@brief 递归删除所有结点
468    void _RecursiveReleaseNode(RBTreeNode *node);
469    //@brief 显示
470    void _Display(RBTreeNode *node) const;
471    //@brief 真正的插入函数
472    void _InsertRBTree(RBTreeNode *node);
473    //@brief 对插入操作的修复
474    void _InsertFixup(RBTreeNode *node);
475    //@brief 左旋
476    void _LeftRotate(RBTreeNode *node);
477    //@brief 右旋
478    void _RightRotate(RBTreeNode *node);
479    //@brief 真正的删除操作
480    void _Delete(RBTreeNode *node);
481    //@brief 专属红黑树的替换操作
482    void _RB_Transplant(RBTreeNode *unode, RBTreeNode *vnode);
483    //@brief 对删除操作的修复
484    void _DeleteFixup(RBTreeNode *node);
485    //@brief 后继
486    RBTreeNode * _Successor(RBTreeNode *node);
487    //@brief 前驱
488    RBTreeNode * _Predecessor(RBTreeNode *node);
489    //@brief Maximum
490    RBTreeNode * _Maximum(RBTreeNode *node);
491    //@brief Minimum
492    RBTreeNode * _Minimum(RBTreeNode *node);
493private:
494    //红黑树的数据成员
495    RBTreeNode * m_pRoot;    //根结点
496    static RBTreeNode    *m_pNil;    //哨兵空结点
497};
498
499#endif//__RED_BLACK_TREE_#ifndef __RED_BLACK_TREE_
500#define __RED_BLACK_TREE_
501//使用模板类
502template< typename TKey, typename TValue >
503class RBTree
504{
505    /************************************************************************/
506    /* 红黑树结点属性
507    /************************************************************************/
508public:
509    //结点的颜色-枚举
510    enum RBTreeNodeColor {
511        RED,    //红色
512        BLACK    //黑色
513    };
514    //结点的属性
515    struct RBTreeNode {
516        TKey                Key;
517        TValue                Value;
518        RBTreeNodeColor        Color;
519        RBTreeNode            *Parent;
520        RBTreeNode            *Left;
521        RBTreeNode            *Right;
522        //@brief 红黑树中的哨兵结点T.nil实际上是空结点，为无效结点
523        //@return 返回某个结点是否为无效结点
524        //@retval = true 非nil结点
525        //@retval = false nil结点
526        inline bool isValid() const {
527            return (this != m_pNil);
528        }
529    };
530    /************************************************************************/
531    /* 红黑树公有属性
532    /************************************************************************/
533public:
534    RBTree();    //构造函数
535    ~RBTree();    //析构函数
536    //@brief 插入一个结点
537    bool Insert(TKey key, TValue value);
538    //@brief 删除一个结点
539    bool Delete(TKey key);
540    //@brief 搜索一个结点
541    RBTreeNode * Search(TValue const &value);
542    //@brief 判断红黑树是否为空
543    bool Empty();
544    //@brief 显示当前红黑树
545    void Display() const;
546    /************************************************************************/
547    /* 红黑树私有属性
548    /************************************************************************/
549private:
550    //@brief 递归删除所有结点
551    void _RecursiveReleaseNode(RBTreeNode *node);
552    //@brief 显示
553    void _Display(RBTreeNode *node) const;
554    //@brief 真正的插入函数
555    void _InsertRBTree(RBTreeNode *node);
556    //@brief 对插入操作的修复
557    void _InsertFixup(RBTreeNode *node);
558    //@brief 左旋
559    void _LeftRotate(RBTreeNode *node);
560    //@brief 右旋
561    void _RightRotate(RBTreeNode *node);
562    //@brief 真正的删除操作
563    void _Delete(RBTreeNode *node);
564    //@brief 专属红黑树的替换操作
565    void _RB_Transplant(RBTreeNode *unode, RBTreeNode *vnode);
566    //@brief 对删除操作的修复
567    void _DeleteFixup(RBTreeNode *node);
568    //@brief 后继
569    RBTreeNode * _Successor(RBTreeNode *node);
570    //@brief 前驱
571    RBTreeNode * _Predecessor(RBTreeNode *node);
572    //@brief Maximum
573    RBTreeNode * _Maximum(RBTreeNode *node);
574    //@brief Minimum
575    RBTreeNode * _Minimum(RBTreeNode *node);
576private:
577    //红黑树的数据成员
578    RBTreeNode * m_pRoot;    //根结点
579    static RBTreeNode    *m_pNil;    //哨兵空结点
580};
581#endif//__RED_BLACK_TREE_

  1#include <iostream>
  2#include <ctime>
  3#include <cassert>
  4#include <sstream>
  5using namespace std;
  6#include "red_black_tree.h"
  7//静态成员变量初始化
  8template<typename TKey, typename TValue>
  9typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::m_pNil = NULL;
 10template<typename TKey, typename TValue>
 11RBTree<TKey, TValue>::RBTree()
 12{
 13    if (!m_pNil) {
 14        //叶结点是一个特殊的黑结点
 15        m_pNil = new RBTreeNode();
 16        m_pNil->Color = BLACK;
 17    }
 18    m_pRoot = m_pNil;
 19}
 20
 21template<typename TKey, typename TValue>
 22RBTree<TKey, TValue>::~RBTree()
 23{
 24    _RecursiveReleaseNode(m_pRoot);
 25}
 26
 27template<typename TKey, typename TValue>
 28void RBTree<TKey, TValue>::_RecursiveReleaseNode(RBTreeNode *node)
 29{
 30    if (node->isValid()) {
 31        _RecursiveReleaseNode(node->Left);
 32        _RecursiveReleaseNode(node->Right);
 33        delete node;
 34    }
 35}
 36
 37template<typename TKey, typename TValue>
 38bool RBTree<TKey, TValue>::Empty()
 39{
 40    return !(m_pRoot->isValid());
 41}
 42
 43//左旋
 44template<typename TKey, typename TValue>
 45void RBTree<TKey, TValue>::_LeftRotate(RBTreeNode *x_node)
 46{
 47    //assert
 48    if (!(x_node->isValid() && x_node->Right->isValid()))
 49        throw exception("左旋操作要求对非哨兵进行操作，并且要求右孩子也不是哨兵");
 50    RBTreeNode *y_node = x_node->Right;
 51    //以下三步的宗旨是用 y 替换 x，注意将 x 的Parent、Left、Right都换成 y 的
 52    // 1) x 和 y 分离 (补)
 53    x_node->Right = y_node->Left;
 54    if (y_node->Left != m_pNil)
 55        y_node->Left->Parent = x_node;
 56    // 2) 设置y->Parent (提)
 57    y_node->Parent = x_node->Parent;
 58    if (x_node->Parent == m_pNil)
 59        m_pRoot = y_node;
 60    else if (x_node->Parent->Left == x_node)
 61        x_node->Parent->Left = y_node;
 62    else
 63        x_node->Parent->Right = y_node;
 64    // 3) 设置y->Left (降)
 65    y_node->Left = x_node;
 66    x_node->Parent = y_node;
 67}
 68
 69//右旋
 70template<typename TKey, typename TValue>
 71void RBTree<TKey, TValue>::_RightRotate(RBTreeNode *x_node)
 72{
 73    //assert
 74    if (!(x_node->isValid() && x_node->Left->isValid()))
 75        throw exception("右旋操作要求对非哨兵进行操作，并且要求左孩子也不是哨兵");
 76    RBTreeNode *y_node = x_node->Left;
 77    //以下三步的宗旨是用 y 替换 x，注意将 x 的Parent、Left、Right都换成 y 的
 78    // 1) x 和 y 分离 (补)
 79    x_node->Left = y_node->Right;
 80    if (y_node->Right != m_pNil)
 81        y_node->Right->Parent = x_node;
 82    // 2) 设置y->Parent (提)
 83    y_node->Parent = x_node->Parent;
 84    if (x_node->Parent == m_pNil)
 85        m_pRoot = y_node;
 86    else if (x_node->Parent->Right == x_node)
 87        x_node->Parent->Right = y_node;
 88    else
 89        x_node->Parent->Left = y_node;
 90    // 3) 设置y->Left (降)
 91    y_node->Right = x_node;
 92    x_node->Parent = y_node;
 93}
 94
 95//搜索
 96template<typename TKey, typename TValue>
 97typename RBTree<TKey, TValue>::RBTreeNode* RBTree<TKey, TValue>::Search(TValue const &value)
 98{
 99    RBTreeNode *node = m_pRoot;
100    while (node != m_pNil && node->Value != value)
101        node = ((value < node->Value) ? node->Left : node->Right);
102    return node;
103}
104
105//插入
106template<typename TKey, typename TValue>
107bool RBTree<TKey, TValue>::Insert(TKey key, TValue value)
108{
109    if (Search(value)->isValid())
110        //value 重复，添加失败
111        return false;
112    else {
113        //新添加的节点为红结点，left=right=nil
114        RBTreeNode *new_node = new RBTreeNode();
115        new_node->Key = key;
116        new_node->Value = value;
117        new_node->Color = RED;
118        new_node->Left = new_node->Right = m_pNil;
119        //插入
120        _InsertRBTree(new_node);
121        //修复
122        _InsertFixup(new_node);
123        return true;
124    }
125}
126
127//真正的插入:与二叉搜索树几乎一样
128template<typename TKey, typename TValue>
129void RBTree<TKey, TValue>::_InsertRBTree(RBTreeNode *new_node)
130{
131    RBTreeNode *current_node = m_pNil;
132    RBTreeNode *next_node = m_pRoot;
133    //找到插入点
134    while (next_node != m_pNil) {
135        current_node = next_node;
136        next_node = (new_node->Value < next_node->Value) ? next_node->Left : next_node->Right;
137    }
138    new_node->Parent = current_node;
139    if (current_node == m_pNil) //空树
140        m_pRoot = new_node;
141    else if (new_node->Value < current_node->Value)
142        current_node->Left = new_node; //插入左子树
143    else
144        current_node->Right = new_node; //插入右子树
145                                        //设置new_node-left-right = nil, color = red
146    new_node->Left = m_pNil;
147    new_node->Right = m_pNil;
148    new_node->Color = RED;    //插入结点为红色
149}
150
151//插入修复
152//new_node -> z, uncle_node -> y;
153template<typename TKey, typename TValue>
154void RBTree<TKey, TValue>::_InsertFixup(RBTreeNode *new_node)
155{
156    //////////////////////////////////////////////////////////////////////////
157    //啰嗦的写法
158    /*
159    while ( new_node->Parent->Color == RED ) {
160    RBTreeNode *uncle_node = new RBTreeNode();
161    if ( new_node->Parent == new_node->Parent->Parent->Left ) { //new的父结点为祖父结点的左孩子
162    uncle_node = new_node->Parent->Right; //uncle结点在右边
163    if ( uncle_node->Color == RED ) { //case1: new 的叔结点为红色
164    new_node->Color = BLACK;
165    uncle_node->Color = BLACK;
166    new_node->Parent->Color = RED;
167    new_node = new_node->Parent->Parent;
168    }
169    else if ( uncle_node->Color == BLACK && new_node->Parent->Right )  //case2: new 叔结点为黑色且new是一个右孩子
170    _LeftRotate( new_node->Parent );
171    new_node->Parent->Color = BLACK;    //case3: new 叔结点为黑色且new是左孩子
172    new_node->Parent->Parent->Color = RED;
173    _RightRotate( new_node->Parent->Parent );
174    }
175    else { //和上面对称的相同操作
176    ///
177    }
178    }
179    */
180    //////////////////////////////////////////////////////////////////////////
181    //精炼的写法
182    while (new_node->Parent->Color == RED) {
183        //标识new的父结点是否是祖父结点的左孩子
184        bool parent_is_left_child_flag = (new_node->Parent == new_node->Parent->Parent->Left);
185        RBTreeNode *uncle_node = (parent_is_left_child_flag ? new_node->Parent->Parent->Right : new_node->Parent->Parent->Left);
186        if (uncle_node->Color == RED) { //case1: new 的叔结点为红色
187            new_node->Parent->Color = BLACK;  //!!!
188            uncle_node->Color = BLACK;
189            new_node->Parent->Parent->Color = RED; //!!!这两个地方写错了，tmd,还得老子改了大半天
190            new_node = new_node->Parent->Parent;
191        }
192        else {
193            if (new_node == (parent_is_left_child_flag ? new_node->Parent->Right : new_node->Parent->Left)) {//case2: new 叔结点为黑色且new是一个右孩子
194                new_node = new_node->Parent;
195                parent_is_left_child_flag ? _LeftRotate(new_node) : _RightRotate(new_node);
196            }
197            new_node->Parent->Color = BLACK;    //case3: new 叔结点为黑色且new是左孩子
198            new_node->Parent->Parent->Color = RED;
199            parent_is_left_child_flag ? _RightRotate(new_node->Parent->Parent) : _LeftRotate(new_node->Parent->Parent);
200        }
201    }
202    m_pRoot->Color = BLACK;
203}
204
205//删除
206template<typename TKey, typename TValue>
207bool RBTree<TKey, TValue>::Delete(TKey key)
208{
209    //没有找到该结点
210    RBTreeNode *delete_node = Search(key);
211    if (!(delete_node->isValid())) //!isValid()
212        return false;
213    else {
214        _Delete(delete_node);
215        return true;
216    }
217}
218
219//真正的删除
220//形如二叉搜索树的删除，只不过需要记录待删除节点的右孩子的颜色值
221//delete_node -> z; min_node -> y; temp_node -> x
222template<typename TKey, typename TValue>
223void RBTree<TKey, TValue>::_Delete(RBTreeNode *delete_node)
224{
225    RBTreeNode *temp_node = delete_node;
226    int color = delete_node->Color; //记录待删除结点原来的颜色
227    if (delete_node->Left == m_pNil) { //左孩子为空
228        temp_node = delete_node->Right;
229        _RB_Transplant(delete_node, delete_node->Right);
230    }
231    else if (delete_node->Right == m_pNil) {//右孩子为空
232        temp_node = delete_node->Left;
233        _RB_Transplant(delete_node, delete_node->Left);
234    }
235    else {
236        RBTreeNode *min_node = _Minimum(delete_node->Right); //delete的后继结点min_node
237        temp_node = min_node->Right;
238        color = min_node->Color; //更新color
239        if (min_node->Parent == delete_node)
240            temp_node->Parent = min_node;
241        else {
242            _RB_Transplant(min_node, min_node->Right);
243            min_node->Right = delete_node->Right;
244            min_node->Right->Parent = min_node;
245        }
246        _RB_Transplant(delete_node, min_node);
247        min_node->Left = delete_node->Left;
248        min_node->Left->Parent = min_node;
249        min_node->Color = delete_node->Color;
250    }
251    if (color == BLACK)
252        _DeleteFixup(temp_node); //template_node x
253}
254
255//删除修复
256template<typename TKey, typename TValue>
257void RBTree<TKey, TValue>::_DeleteFixup(RBTreeNode *node)
258{
259    while (node != m_pRoot && node->Color == BLACK) {
260        //标识node是否是其父结点的左孩子
261        bool node_is_left_child_flag = (node == node->Parent->Left);
262        //node的兄弟节点
263        RBTreeNode *brother = (node_is_left_child_flag ? node->Parent->Right : node->Parent->Left);
264        //case1 node的兄弟结点为红色，一次旋转操作变成case2
265        if (brother->Color == RED) {
266            node->Parent->Color = RED;
267            brother->Color = BLACK;
268            node_is_left_child_flag ? _LeftRotate(node->Parent) : _RightRotate(node->Parent);
269            //更新brother结点
270            brother = (node_is_left_child_flag ? node->Parent->Right : node->Parent->Left);
271        }
272        //case2 node 的兄弟结点为黑色，且brother两个孩子结点皆为黑色
273        if (brother->Left->Color == BLACK && brother->Right->Color == BLACK) {
274            brother->Color = RED;
275            node = node->Parent; //node更新为上一层
276        }
277        //case3 node的兄弟结点为黑色，且brother的左孩子为红色，右孩子为黑色
278        else {
279            if ((node_is_left_child_flag ? brother->Right->Color : brother->Left->Color) == BLACK) {
280                brother->Color = RED;
281                //注意左右的不同
282                (node_is_left_child_flag ? brother->Left->Color : brother->Right->Color) = BLACK;
283                node_is_left_child_flag ? _RightRotate(brother) : _LeftRotate(brother);
284                brother = (node_is_left_child_flag ? node->Parent->Right : node->Parent->Left); //更新brother结点 -> 变成case4
285            }
286            //case4 node结点的兄弟结点为黑色，且brother 结点的右孩子为红色
287            brother->Color = /*node->Parent->Color*/RED;
288            node->Parent->Color = BLACK;
289            (node_is_left_child_flag ? brother->Right->Color : brother->Left->Color) = BLACK;
290            node_is_left_child_flag ? _LeftRotate(node->Parent) : _RightRotate(node->Parent);
291            node = m_pRoot; //最后赋给root
292        }
293    }
294    //最后只需要简单置x为黑结点就可以，_root的改变已经由左右旋自动处理了
295    node->Color = BLACK;
296}
297
298//RB替换操作
299template<typename TKey, typename TValue>
300void RBTree<TKey, TValue>::_RB_Transplant(RBTreeNode *unode, RBTreeNode *vnode)
301{
302    if (unode->Parent == m_pNil)
303        m_pRoot = vnode;
304    else if (unode->Parent->Left == unode)
305        unode->Parent->Left = vnode;
306    else
307        unode->Parent->Right = vnode;
308    vnode->Parent = unode->Parent; //!!!别漏了
309}
310
311//显示
312template<typename TKey, typename TValue>
313void RBTree<TKey, TValue>::Display() const
314{
315    _Display(m_pRoot);
316    std::cout << std::endl;
317}
318
319template<typename TKey, typename TValue>
320void RBTree<TKey, TValue>::_Display(RBTreeNode *node) const
321{
322    //     if ( node->isValid() ) {
323    //         cout << node->Value << " ";
324    //         if (node->Left->isValid())
325    //             _Display(node->Left);
326    //         if (node->Right->isValid())
327    //             _Display(node->Right);
328    //     }
329    if (node->Parent == m_pNil)
330        cout << "root: " << node->Value << "( " << node->Color << " )" << endl;
331    else if (node->Parent->Left == node)
332        cout << "left: " << node->Value << "( " << node->Color << " )" << " " << "parent: " << node->Parent->Value << "( " << node->Parent->Color << " )" << endl;
333    else cout << "right: " << node->Value << "( " << node->Color << " )" << " " << "parent: " << node->Parent->Value << "( " << node->Parent->Color << " )" << endl;
334    if (node->Left->isValid())
335        _Display(node->Left);
336    if (node->Right->isValid())
337        _Display(node->Right);
338}
339
340//@brief 后继
341template<typename TKey, typename TValue>
342typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::_Successor(RBTreeNode *node)
343{
344    if (node->m_pRight)
345        return _GetMaximum(node);
346    _Node *pTemp = node->m_pParent;
347    while (pTemp && node == pTemp->m_pRight) {
348        node = pTemp;
349        pTemp = pTemp->m_pParent;
350    }
351    return pTemp;
352}
353
354//@brief 前驱
355template<typename TKey, typename TValue>
356typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::_Predecessor(RBTreeNode *node)
357{
358    if (node->m_pLeft)
359        return _GetMinimum(node);
360    _Node *pTemp = node->m_pParent;
361    while (pTemp && node == pTemp->m_pLeft) {
362        node = pTemp;
363        pTemp = pTemp->m_pParent;
364    }
365    return pTemp;
366}
367
368//@brief Maximum
369template<typename TKey, typename TValue>
370typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::_Maximum(RBTreeNode *node)
371{
372    while (node->Right != m_pNil) {
373        node = node->Right;
374    }
375    return node;
376}
377
378//@brief Minimum
379template<typename TKey, typename TValue>
380typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::_Minimum(RBTreeNode *node)
381{
382    while (node->Left != m_pNil) {
383        node = node->Left;
384    }
385    return node;
386}
387
388int main()
389{
390    srand((unsigned)time(NULL));
391    RBTree<int, int> rbt;
392    int ninsert[] = { 12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17 };
393    //int ninsert[] = {3,7,12,10,14,15,16,17,21,19,20,23,26,41,30,28,38,35,39,47};
394    int n = sizeof(ninsert) / sizeof(ninsert[0]);
395    //用随机值生成一棵二叉查找树
396    for (int i = 0; i < n; ++i)
397    {
398        //int v = rand() % 100;
399        rbt.Insert(ninsert[i], ninsert[i]);
400        //rbt.Insert( i, i );
401    }
402    rbt.Display();
403    //     for ( int i = 0; i < n; i ++)
404    //         rbt.Delete( ninsert[i] );
405    //     删除所有的小奇数
406    for (int i = 1; i < n; ++i)
407    {
408        if (i % 2 == 1 /*&& i < 50*/)
409        {
410            if (rbt.Delete(i))
411            {
412                cout << "Deleted [" << i << "]" << endl;
413            }
414        }
415    }
416    rbt.Display();
417    //         //删除所有的大偶数
418    //         for ( int i = 0; i < 100; ++i )
419    //         {
420    //             if ( i % 2 == 0 && i > 50 )
421    //             {
422    //                 if ( rbt.Delete( i ) )
423    //                 {
424    //                     cout << "Deleted [" << i << "]" << endl;
425    //                 }
426    //             }
427    //         }
428    //         rbt.Display();
429    return 0;
430}