1 //===----------------------------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 // Not a portable test
11 
12 // Returns __tree_next(__z)
13 // template <class _NodePtr>
14 // void
15 // __tree_remove(_NodePtr __root, _NodePtr __z)
16 
17 #include <__tree>
18 #include <cassert>
19 
20 struct Node
21 {
22     Node* __left_;
23     Node* __right_;
24     Node* __parent_;
25     bool __is_black_;
26 
27     Node() : __left_(), __right_(), __parent_(), __is_black_() {}
28 };
29 
30 void
31 test1()
32 {
33     {
34         // Left
35         // Case 1 -> Case 2 -> x is red turned to black
36         Node root;
37         Node b;
38         Node c;
39         Node d;
40         Node e;
41         Node y;
42 
43         root.__left_ = &b;
44 
45         b.__parent_ = &root;
46         b.__left_ = &y;
47         b.__right_ = &d;
48         b.__is_black_ = true;
49 
50         y.__parent_ = &b;
51         y.__left_ = 0;
52         y.__right_ = 0;
53         y.__is_black_ = true;
54 
55         d.__parent_ = &b;
56         d.__left_ = &c;
57         d.__right_ = &e;
58         d.__is_black_ = false;
59 
60         c.__parent_ = &d;
61         c.__left_ = 0;
62         c.__right_ = 0;
63         c.__is_black_ = true;
64 
65         e.__parent_ = &d;
66         e.__left_ = 0;
67         e.__right_ = 0;
68         e.__is_black_ = true;
69 
70         std::__tree_remove(root.__left_, &y);
71         assert(std::__tree_invariant(root.__left_));
72 
73         assert(root.__parent_ == 0);
74         assert(root.__left_ == &d);
75         assert(root.__right_ == 0);
76         assert(root.__is_black_ == false);
77 
78         assert(d.__parent_ == &root);
79         assert(d.__left_ == &b);
80         assert(d.__right_ == &e);
81         assert(d.__is_black_ == true);
82 
83         assert(b.__parent_ == &d);
84         assert(b.__left_ == 0);
85         assert(b.__right_ == &c);
86         assert(b.__is_black_ == true);
87 
88         assert(c.__parent_ == &b);
89         assert(c.__left_ == 0);
90         assert(c.__right_ == 0);
91         assert(c.__is_black_ == false);
92 
93         assert(e.__parent_ == &d);
94         assert(e.__left_ == 0);
95         assert(e.__right_ == 0);
96         assert(e.__is_black_ == true);
97     }
98     {
99         // Right
100         // Case 1 -> Case 2 -> x is red turned to black
101         Node root;
102         Node b;
103         Node c;
104         Node d;
105         Node e;
106         Node y;
107 
108         root.__left_ = &b;
109 
110         b.__parent_ = &root;
111         b.__right_ = &y;
112         b.__left_ = &d;
113         b.__is_black_ = true;
114 
115         y.__parent_ = &b;
116         y.__right_ = 0;
117         y.__left_ = 0;
118         y.__is_black_ = true;
119 
120         d.__parent_ = &b;
121         d.__right_ = &c;
122         d.__left_ = &e;
123         d.__is_black_ = false;
124 
125         c.__parent_ = &d;
126         c.__right_ = 0;
127         c.__left_ = 0;
128         c.__is_black_ = true;
129 
130         e.__parent_ = &d;
131         e.__right_ = 0;
132         e.__left_ = 0;
133         e.__is_black_ = true;
134 
135         std::__tree_remove(root.__left_, &y);
136         assert(std::__tree_invariant(root.__left_));
137 
138         assert(root.__parent_ == 0);
139         assert(root.__left_ == &d);
140         assert(root.__right_ == 0);
141         assert(root.__is_black_ == false);
142 
143         assert(d.__parent_ == &root);
144         assert(d.__right_ == &b);
145         assert(d.__left_ == &e);
146         assert(d.__is_black_ == true);
147 
148         assert(b.__parent_ == &d);
149         assert(b.__right_ == 0);
150         assert(b.__left_ == &c);
151         assert(b.__is_black_ == true);
152 
153         assert(c.__parent_ == &b);
154         assert(c.__right_ == 0);
155         assert(c.__left_ == 0);
156         assert(c.__is_black_ == false);
157 
158         assert(e.__parent_ == &d);
159         assert(e.__right_ == 0);
160         assert(e.__left_ == 0);
161         assert(e.__is_black_ == true);
162     }
163     {
164         // Left
165         // Case 1 -> Case 3 -> Case 4
166         Node root;
167         Node b;
168         Node c;
169         Node d;
170         Node e;
171         Node f;
172         Node y;
173 
174         root.__left_ = &b;
175 
176         b.__parent_ = &root;
177         b.__left_ = &y;
178         b.__right_ = &d;
179         b.__is_black_ = true;
180 
181         y.__parent_ = &b;
182         y.__left_ = 0;
183         y.__right_ = 0;
184         y.__is_black_ = true;
185 
186         d.__parent_ = &b;
187         d.__left_ = &c;
188         d.__right_ = &e;
189         d.__is_black_ = false;
190 
191         c.__parent_ = &d;
192         c.__left_ = &f;
193         c.__right_ = 0;
194         c.__is_black_ = true;
195 
196         e.__parent_ = &d;
197         e.__left_ = 0;
198         e.__right_ = 0;
199         e.__is_black_ = true;
200 
201         f.__parent_ = &c;
202         f.__left_ = 0;
203         f.__right_ = 0;
204         f.__is_black_ = false;
205 
206         std::__tree_remove(root.__left_, &y);
207         assert(std::__tree_invariant(root.__left_));
208 
209         assert(root.__parent_ == 0);
210         assert(root.__left_ == &d);
211         assert(root.__right_ == 0);
212         assert(root.__is_black_ == false);
213 
214         assert(d.__parent_ == &root);
215         assert(d.__left_ == &f);
216         assert(d.__right_ == &e);
217         assert(d.__is_black_ == true);
218 
219         assert(f.__parent_ == &d);
220         assert(f.__left_ == &b);
221         assert(f.__right_ == &c);
222         assert(f.__is_black_ == false);
223 
224         assert(b.__parent_ == &f);
225         assert(b.__left_ == 0);
226         assert(b.__right_ == 0);
227         assert(b.__is_black_ == true);
228 
229         assert(c.__parent_ == &f);
230         assert(c.__left_ == 0);
231         assert(c.__right_ == 0);
232         assert(c.__is_black_ == true);
233 
234         assert(e.__parent_ == &d);
235         assert(e.__left_ == 0);
236         assert(e.__right_ == 0);
237         assert(e.__is_black_ == true);
238     }
239     {
240         // Right
241         // Case 1 -> Case 3 -> Case 4
242         Node root;
243         Node b;
244         Node c;
245         Node d;
246         Node e;
247         Node f;
248         Node y;
249 
250         root.__left_ = &b;
251 
252         b.__parent_ = &root;
253         b.__right_ = &y;
254         b.__left_ = &d;
255         b.__is_black_ = true;
256 
257         y.__parent_ = &b;
258         y.__right_ = 0;
259         y.__left_ = 0;
260         y.__is_black_ = true;
261 
262         d.__parent_ = &b;
263         d.__right_ = &c;
264         d.__left_ = &e;
265         d.__is_black_ = false;
266 
267         c.__parent_ = &d;
268         c.__right_ = &f;
269         c.__left_ = 0;
270         c.__is_black_ = true;
271 
272         e.__parent_ = &d;
273         e.__right_ = 0;
274         e.__left_ = 0;
275         e.__is_black_ = true;
276 
277         f.__parent_ = &c;
278         f.__right_ = 0;
279         f.__left_ = 0;
280         f.__is_black_ = false;
281 
282         std::__tree_remove(root.__left_, &y);
283         assert(std::__tree_invariant(root.__left_));
284 
285         assert(root.__parent_ == 0);
286         assert(root.__left_ == &d);
287         assert(root.__right_ == 0);
288         assert(root.__is_black_ == false);
289 
290         assert(d.__parent_ == &root);
291         assert(d.__right_ == &f);
292         assert(d.__left_ == &e);
293         assert(d.__is_black_ == true);
294 
295         assert(f.__parent_ == &d);
296         assert(f.__right_ == &b);
297         assert(f.__left_ == &c);
298         assert(f.__is_black_ == false);
299 
300         assert(b.__parent_ == &f);
301         assert(b.__right_ == 0);
302         assert(b.__left_ == 0);
303         assert(b.__is_black_ == true);
304 
305         assert(c.__parent_ == &f);
306         assert(c.__right_ == 0);
307         assert(c.__left_ == 0);
308         assert(c.__is_black_ == true);
309 
310         assert(e.__parent_ == &d);
311         assert(e.__right_ == 0);
312         assert(e.__left_ == 0);
313         assert(e.__is_black_ == true);
314     }
315 }
316 
317 void
318 test2()
319 {
320     {
321         Node root;
322         Node a;
323         Node b;
324         Node c;
325 
326         root.__left_ = &b;
327 
328         b.__parent_ = &root;
329         b.__left_ = &a;
330         b.__right_ = &c;
331         b.__is_black_ = true;
332 
333         a.__parent_ = &b;
334         a.__left_ = 0;
335         a.__right_ = 0;
336         a.__is_black_ = true;
337 
338         c.__parent_ = &b;
339         c.__left_ = 0;
340         c.__right_ = 0;
341         c.__is_black_ = true;
342 
343         std::__tree_remove(root.__left_, &a);
344 
345         assert(std::__tree_invariant(root.__left_));
346 
347         assert(root.__parent_ == 0);
348         assert(root.__left_ == &b);
349         assert(root.__right_ == 0);
350         assert(root.__is_black_ == false);
351 
352         assert(b.__parent_ == &root);
353         assert(b.__left_ == 0);
354         assert(b.__right_ == &c);
355         assert(b.__is_black_ == true);
356 
357         assert(c.__parent_ == &b);
358         assert(c.__left_ == 0);
359         assert(c.__right_ == 0);
360         assert(c.__is_black_ == false);
361 
362         std::__tree_remove(root.__left_, &b);
363 
364         assert(std::__tree_invariant(root.__left_));
365 
366         assert(root.__parent_ == 0);
367         assert(root.__left_ == &c);
368         assert(root.__right_ == 0);
369         assert(root.__is_black_ == false);
370 
371         assert(c.__parent_ == &root);
372         assert(c.__left_ == 0);
373         assert(c.__right_ == 0);
374         assert(c.__is_black_ == true);
375 
376         std::__tree_remove(root.__left_, &c);
377 
378         assert(std::__tree_invariant(root.__left_));
379 
380         assert(root.__parent_ == 0);
381         assert(root.__left_ == 0);
382         assert(root.__right_ == 0);
383         assert(root.__is_black_ == false);
384     }
385     {
386         Node root;
387         Node a;
388         Node b;
389         Node c;
390 
391         root.__left_ = &b;
392 
393         b.__parent_ = &root;
394         b.__left_ = &a;
395         b.__right_ = &c;
396         b.__is_black_ = true;
397 
398         a.__parent_ = &b;
399         a.__left_ = 0;
400         a.__right_ = 0;
401         a.__is_black_ = false;
402 
403         c.__parent_ = &b;
404         c.__left_ = 0;
405         c.__right_ = 0;
406         c.__is_black_ = false;
407 
408         std::__tree_remove(root.__left_, &a);
409 
410         assert(std::__tree_invariant(root.__left_));
411 
412         assert(root.__parent_ == 0);
413         assert(root.__left_ == &b);
414         assert(root.__right_ == 0);
415         assert(root.__is_black_ == false);
416 
417         assert(b.__parent_ == &root);
418         assert(b.__left_ == 0);
419         assert(b.__right_ == &c);
420         assert(b.__is_black_ == true);
421 
422         assert(c.__parent_ == &b);
423         assert(c.__left_ == 0);
424         assert(c.__right_ == 0);
425         assert(c.__is_black_ == false);
426 
427         std::__tree_remove(root.__left_, &b);
428 
429         assert(std::__tree_invariant(root.__left_));
430 
431         assert(root.__parent_ == 0);
432         assert(root.__left_ == &c);
433         assert(root.__right_ == 0);
434         assert(root.__is_black_ == false);
435 
436         assert(c.__parent_ == &root);
437         assert(c.__left_ == 0);
438         assert(c.__right_ == 0);
439         assert(c.__is_black_ == true);
440 
441         std::__tree_remove(root.__left_, &c);
442 
443         assert(std::__tree_invariant(root.__left_));
444 
445         assert(root.__parent_ == 0);
446         assert(root.__left_ == 0);
447         assert(root.__right_ == 0);
448         assert(root.__is_black_ == false);
449     }
450     {
451         Node root;
452         Node a;
453         Node b;
454         Node c;
455 
456         root.__left_ = &b;
457 
458         b.__parent_ = &root;
459         b.__left_ = &a;
460         b.__right_ = &c;
461         b.__is_black_ = true;
462 
463         a.__parent_ = &b;
464         a.__left_ = 0;
465         a.__right_ = 0;
466         a.__is_black_ = true;
467 
468         c.__parent_ = &b;
469         c.__left_ = 0;
470         c.__right_ = 0;
471         c.__is_black_ = true;
472 
473         std::__tree_remove(root.__left_, &a);
474 
475         assert(std::__tree_invariant(root.__left_));
476 
477         assert(root.__parent_ == 0);
478         assert(root.__left_ == &b);
479         assert(root.__right_ == 0);
480         assert(root.__is_black_ == false);
481 
482         assert(b.__parent_ == &root);
483         assert(b.__left_ == 0);
484         assert(b.__right_ == &c);
485         assert(b.__is_black_ == true);
486 
487         assert(c.__parent_ == &b);
488         assert(c.__left_ == 0);
489         assert(c.__right_ == 0);
490         assert(c.__is_black_ == false);
491 
492         std::__tree_remove(root.__left_, &c);
493 
494         assert(std::__tree_invariant(root.__left_));
495 
496         assert(root.__parent_ == 0);
497         assert(root.__left_ == &b);
498         assert(root.__right_ == 0);
499         assert(root.__is_black_ == false);
500 
501         assert(b.__parent_ == &root);
502         assert(b.__left_ == 0);
503         assert(b.__right_ == 0);
504         assert(b.__is_black_ == true);
505 
506         std::__tree_remove(root.__left_, &b);
507 
508         assert(std::__tree_invariant(root.__left_));
509 
510         assert(root.__parent_ == 0);
511         assert(root.__left_ == 0);
512         assert(root.__right_ == 0);
513         assert(root.__is_black_ == false);
514     }
515     {
516         Node root;
517         Node a;
518         Node b;
519         Node c;
520 
521         root.__left_ = &b;
522 
523         b.__parent_ = &root;
524         b.__left_ = &a;
525         b.__right_ = &c;
526         b.__is_black_ = true;
527 
528         a.__parent_ = &b;
529         a.__left_ = 0;
530         a.__right_ = 0;
531         a.__is_black_ = false;
532 
533         c.__parent_ = &b;
534         c.__left_ = 0;
535         c.__right_ = 0;
536         c.__is_black_ = false;
537 
538         std::__tree_remove(root.__left_, &a);
539 
540         assert(std::__tree_invariant(root.__left_));
541 
542         assert(root.__parent_ == 0);
543         assert(root.__left_ == &b);
544         assert(root.__right_ == 0);
545         assert(root.__is_black_ == false);
546 
547         assert(b.__parent_ == &root);
548         assert(b.__left_ == 0);
549         assert(b.__right_ == &c);
550         assert(b.__is_black_ == true);
551 
552         assert(c.__parent_ == &b);
553         assert(c.__left_ == 0);
554         assert(c.__right_ == 0);
555         assert(c.__is_black_ == false);
556 
557         std::__tree_remove(root.__left_, &c);
558 
559         assert(std::__tree_invariant(root.__left_));
560 
561         assert(root.__parent_ == 0);
562         assert(root.__left_ == &b);
563         assert(root.__right_ == 0);
564         assert(root.__is_black_ == false);
565 
566         assert(b.__parent_ == &root);
567         assert(b.__left_ == 0);
568         assert(b.__right_ == 0);
569         assert(b.__is_black_ == true);
570 
571         std::__tree_remove(root.__left_, &b);
572 
573         assert(std::__tree_invariant(root.__left_));
574 
575         assert(root.__parent_ == 0);
576         assert(root.__left_ == 0);
577         assert(root.__right_ == 0);
578         assert(root.__is_black_ == false);
579     }
580     {
581         Node root;
582         Node a;
583         Node b;
584         Node c;
585 
586         root.__left_ = &b;
587 
588         b.__parent_ = &root;
589         b.__left_ = &a;
590         b.__right_ = &c;
591         b.__is_black_ = true;
592 
593         a.__parent_ = &b;
594         a.__left_ = 0;
595         a.__right_ = 0;
596         a.__is_black_ = true;
597 
598         c.__parent_ = &b;
599         c.__left_ = 0;
600         c.__right_ = 0;
601         c.__is_black_ = true;
602 
603         std::__tree_remove(root.__left_, &b);
604 
605         assert(std::__tree_invariant(root.__left_));
606 
607         assert(root.__parent_ == 0);
608         assert(root.__left_ == &c);
609         assert(root.__right_ == 0);
610         assert(root.__is_black_ == false);
611 
612         assert(a.__parent_ == &c);
613         assert(a.__left_ == 0);
614         assert(a.__right_ == 0);
615         assert(a.__is_black_ == false);
616 
617         assert(c.__parent_ == &root);
618         assert(c.__left_ == &a);
619         assert(c.__right_ == 0);
620         assert(c.__is_black_ == true);
621 
622         std::__tree_remove(root.__left_, &a);
623 
624         assert(std::__tree_invariant(root.__left_));
625 
626         assert(root.__parent_ == 0);
627         assert(root.__left_ == &c);
628         assert(root.__right_ == 0);
629         assert(root.__is_black_ == false);
630 
631         assert(c.__parent_ == &root);
632         assert(c.__left_ == 0);
633         assert(c.__right_ == 0);
634         assert(c.__is_black_ == true);
635 
636         std::__tree_remove(root.__left_, &c);
637 
638         assert(std::__tree_invariant(root.__left_));
639 
640         assert(root.__parent_ == 0);
641         assert(root.__left_ == 0);
642         assert(root.__right_ == 0);
643         assert(root.__is_black_ == false);
644     }
645     {
646         Node root;
647         Node a;
648         Node b;
649         Node c;
650 
651         root.__left_ = &b;
652 
653         b.__parent_ = &root;
654         b.__left_ = &a;
655         b.__right_ = &c;
656         b.__is_black_ = true;
657 
658         a.__parent_ = &b;
659         a.__left_ = 0;
660         a.__right_ = 0;
661         a.__is_black_ = false;
662 
663         c.__parent_ = &b;
664         c.__left_ = 0;
665         c.__right_ = 0;
666         c.__is_black_ = false;
667 
668         std::__tree_remove(root.__left_, &b);
669 
670         assert(std::__tree_invariant(root.__left_));
671 
672         assert(root.__parent_ == 0);
673         assert(root.__left_ == &c);
674         assert(root.__right_ == 0);
675         assert(root.__is_black_ == false);
676 
677         assert(a.__parent_ == &c);
678         assert(a.__left_ == 0);
679         assert(a.__right_ == 0);
680         assert(a.__is_black_ == false);
681 
682         assert(c.__parent_ == &root);
683         assert(c.__left_ == &a);
684         assert(c.__right_ == 0);
685         assert(c.__is_black_ == true);
686 
687         std::__tree_remove(root.__left_, &a);
688 
689         assert(std::__tree_invariant(root.__left_));
690 
691         assert(root.__parent_ == 0);
692         assert(root.__left_ == &c);
693         assert(root.__right_ == 0);
694         assert(root.__is_black_ == false);
695 
696         assert(c.__parent_ == &root);
697         assert(c.__left_ == 0);
698         assert(c.__right_ == 0);
699         assert(c.__is_black_ == true);
700 
701         std::__tree_remove(root.__left_, &c);
702 
703         assert(std::__tree_invariant(root.__left_));
704 
705         assert(root.__parent_ == 0);
706         assert(root.__left_ == 0);
707         assert(root.__right_ == 0);
708         assert(root.__is_black_ == false);
709     }
710     {
711         Node root;
712         Node a;
713         Node b;
714         Node c;
715 
716         root.__left_ = &b;
717 
718         b.__parent_ = &root;
719         b.__left_ = &a;
720         b.__right_ = &c;
721         b.__is_black_ = true;
722 
723         a.__parent_ = &b;
724         a.__left_ = 0;
725         a.__right_ = 0;
726         a.__is_black_ = true;
727 
728         c.__parent_ = &b;
729         c.__left_ = 0;
730         c.__right_ = 0;
731         c.__is_black_ = true;
732 
733         std::__tree_remove(root.__left_, &b);
734 
735         assert(std::__tree_invariant(root.__left_));
736 
737         assert(root.__parent_ == 0);
738         assert(root.__left_ == &c);
739         assert(root.__right_ == 0);
740         assert(root.__is_black_ == false);
741 
742         assert(a.__parent_ == &c);
743         assert(a.__left_ == 0);
744         assert(a.__right_ == 0);
745         assert(a.__is_black_ == false);
746 
747         assert(c.__parent_ == &root);
748         assert(c.__left_ == &a);
749         assert(c.__right_ == 0);
750         assert(c.__is_black_ == true);
751 
752         std::__tree_remove(root.__left_, &c);
753 
754         assert(std::__tree_invariant(root.__left_));
755 
756         assert(root.__parent_ == 0);
757         assert(root.__left_ == &a);
758         assert(root.__right_ == 0);
759         assert(root.__is_black_ == false);
760 
761         assert(a.__parent_ == &root);
762         assert(a.__left_ == 0);
763         assert(a.__right_ == 0);
764         assert(a.__is_black_ == true);
765 
766         std::__tree_remove(root.__left_, &a);
767 
768         assert(std::__tree_invariant(root.__left_));
769 
770         assert(root.__parent_ == 0);
771         assert(root.__left_ == 0);
772         assert(root.__right_ == 0);
773         assert(root.__is_black_ == false);
774     }
775     {
776         Node root;
777         Node a;
778         Node b;
779         Node c;
780 
781         root.__left_ = &b;
782 
783         b.__parent_ = &root;
784         b.__left_ = &a;
785         b.__right_ = &c;
786         b.__is_black_ = true;
787 
788         a.__parent_ = &b;
789         a.__left_ = 0;
790         a.__right_ = 0;
791         a.__is_black_ = false;
792 
793         c.__parent_ = &b;
794         c.__left_ = 0;
795         c.__right_ = 0;
796         c.__is_black_ = false;
797 
798         std::__tree_remove(root.__left_, &b);
799 
800         assert(std::__tree_invariant(root.__left_));
801 
802         assert(root.__parent_ == 0);
803         assert(root.__left_ == &c);
804         assert(root.__right_ == 0);
805         assert(root.__is_black_ == false);
806 
807         assert(a.__parent_ == &c);
808         assert(a.__left_ == 0);
809         assert(a.__right_ == 0);
810         assert(a.__is_black_ == false);
811 
812         assert(c.__parent_ == &root);
813         assert(c.__left_ == &a);
814         assert(c.__right_ == 0);
815         assert(c.__is_black_ == true);
816 
817         std::__tree_remove(root.__left_, &c);
818 
819         assert(std::__tree_invariant(root.__left_));
820 
821         assert(root.__parent_ == 0);
822         assert(root.__left_ == &a);
823         assert(root.__right_ == 0);
824         assert(root.__is_black_ == false);
825 
826         assert(a.__parent_ == &root);
827         assert(a.__left_ == 0);
828         assert(a.__right_ == 0);
829         assert(a.__is_black_ == true);
830 
831         std::__tree_remove(root.__left_, &a);
832 
833         assert(std::__tree_invariant(root.__left_));
834 
835         assert(root.__parent_ == 0);
836         assert(root.__left_ == 0);
837         assert(root.__right_ == 0);
838         assert(root.__is_black_ == false);
839     }
840     {
841         Node root;
842         Node a;
843         Node b;
844         Node c;
845 
846         root.__left_ = &b;
847 
848         b.__parent_ = &root;
849         b.__left_ = &a;
850         b.__right_ = &c;
851         b.__is_black_ = true;
852 
853         a.__parent_ = &b;
854         a.__left_ = 0;
855         a.__right_ = 0;
856         a.__is_black_ = true;
857 
858         c.__parent_ = &b;
859         c.__left_ = 0;
860         c.__right_ = 0;
861         c.__is_black_ = true;
862 
863         std::__tree_remove(root.__left_, &c);
864 
865         assert(std::__tree_invariant(root.__left_));
866 
867         assert(root.__parent_ == 0);
868         assert(root.__left_ == &b);
869         assert(root.__right_ == 0);
870         assert(root.__is_black_ == false);
871 
872         assert(a.__parent_ == &b);
873         assert(a.__left_ == 0);
874         assert(a.__right_ == 0);
875         assert(a.__is_black_ == false);
876 
877         assert(b.__parent_ == &root);
878         assert(b.__left_ == &a);
879         assert(b.__right_ == 0);
880         assert(b.__is_black_ == true);
881 
882         std::__tree_remove(root.__left_, &b);
883 
884         assert(std::__tree_invariant(root.__left_));
885 
886         assert(root.__parent_ == 0);
887         assert(root.__left_ == &a);
888         assert(root.__right_ == 0);
889         assert(root.__is_black_ == false);
890 
891         assert(a.__parent_ == &root);
892         assert(a.__left_ == 0);
893         assert(a.__right_ == 0);
894         assert(a.__is_black_ == true);
895 
896         std::__tree_remove(root.__left_, &a);
897 
898         assert(std::__tree_invariant(root.__left_));
899 
900         assert(root.__parent_ == 0);
901         assert(root.__left_ == 0);
902         assert(root.__right_ == 0);
903         assert(root.__is_black_ == false);
904     }
905     {
906         Node root;
907         Node a;
908         Node b;
909         Node c;
910 
911         root.__left_ = &b;
912 
913         b.__parent_ = &root;
914         b.__left_ = &a;
915         b.__right_ = &c;
916         b.__is_black_ = true;
917 
918         a.__parent_ = &b;
919         a.__left_ = 0;
920         a.__right_ = 0;
921         a.__is_black_ = false;
922 
923         c.__parent_ = &b;
924         c.__left_ = 0;
925         c.__right_ = 0;
926         c.__is_black_ = false;
927 
928         std::__tree_remove(root.__left_, &c);
929 
930         assert(std::__tree_invariant(root.__left_));
931 
932         assert(root.__parent_ == 0);
933         assert(root.__left_ == &b);
934         assert(root.__right_ == 0);
935         assert(root.__is_black_ == false);
936 
937         assert(a.__parent_ == &b);
938         assert(a.__left_ == 0);
939         assert(a.__right_ == 0);
940         assert(a.__is_black_ == false);
941 
942         assert(b.__parent_ == &root);
943         assert(b.__left_ == &a);
944         assert(b.__right_ == 0);
945         assert(b.__is_black_ == true);
946 
947         std::__tree_remove(root.__left_, &b);
948 
949         assert(std::__tree_invariant(root.__left_));
950 
951         assert(root.__parent_ == 0);
952         assert(root.__left_ == &a);
953         assert(root.__right_ == 0);
954         assert(root.__is_black_ == false);
955 
956         assert(a.__parent_ == &root);
957         assert(a.__left_ == 0);
958         assert(a.__right_ == 0);
959         assert(a.__is_black_ == true);
960 
961         std::__tree_remove(root.__left_, &a);
962 
963         assert(std::__tree_invariant(root.__left_));
964 
965         assert(root.__parent_ == 0);
966         assert(root.__left_ == 0);
967         assert(root.__right_ == 0);
968         assert(root.__is_black_ == false);
969     }
970     {
971         Node root;
972         Node a;
973         Node b;
974         Node c;
975 
976         root.__left_ = &b;
977 
978         b.__parent_ = &root;
979         b.__left_ = &a;
980         b.__right_ = &c;
981         b.__is_black_ = true;
982 
983         a.__parent_ = &b;
984         a.__left_ = 0;
985         a.__right_ = 0;
986         a.__is_black_ = true;
987 
988         c.__parent_ = &b;
989         c.__left_ = 0;
990         c.__right_ = 0;
991         c.__is_black_ = true;
992 
993         std::__tree_remove(root.__left_, &c);
994 
995         assert(std::__tree_invariant(root.__left_));
996 
997         assert(root.__parent_ == 0);
998         assert(root.__left_ == &b);
999         assert(root.__right_ == 0);
1000         assert(root.__is_black_ == false);
1001 
1002         assert(a.__parent_ == &b);
1003         assert(a.__left_ == 0);
1004         assert(a.__right_ == 0);
1005         assert(a.__is_black_ == false);
1006 
1007         assert(b.__parent_ == &root);
1008         assert(b.__left_ == &a);
1009         assert(b.__right_ == 0);
1010         assert(b.__is_black_ == true);
1011 
1012         std::__tree_remove(root.__left_, &a);
1013 
1014         assert(std::__tree_invariant(root.__left_));
1015 
1016         assert(root.__parent_ == 0);
1017         assert(root.__left_ == &b);
1018         assert(root.__right_ == 0);
1019         assert(root.__is_black_ == false);
1020 
1021         assert(b.__parent_ == &root);
1022         assert(b.__left_ == 0);
1023         assert(b.__right_ == 0);
1024         assert(b.__is_black_ == true);
1025 
1026         std::__tree_remove(root.__left_, &b);
1027 
1028         assert(std::__tree_invariant(root.__left_));
1029 
1030         assert(root.__parent_ == 0);
1031         assert(root.__left_ == 0);
1032         assert(root.__right_ == 0);
1033         assert(root.__is_black_ == false);
1034     }
1035     {
1036         Node root;
1037         Node a;
1038         Node b;
1039         Node c;
1040 
1041         root.__left_ = &b;
1042 
1043         b.__parent_ = &root;
1044         b.__left_ = &a;
1045         b.__right_ = &c;
1046         b.__is_black_ = true;
1047 
1048         a.__parent_ = &b;
1049         a.__left_ = 0;
1050         a.__right_ = 0;
1051         a.__is_black_ = false;
1052 
1053         c.__parent_ = &b;
1054         c.__left_ = 0;
1055         c.__right_ = 0;
1056         c.__is_black_ = false;
1057 
1058         std::__tree_remove(root.__left_, &c);
1059 
1060         assert(std::__tree_invariant(root.__left_));
1061 
1062         assert(root.__parent_ == 0);
1063         assert(root.__left_ == &b);
1064         assert(root.__right_ == 0);
1065         assert(root.__is_black_ == false);
1066 
1067         assert(a.__parent_ == &b);
1068         assert(a.__left_ == 0);
1069         assert(a.__right_ == 0);
1070         assert(a.__is_black_ == false);
1071 
1072         assert(b.__parent_ == &root);
1073         assert(b.__left_ == &a);
1074         assert(b.__right_ == 0);
1075         assert(b.__is_black_ == true);
1076 
1077         std::__tree_remove(root.__left_, &a);
1078 
1079         assert(std::__tree_invariant(root.__left_));
1080 
1081         assert(root.__parent_ == 0);
1082         assert(root.__left_ == &b);
1083         assert(root.__right_ == 0);
1084         assert(root.__is_black_ == false);
1085 
1086         assert(b.__parent_ == &root);
1087         assert(b.__left_ == 0);
1088         assert(b.__right_ == 0);
1089         assert(b.__is_black_ == true);
1090 
1091         std::__tree_remove(root.__left_, &b);
1092 
1093         assert(std::__tree_invariant(root.__left_));
1094 
1095         assert(root.__parent_ == 0);
1096         assert(root.__left_ == 0);
1097         assert(root.__right_ == 0);
1098         assert(root.__is_black_ == false);
1099     }
1100 }
1101 
1102 void
1103 test3()
1104 {
1105     Node root;
1106     Node a;
1107     Node b;
1108     Node c;
1109     Node d;
1110     Node e;
1111     Node f;
1112     Node g;
1113     Node h;
1114 
1115     root.__left_ = &e;
1116 
1117     e.__parent_ = &root;
1118     e.__left_ = &c;
1119     e.__right_ = &g;
1120     e.__is_black_ = true;
1121 
1122     c.__parent_ = &e;
1123     c.__left_ = &b;
1124     c.__right_ = &d;
1125     c.__is_black_ = false;
1126 
1127     g.__parent_ = &e;
1128     g.__left_ = &f;
1129     g.__right_ = &h;
1130     g.__is_black_ = false;
1131 
1132     b.__parent_ = &c;
1133     b.__left_ = &a;
1134     b.__right_ = 0;
1135     b.__is_black_ = true;
1136 
1137     d.__parent_ = &c;
1138     d.__left_ = 0;
1139     d.__right_ = 0;
1140     d.__is_black_ = true;
1141 
1142     f.__parent_ = &g;
1143     f.__left_ = 0;
1144     f.__right_ = 0;
1145     f.__is_black_ = true;
1146 
1147     h.__parent_ = &g;
1148     h.__left_ = 0;
1149     h.__right_ = 0;
1150     h.__is_black_ = true;
1151 
1152     a.__parent_ = &b;
1153     a.__left_ = 0;
1154     a.__right_ = 0;
1155     a.__is_black_ = false;
1156 
1157     assert(std::__tree_invariant(root.__left_));
1158 
1159     std::__tree_remove(root.__left_, &h);
1160 
1161     assert(std::__tree_invariant(root.__left_));
1162 
1163     assert(root.__parent_ == 0);
1164     assert(root.__left_ == &e);
1165     assert(root.__right_ == 0);
1166     assert(root.__is_black_ == false);
1167 
1168     assert(e.__parent_ == &root);
1169     assert(e.__left_ == &c);
1170     assert(e.__right_ == &g);
1171     assert(e.__is_black_ == true);
1172 
1173     assert(c.__parent_ == &e);
1174     assert(c.__left_ == &b);
1175     assert(c.__right_ == &d);
1176     assert(c.__is_black_ == false);
1177 
1178     assert(g.__parent_ == &e);
1179     assert(g.__left_ == &f);
1180     assert(g.__right_ == 0);
1181     assert(g.__is_black_ == true);
1182 
1183     assert(b.__parent_ == &c);
1184     assert(b.__left_ == &a);
1185     assert(b.__right_ == 0);
1186     assert(b.__is_black_ == true);
1187 
1188     assert(a.__parent_ == &b);
1189     assert(a.__left_ == 0);
1190     assert(a.__right_ == 0);
1191     assert(a.__is_black_ == false);
1192 
1193     assert(d.__parent_ == &c);
1194     assert(d.__left_ == 0);
1195     assert(d.__right_ == 0);
1196     assert(d.__is_black_ == true);
1197 
1198     assert(f.__parent_ == &g);
1199     assert(f.__left_ == 0);
1200     assert(f.__right_ == 0);
1201     assert(f.__is_black_ == false);
1202 
1203     std::__tree_remove(root.__left_, &g);
1204 
1205     assert(std::__tree_invariant(root.__left_));
1206 
1207     assert(root.__parent_ == 0);
1208     assert(root.__left_ == &e);
1209     assert(root.__right_ == 0);
1210     assert(root.__is_black_ == false);
1211 
1212     assert(e.__parent_ == &root);
1213     assert(e.__left_ == &c);
1214     assert(e.__right_ == &f);
1215     assert(e.__is_black_ == true);
1216 
1217     assert(c.__parent_ == &e);
1218     assert(c.__left_ == &b);
1219     assert(c.__right_ == &d);
1220     assert(c.__is_black_ == false);
1221 
1222     assert(b.__parent_ == &c);
1223     assert(b.__left_ == &a);
1224     assert(b.__right_ == 0);
1225     assert(b.__is_black_ == true);
1226 
1227     assert(a.__parent_ == &b);
1228     assert(a.__left_ == 0);
1229     assert(a.__right_ == 0);
1230     assert(a.__is_black_ == false);
1231 
1232     assert(d.__parent_ == &c);
1233     assert(d.__left_ == 0);
1234     assert(d.__right_ == 0);
1235     assert(d.__is_black_ == true);
1236 
1237     assert(f.__parent_ == &e);
1238     assert(f.__left_ == 0);
1239     assert(f.__right_ == 0);
1240     assert(f.__is_black_ == true);
1241 
1242     std::__tree_remove(root.__left_, &f);
1243 
1244     assert(std::__tree_invariant(root.__left_));
1245 
1246     assert(root.__parent_ == 0);
1247     assert(root.__left_ == &c);
1248     assert(root.__right_ == 0);
1249     assert(root.__is_black_ == false);
1250 
1251     assert(c.__parent_ == &root);
1252     assert(c.__left_ == &b);
1253     assert(c.__right_ == &e);
1254     assert(c.__is_black_ == true);
1255 
1256     assert(b.__parent_ == &c);
1257     assert(b.__left_ == &a);
1258     assert(b.__right_ == 0);
1259     assert(b.__is_black_ == true);
1260 
1261     assert(e.__parent_ == &c);
1262     assert(e.__left_ == &d);
1263     assert(e.__right_ == 0);
1264     assert(e.__is_black_ == true);
1265 
1266     assert(a.__parent_ == &b);
1267     assert(a.__left_ == 0);
1268     assert(a.__right_ == 0);
1269     assert(a.__is_black_ == false);
1270 
1271     assert(d.__parent_ == &e);
1272     assert(d.__left_ == 0);
1273     assert(d.__right_ == 0);
1274     assert(d.__is_black_ == false);
1275 
1276     std::__tree_remove(root.__left_, &e);
1277 
1278     assert(std::__tree_invariant(root.__left_));
1279 
1280     assert(root.__parent_ == 0);
1281     assert(root.__left_ == &c);
1282     assert(root.__right_ == 0);
1283     assert(root.__is_black_ == false);
1284 
1285     assert(c.__parent_ == &root);
1286     assert(c.__left_ == &b);
1287     assert(c.__right_ == &d);
1288     assert(c.__is_black_ == true);
1289 
1290     assert(b.__parent_ == &c);
1291     assert(b.__left_ == &a);
1292     assert(b.__right_ == 0);
1293     assert(b.__is_black_ == true);
1294 
1295     assert(a.__parent_ == &b);
1296     assert(a.__left_ == 0);
1297     assert(a.__right_ == 0);
1298     assert(a.__is_black_ == false);
1299 
1300     assert(d.__parent_ == &c);
1301     assert(d.__left_ == 0);
1302     assert(d.__right_ == 0);
1303     assert(d.__is_black_ == true);
1304 
1305     std::__tree_remove(root.__left_, &d);
1306 
1307     assert(std::__tree_invariant(root.__left_));
1308 
1309     assert(root.__parent_ == 0);
1310     assert(root.__left_ == &b);
1311     assert(root.__right_ == 0);
1312     assert(root.__is_black_ == false);
1313 
1314     assert(b.__parent_ == &root);
1315     assert(b.__left_ == &a);
1316     assert(b.__right_ == &c);
1317     assert(b.__is_black_ == true);
1318 
1319     assert(a.__parent_ == &b);
1320     assert(a.__left_ == 0);
1321     assert(a.__right_ == 0);
1322     assert(a.__is_black_ == true);
1323 
1324     assert(c.__parent_ == &b);
1325     assert(c.__left_ == 0);
1326     assert(c.__right_ == 0);
1327     assert(c.__is_black_ == true);
1328 
1329     std::__tree_remove(root.__left_, &c);
1330 
1331     assert(std::__tree_invariant(root.__left_));
1332 
1333     assert(root.__parent_ == 0);
1334     assert(root.__left_ == &b);
1335     assert(root.__right_ == 0);
1336     assert(root.__is_black_ == false);
1337 
1338     assert(b.__parent_ == &root);
1339     assert(b.__left_ == &a);
1340     assert(b.__right_ == 0);
1341     assert(b.__is_black_ == true);
1342 
1343     assert(a.__parent_ == &b);
1344     assert(a.__left_ == 0);
1345     assert(a.__right_ == 0);
1346     assert(a.__is_black_ == false);
1347 
1348     std::__tree_remove(root.__left_, &b);
1349 
1350     assert(std::__tree_invariant(root.__left_));
1351 
1352     assert(root.__parent_ == 0);
1353     assert(root.__left_ == &a);
1354     assert(root.__right_ == 0);
1355     assert(root.__is_black_ == false);
1356 
1357     assert(a.__parent_ == &root);
1358     assert(a.__left_ == 0);
1359     assert(a.__right_ == 0);
1360     assert(a.__is_black_ == true);
1361 
1362     std::__tree_remove(root.__left_, &a);
1363 
1364     assert(std::__tree_invariant(root.__left_));
1365 
1366     assert(root.__parent_ == 0);
1367     assert(root.__left_ == 0);
1368     assert(root.__right_ == 0);
1369     assert(root.__is_black_ == false);
1370 }
1371 
1372 void
1373 test4()
1374 {
1375     Node root;
1376     Node a;
1377     Node b;
1378     Node c;
1379     Node d;
1380     Node e;
1381     Node f;
1382     Node g;
1383     Node h;
1384 
1385     root.__left_ = &d;
1386 
1387     d.__parent_ = &root;
1388     d.__left_ = &b;
1389     d.__right_ = &f;
1390     d.__is_black_ = true;
1391 
1392     b.__parent_ = &d;
1393     b.__left_ = &a;
1394     b.__right_ = &c;
1395     b.__is_black_ = false;
1396 
1397     f.__parent_ = &d;
1398     f.__left_ = &e;
1399     f.__right_ = &g;
1400     f.__is_black_ = false;
1401 
1402     a.__parent_ = &b;
1403     a.__left_ = 0;
1404     a.__right_ = 0;
1405     a.__is_black_ = true;
1406 
1407     c.__parent_ = &b;
1408     c.__left_ = 0;
1409     c.__right_ = 0;
1410     c.__is_black_ = true;
1411 
1412     e.__parent_ = &f;
1413     e.__left_ = 0;
1414     e.__right_ = 0;
1415     e.__is_black_ = true;
1416 
1417     g.__parent_ = &f;
1418     g.__left_ = 0;
1419     g.__right_ = &h;
1420     g.__is_black_ = true;
1421 
1422     h.__parent_ = &g;
1423     h.__left_ = 0;
1424     h.__right_ = 0;
1425     h.__is_black_ = false;
1426 
1427     assert(std::__tree_invariant(root.__left_));
1428 
1429     std::__tree_remove(root.__left_, &a);
1430 
1431     assert(std::__tree_invariant(root.__left_));
1432 
1433     assert(root.__parent_ == 0);
1434     assert(root.__left_ == &d);
1435     assert(root.__right_ == 0);
1436     assert(root.__is_black_ == false);
1437 
1438     assert(d.__parent_ == &root);
1439     assert(d.__left_ == &b);
1440     assert(d.__right_ == &f);
1441     assert(d.__is_black_ == true);
1442 
1443     assert(b.__parent_ == &d);
1444     assert(b.__left_ == 0);
1445     assert(b.__right_ == &c);
1446     assert(b.__is_black_ == true);
1447 
1448     assert(f.__parent_ == &d);
1449     assert(f.__left_ == &e);
1450     assert(f.__right_ == &g);
1451     assert(f.__is_black_ == false);
1452 
1453     assert(c.__parent_ == &b);
1454     assert(c.__left_ == 0);
1455     assert(c.__right_ == 0);
1456     assert(c.__is_black_ == false);
1457 
1458     assert(e.__parent_ == &f);
1459     assert(e.__left_ == 0);
1460     assert(e.__right_ == 0);
1461     assert(e.__is_black_ == true);
1462 
1463     assert(g.__parent_ == &f);
1464     assert(g.__left_ == 0);
1465     assert(g.__right_ == &h);
1466     assert(g.__is_black_ == true);
1467 
1468     assert(h.__parent_ == &g);
1469     assert(h.__left_ == 0);
1470     assert(h.__right_ == 0);
1471     assert(h.__is_black_ == false);
1472 
1473     std::__tree_remove(root.__left_, &b);
1474 
1475     assert(std::__tree_invariant(root.__left_));
1476 
1477     assert(root.__parent_ == 0);
1478     assert(root.__left_ == &d);
1479     assert(root.__right_ == 0);
1480     assert(root.__is_black_ == false);
1481 
1482     assert(d.__parent_ == &root);
1483     assert(d.__left_ == &c);
1484     assert(d.__right_ == &f);
1485     assert(d.__is_black_ == true);
1486 
1487     assert(c.__parent_ == &d);
1488     assert(c.__left_ == 0);
1489     assert(c.__right_ == 0);
1490     assert(c.__is_black_ == true);
1491 
1492     assert(f.__parent_ == &d);
1493     assert(f.__left_ == &e);
1494     assert(f.__right_ == &g);
1495     assert(f.__is_black_ == false);
1496 
1497     assert(e.__parent_ == &f);
1498     assert(e.__left_ == 0);
1499     assert(e.__right_ == 0);
1500     assert(e.__is_black_ == true);
1501 
1502     assert(g.__parent_ == &f);
1503     assert(g.__left_ == 0);
1504     assert(g.__right_ == &h);
1505     assert(g.__is_black_ == true);
1506 
1507     assert(h.__parent_ == &g);
1508     assert(h.__left_ == 0);
1509     assert(h.__right_ == 0);
1510     assert(h.__is_black_ == false);
1511 
1512     std::__tree_remove(root.__left_, &c);
1513 
1514     assert(std::__tree_invariant(root.__left_));
1515 
1516     assert(root.__parent_ == 0);
1517     assert(root.__left_ == &f);
1518     assert(root.__right_ == 0);
1519     assert(root.__is_black_ == false);
1520 
1521     assert(f.__parent_ == &root);
1522     assert(f.__left_ == &d);
1523     assert(f.__right_ == &g);
1524     assert(f.__is_black_ == true);
1525 
1526     assert(d.__parent_ == &f);
1527     assert(d.__left_ == 0);
1528     assert(d.__right_ == &e);
1529     assert(d.__is_black_ == true);
1530 
1531     assert(g.__parent_ == &f);
1532     assert(g.__left_ == 0);
1533     assert(g.__right_ == &h);
1534     assert(g.__is_black_ == true);
1535 
1536     assert(e.__parent_ == &d);
1537     assert(e.__left_ == 0);
1538     assert(e.__right_ == 0);
1539     assert(e.__is_black_ == false);
1540 
1541     assert(h.__parent_ == &g);
1542     assert(h.__left_ == 0);
1543     assert(h.__right_ == 0);
1544     assert(h.__is_black_ == false);
1545 
1546     std::__tree_remove(root.__left_, &d);
1547 
1548     assert(std::__tree_invariant(root.__left_));
1549 
1550     assert(root.__parent_ == 0);
1551     assert(root.__left_ == &f);
1552     assert(root.__right_ == 0);
1553     assert(root.__is_black_ == false);
1554 
1555     assert(f.__parent_ == &root);
1556     assert(f.__left_ == &e);
1557     assert(f.__right_ == &g);
1558     assert(f.__is_black_ == true);
1559 
1560     assert(e.__parent_ == &f);
1561     assert(e.__left_ == 0);
1562     assert(e.__right_ == 0);
1563     assert(e.__is_black_ == true);
1564 
1565     assert(g.__parent_ == &f);
1566     assert(g.__left_ == 0);
1567     assert(g.__right_ == &h);
1568     assert(g.__is_black_ == true);
1569 
1570     assert(h.__parent_ == &g);
1571     assert(h.__left_ == 0);
1572     assert(h.__right_ == 0);
1573     assert(h.__is_black_ == false);
1574 
1575     std::__tree_remove(root.__left_, &e);
1576 
1577     assert(std::__tree_invariant(root.__left_));
1578 
1579     assert(root.__parent_ == 0);
1580     assert(root.__left_ == &g);
1581     assert(root.__right_ == 0);
1582     assert(root.__is_black_ == false);
1583 
1584     assert(g.__parent_ == &root);
1585     assert(g.__left_ == &f);
1586     assert(g.__right_ == &h);
1587     assert(g.__is_black_ == true);
1588 
1589     assert(f.__parent_ == &g);
1590     assert(f.__left_ == 0);
1591     assert(f.__right_ == 0);
1592     assert(f.__is_black_ == true);
1593 
1594     assert(h.__parent_ == &g);
1595     assert(h.__left_ == 0);
1596     assert(h.__right_ == 0);
1597     assert(h.__is_black_ == true);
1598 
1599     std::__tree_remove(root.__left_, &f);
1600 
1601     assert(std::__tree_invariant(root.__left_));
1602 
1603     assert(root.__parent_ == 0);
1604     assert(root.__left_ == &g);
1605     assert(root.__right_ == 0);
1606     assert(root.__is_black_ == false);
1607 
1608     assert(g.__parent_ == &root);
1609     assert(g.__left_ == 0);
1610     assert(g.__right_ == &h);
1611     assert(g.__is_black_ == true);
1612 
1613     assert(h.__parent_ == &g);
1614     assert(h.__left_ == 0);
1615     assert(h.__right_ == 0);
1616     assert(h.__is_black_ == false);
1617 
1618     std::__tree_remove(root.__left_, &g);
1619 
1620     assert(std::__tree_invariant(root.__left_));
1621 
1622     assert(root.__parent_ == 0);
1623     assert(root.__left_ == &h);
1624     assert(root.__right_ == 0);
1625     assert(root.__is_black_ == false);
1626 
1627     assert(h.__parent_ == &root);
1628     assert(h.__left_ == 0);
1629     assert(h.__right_ == 0);
1630     assert(h.__is_black_ == true);
1631 
1632     std::__tree_remove(root.__left_, &h);
1633 
1634     assert(std::__tree_invariant(root.__left_));
1635 
1636     assert(root.__parent_ == 0);
1637     assert(root.__left_ == 0);
1638     assert(root.__right_ == 0);
1639     assert(root.__is_black_ == false);
1640 }
1641 
1642 int main()
1643 {
1644     test1();
1645     test2();
1646     test3();
1647     test4();
1648 }
1649