1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
25 #ifndef red_black_trees_h
26 #define red_black_trees_h
28 //////////////////////////////////////////////////////////////////////////////
30 // (1) the number of black links from each path from the root to
31 // a leaf is the same.
32 // (2) no red links may be followed by another red link.
33 //////////////////////////////////////////////////////////////////////////////
35 #include <AD/trees/trees.h>
37 template <class K
, class V
>
38 class RBTree
: public BinaryTree
<K
,V
> {
40 TrNode
<K
,V
> * split(const K
&, TrNode
<K
,V
> *, TrNode
<K
,V
> *,
41 TrNode
<K
,V
> *, TrNode
<K
,V
> *);
42 TrNode
<K
,V
> * rotate(const K
&, TrNode
<K
,V
> *);
46 ///////////////////////////////////////////////////////////////////////
47 // Constructor and destructor
48 ///////////////////////////////////////////////////////////////////////
50 RBTree(RBTree
& t
) { *this = t
; }
53 ///////////////////////////////////////////////////////////////////////
55 ///////////////////////////////////////////////////////////////////////
56 // void operator = (RBTree&); // inherited
58 ///////////////////////////////////////////////////////////////////////
60 ///////////////////////////////////////////////////////////////////////
61 Ix
insert(const K
&, const V
&);
62 Bool
remove(const K
&);
64 ///////////////////////////////////////////////////////////////////////
66 ///////////////////////////////////////////////////////////////////////
70 /////////////////////////////////////////////////////////////////////////////
71 // Implementation of the template methods
72 /////////////////////////////////////////////////////////////////////////////
74 /////////////////////////////////////////////////////////////////////////////
76 /////////////////////////////////////////////////////////////////////////////
77 template <class K
, class V
>
78 Ix RBTree
<K
,V
>::insert(const K
& key
, const V
& value
)
79 { TrNode
<K
,V
> * gg
, * g
, * p
, * x
;
80 p
= g
= x
= (TrNode
<K
,V
>*)tree_root
;
83 int r
= compare(key
,x
->key
);
84 if (r
== 0 && ! duplicates_allowed
) { x
->value
= value
; return; }
85 if (r
< 0) if (x
->is_left_threaded()) break;
86 else x
= (TrNode
<K
,V
>*)x
->L
;
87 else if (x
->is_right_threaded()) break;
88 else x
= (TrNode
<K
,V
>*)x
->R
;
90 if (x
->thread() == No_thread
&& x
->L
->is_red() && x
->R
->is_red())
91 x
= split(key
,gg
,g
,p
,x
);
94 x
= new TrNode
<K
,V
> (key
,value
);
95 if (r
< 0) p
->L
= x
; else p
->R
= x
;
96 x
= split(key
,gg
,g
,p
,x
);
99 /////////////////////////////////////////////////////////////////////////////
101 /////////////////////////////////////////////////////////////////////////////
102 template <class K
, class V
>
103 Bool RBTree
<K
,V
>::remove(const K
& key
)
107 /////////////////////////////////////////////////////////////////////////////
109 /////////////////////////////////////////////////////////////////////////////
110 template <class K
, class V
>
111 TrNode
<K
,V
> * RBTree
<K
,V
>::split
112 (const K
& key
, TrNode
<K
,V
> * gg
,
113 TrNode
<K
,V
> * g
, TrNode
<K
,V
> * p
, TrNode
<K
,V
> * x
)
117 /////////////////////////////////////////////////////////////////////////////
119 /////////////////////////////////////////////////////////////////////////////
120 template <class K
, class V
>
121 TrNode
<K
,V
> * RBTree
<K
,V
>::rotate(const K
&, TrNode
<K
,V
> *)
122 { TrNode
<K
,V
> * c
, * gc
;