The initial Binary Search Tree Empty tree The initial Splay Tree Empty tree Inserted 64000 nodes The first 40 nodes of the Binary Search Tree [ 453966129, 0 ][ 392049629, 1 ][ 1531316372, 1 ][ 115761792, 2 ] [ 451218181, 2 ][ 675555458, 2 ][ 1554408035, 2 ][ 96877493, 3 ] [ 121003408, 3 ][ 402434934, 3 ][ 451885507, 3 ][ 661111487, 3 ] [ 1131420699, 3 ][ 1552057859, 3 ][ 1919448991, 3 ][ 25985468, 4 ] [ 99627126, 4 ][ 117868878, 4 ][ 220165216, 4 ][ 399855813, 4 ] [ 414670896, 4 ][ 451545055, 4 ][ 451978379, 4 ][ 562239357, 4 ] [ 662562527, 4 ][ 1048516211, 4 ][ 1291888468, 4 ][ 1535083445, 4 ] [ 1553297246, 4 ][ 1787353214, 4 ][ 2091931086, 4 ][ 23633700, 5 ] [ 31523067, 5 ][ 98142914, 5 ][ 108924556, 5 ][ 116294677, 5 ] [ 118112897, 5 ][ 215297550, 5 ][ 309872653, 5 ][ 396534619, 5 ] The first 40 nodes of the Splay Tree [ 1110396074, 0 ][ 1110387632, 1 ][ 1182364647, 1 ][ 828123364, 2 ] [ 1131127078, 2 ][ 1182412629, 2 ][ 634208085, 3 ][ 838805526, 3 ] [ 1131118986, 3 ][ 1142698232, 3 ][ 1929182863, 3 ][ 634188889, 4 ] [ 761989742, 4 ][ 828139666, 4 ][ 1107165652, 4 ][ 1121038125, 4 ] [ 1142688533, 4 ][ 1164647820, 4 ][ 1829447325, 4 ][ 1929214386, 4 ] [ 603200636, 5 ][ 649391864, 5 ][ 815909242, 5 ][ 832975398, 5 ] [ 1013399655, 5 ][ 1107948479, 5 ][ 1112882080, 5 ][ 1121043322, 5 ] [ 1133270868, 5 ][ 1164547645, 5 ][ 1173146970, 5 ][ 1262943196, 5 ] [ 1927179773, 5 ][ 1950446017, 5 ][ 442489351, 6 ][ 603278141, 6 ] [ 647795443, 6 ][ 649439557, 6 ][ 762009649, 6 ][ 823036003, 6 ] finding every 100th node finding every 50th node finding every 25th node Binary Search Tree Results Nr elements(N) = 64000 lg(N) = 15.9658 NrOps(M) Height IPL AveNodeDepth NrCompares(C) C/(MlgN) 64000 36 1215700 18.9953 1215700 1.1898 64100 36 1215700 18.9953 1217351 1.1895 64200 36 1215700 18.9953 1219187 1.1894 64300 36 1215700 18.9953 1221149 1.1895 64400 36 1215700 18.9953 1223223 1.1897 64500 36 1215700 18.9953 1225430 1.1900 64600 36 1215700 18.9953 1227629 1.1903 64700 36 1215700 18.9953 1229394 1.1901 64800 36 1215700 18.9953 1231090 1.1899 64900 36 1215700 18.9953 1232863 1.1898 65000 36 1215700 18.9953 1234743 1.1898 65100 36 1215700 18.9953 1236720 1.1899 65200 36 1215700 18.9953 1238722 1.1900 65300 36 1215700 18.9953 1240834 1.1902 65400 36 1215700 18.9953 1242990 1.1904 65500 36 1215700 18.9953 1245098 1.1906 65600 36 1215700 18.9953 1247329 1.1909 65700 36 1215700 18.9953 1249468 1.1912 65800 36 1215700 18.9953 1251660 1.1914 65900 36 1215700 18.9953 1253933 1.1918 66000 36 1215700 18.9953 1255422 1.1914 66100 36 1215700 18.9953 1257054 1.1911 66200 36 1215700 18.9953 1258725 1.1909 66300 36 1215700 18.9953 1260479 1.1908 66400 36 1215700 18.9953 1262298 1.1907 66500 36 1215700 18.9953 1264133 1.1906 66600 36 1215700 18.9953 1266022 1.1906 66700 36 1215700 18.9953 1268041 1.1907 66800 36 1215700 18.9953 1269994 1.1908 66900 36 1215700 18.9953 1271976 1.1909 67000 36 1215700 18.9953 1273942 1.1909 67100 36 1215700 18.9953 1276028 1.1911 67200 36 1215700 18.9953 1278131 1.1913 67300 36 1215700 18.9953 1280176 1.1914 67400 36 1215700 18.9953 1282299 1.1916 67500 36 1215700 18.9953 1284464 1.1919 67600 36 1215700 18.9953 1286587 1.1921 67700 36 1215700 18.9953 1288708 1.1923 67800 36 1215700 18.9953 1290908 1.1925 67900 36 1215700 18.9953 1293103 1.1928 68000 36 1215700 18.9953 1295229 1.1930 68100 36 1215700 18.9953 1297430 1.1933 68200 36 1215700 18.9953 1299597 1.1935 68300 36 1215700 18.9953 1301793 1.1938 68400 36 1215700 18.9953 1304002 1.1941 68480 36 1215700 18.9953 1305746 1.1943 Splay Tree Results Nr elements(N) = 64000 lg(N) = 15.9658 NrOps(M) Height IPL AveNodeDepth NrCompares(C) C/(MlgN) 64000 53 1741755 27.2149 1062003 1.0393 64100 52 1441708 22.5267 1063756 1.0394 64200 49 1421228 22.2067 1065527 1.0395 64300 48 1425633 22.2755 1067152 1.0395 64400 57 1412443 22.0694 1068832 1.0395 64500 49 1357443 21.2100 1070428 1.0395 64600 52 1380317 21.5675 1071904 1.0393 64700 46 1373818 21.4659 1073164 1.0389 64800 43 1357042 21.2038 1074508 1.0386 64900 43 1341296 20.9578 1075785 1.0382 65000 45 1338298 20.9109 1077087 1.0379 65100 42 1362578 21.2903 1078325 1.0375 65200 46 1372339 21.4428 1079645 1.0372 65300 46 1341877 20.9668 1080957 1.0368 65400 43 1355397 21.1781 1082282 1.0365 65500 44 1323432 20.6786 1083592 1.0362 65600 44 1332247 20.8164 1084909 1.0359 65700 50 1463483 22.8669 1086164 1.0355 65800 45 1313937 20.5303 1087413 1.0351 65900 52 1354584 21.1654 1088631 1.0347 66000 44 1309859 20.4665 1089922 1.0343 66100 53 1492021 23.3128 1091266 1.0340 66200 44 1321788 20.6529 1092609 1.0338 66300 43 1318264 20.5979 1093920 1.0334 66400 48 1371675 21.4324 1095252 1.0331 66500 45 1324039 20.6881 1096508 1.0328 66600 45 1353776 21.1528 1097847 1.0325 66700 43 1282299 20.0359 1099179 1.0322 66800 53 1435522 22.4300 1100507 1.0319 66900 45 1364682 21.3232 1101810 1.0316 67000 48 1330147 20.7835 1103178 1.0313 67100 46 1329051 20.7664 1104553 1.0310 67200 49 1463152 22.8618 1105879 1.0307 67300 46 1369934 21.4052 1107172 1.0304 67400 44 1362386 21.2873 1108468 1.0301 67500 45 1322485 20.6638 1109799 1.0298 67600 41 1278930 19.9833 1111148 1.0295 67700 41 1286702 20.1047 1112480 1.0292 67800 44 1373497 21.4609 1113830 1.0290 67900 45 1308593 20.4468 1115157 1.0287 68000 46 1323657 20.6821 1116512 1.0284 68100 51 1359601 21.2438 1117796 1.0281 68200 46 1302893 20.3577 1119080 1.0277 68300 45 1320294 20.6296 1120332 1.0274 68400 45 1305416 20.3971 1121604 1.0271 68480 46 1277749 19.9648 1122560 1.0267 The first 40 nodes of the Binary Search Tree [ 453966129, 0 ][ 392049629, 1 ][ 1531316372, 1 ][ 115761792, 2 ] [ 451218181, 2 ][ 675555458, 2 ][ 1554408035, 2 ][ 96877493, 3 ] [ 121003408, 3 ][ 402434934, 3 ][ 451885507, 3 ][ 661111487, 3 ] [ 1131420699, 3 ][ 1552057859, 3 ][ 1919448991, 3 ][ 25985468, 4 ] [ 99627126, 4 ][ 117868878, 4 ][ 220165216, 4 ][ 399855813, 4 ] [ 414670896, 4 ][ 451545055, 4 ][ 451978379, 4 ][ 562239357, 4 ] [ 662562527, 4 ][ 1048516211, 4 ][ 1291888468, 4 ][ 1535083445, 4 ] [ 1553297246, 4 ][ 1787353214, 4 ][ 2091931086, 4 ][ 23633700, 5 ] [ 31523067, 5 ][ 98142914, 5 ][ 108924556, 5 ][ 116294677, 5 ] [ 118112897, 5 ][ 215297550, 5 ][ 309872653, 5 ][ 396534619, 5 ] The first 40 nodes of the Splay Tree [ 1110396074, 0 ][ 420926159, 1 ][ 1497318744, 1 ][ 175812515, 2 ] [ 574355167, 2 ][ 1348343806, 2 ][ 1505518866, 2 ][ 34378772, 3 ] [ 210691255, 3 ][ 504187955, 3 ][ 892606765, 3 ][ 1162070416, 3 ] [ 1369651225, 3 ][ 1503219625, 3 ][ 1908290802, 3 ][ 1322583, 4 ] [ 46102327, 4 ][ 207778102, 4 ][ 403303100, 4 ][ 424613474, 4 ] [ 551123132, 4 ][ 778071644, 4 ][ 1078062558, 4 ][ 1130655494, 4 ] [ 1242790835, 4 ][ 1368011150, 4 ][ 1486298877, 4 ][ 1498649486, 4 ] [ 1504372411, 4 ][ 1756878070, 4 ][ 1968308680, 4 ][ 302376, 5 ] [ 32264134, 5 ][ 34823965, 5 ][ 62757876, 5 ][ 195423322, 5 ] [ 210310967, 5 ][ 243143086, 5 ][ 408826770, 5 ][ 423859261, 5 ]