******************************************************************************** EVEN PC ******************************************************************************** SAMPLE 1 -------- EVEN PC n = 50 Smallest gap = 79, largest gap = 238 Keys to insert: 7156 346 5355 4250 4762 4394 3831 2539 2150 4604 5804 6200 4064 4999 2348 1325 2712 1099 3727 5549 3941 1439 7253 893 5166 3597 780 6943 1768 6294 1238 5986 7077 699 6716 3174 6822 7771 7469 446 2936 3351 3443 536 5633 1557 1917 7597 117 6515 +++ Preorder traversal of initial tree 7156 346 117 5355 4250 3831 2539 2150 1325 1099 893 780 699 446 536 1238 1439 1768 1557 1917 2348 2712 3727 3597 3174 2936 3351 3443 4064 3941 4762 4394 4604 4999 5166 5804 5549 5633 6200 5986 6943 6294 6716 6515 6822 7077 7253 7771 7469 7597 +++ Finding closest neighbor x = 7077, y = 7156, gap = 79 +++ Bringing neighboring key to child position *** Case 1: x is a descendent of y Number of rotations = 5 y = 7156, y -> L = 7077, y -> R = 7253 +++ Preorder traversal of final tree 7156 7077 6943 6200 5804 5355 346 117 4250 3831 2539 2150 1325 1099 893 780 699 446 536 1238 1439 1768 1557 1917 2348 2712 3727 3597 3174 2936 3351 3443 4064 3941 4762 4394 4604 4999 5166 5549 5633 5986 6294 6716 6515 6822 7253 7771 7469 7597 ******************************************************************************** SAMPLE 2 -------- EVEN PC n = 50 Smallest gap = 101, largest gap = 240 Keys to insert: 412 8525 8028 3254 1569 1345 5850 2834 8222 139 274 3972 5439 7557 1953 627 3744 6775 7093 4305 4516 2448 6347 5202 1176 5957 6184 5647 2647 3065 6918 513 8378 3577 2327 806 7718 3444 4938 4131 7332 1737 5050 2188 6472 7837 936 6655 4717 1467 +++ Preorder traversal of initial tree 412 139 274 8525 8028 3254 1569 1345 627 513 1176 806 936 1467 2834 1953 1737 2448 2327 2188 2647 3065 5850 3972 3744 3577 3444 5439 4305 4131 4516 5202 4938 4717 5050 5647 7557 6775 6347 5957 6184 6472 6655 7093 6918 7332 7718 7837 8222 8378 +++ Finding closest neighbor x = 412, y = 513, gap = 101 +++ Bringing neighboring key to child position *** Case 2: y is a descendent of x *** Rotation at root Number of rotations = 7 y = 513, y -> L = 412, y -> R = 627 +++ Preorder traversal of final tree 513 412 139 274 627 1345 1176 806 936 1569 1467 3254 2834 1953 1737 2448 2327 2188 2647 3065 8028 5850 3972 3744 3577 3444 5439 4305 4131 4516 5202 4938 4717 5050 5647 7557 6775 6347 5957 6184 6472 6655 7093 6918 7332 7718 7837 8525 8222 8378 ******************************************************************************** ODD PC ******************************************************************************** SAMPLE 1 -------- ODD PC n = 50 Smallest gap = 48, largest gap = 195 Keys to insert: 2493 5959 125 1552 1479 1916 1723 2182 5783 5034 3792 421 4093 1125 585 2375 3709 5286 3286 984 706 1979 4324 3466 4170 4693 3123 1314 2688 254 4642 473 5127 4496 4218 5188 2239 4793 3872 5385 2873 5577 853 5631 3979 2997 1620 4881 2133 3550 +++ Preorder traversal of initial tree 2493 125 1552 1479 421 254 1125 585 473 984 706 853 1314 1916 1723 1620 2182 1979 2133 2375 2239 5959 5783 5034 3792 3709 3286 3123 2688 2873 2997 3466 3550 4093 3872 3979 4324 4170 4218 4693 4642 4496 4793 4881 5286 5127 5188 5385 5577 5631 +++ Finding farthest neighbor x = 2493, y = 2688, gap = 195 +++ Bringing neighboring key to child position *** Case 1: y is a descendent of x Number of rotations = 7 x = 2493, x -> L = 125, x -> R = 2688 +++ Preorder traversal of final tree 2493 125 1552 1479 421 254 1125 585 473 984 706 853 1314 1916 1723 1620 2182 1979 2133 2375 2239 2688 3123 2873 2997 3286 3709 3466 3550 3792 5034 4093 3872 3979 4324 4170 4218 4693 4642 4496 4793 4881 5783 5286 5127 5188 5385 5577 5631 5959 ******************************************************************************** SAMPLE 2 -------- ODD PC n = 50 Smallest gap = 47, largest gap = 190 Keys to insert: 3311 514 4244 2284 5141 3498 2035 2345 2974 2721 5840 187 2237 4062 730 2144 1970 3619 4887 3121 1603 276 5695 5388 5450 5270 4568 5610 343 4714 3769 971 653 3921 1844 1135 5022 2087 1771 834 4382 2796 1376 4469 1293 1470 2458 5951 3691 2564 +++ Preorder traversal of initial tree 3311 514 187 276 343 2284 2035 730 653 1970 1603 971 834 1135 1376 1293 1470 1844 1771 2237 2144 2087 2345 2974 2721 2458 2564 2796 3121 4244 3498 4062 3619 3769 3691 3921 5141 4887 4568 4382 4469 4714 5022 5840 5695 5388 5270 5450 5610 5951 +++ Finding farthest neighbor x = 3121, y = 3311, gap = 190 +++ Bringing neighboring key to child position *** Case 2: x is a descendent of y *** Rotation at root Number of rotations = 5 x = 3121, x -> L = 2974, x -> R = 3311 +++ Preorder traversal of final tree 3121 2974 2345 2284 514 187 276 343 2035 730 653 1970 1603 971 834 1135 1376 1293 1470 1844 1771 2237 2144 2087 2721 2458 2564 2796 3311 4244 3498 4062 3619 3769 3691 3921 5141 4887 4568 4382 4469 4714 5022 5840 5695 5388 5270 5450 5610 5951 ********************************************************************************