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