简介

作业：查找结构与排序方法
作业题目： BST 查找结构与折半查找方法的实现与实验比较
要求编写程序实现 BST 存储结构的建立（插入）、删除、查找和排序算法；实现折半查找算法；比较 BST 查找与折半查找方法的时间性能。
作业要求：
- 1．设计 BST 的左右链存储结构，并实现 BST 插入（建立）、删除、查找和排序算法。
- 2．实现折半查找算法。
- 3．实验比较：设计并产生实验测试数据，考察比较两种查找方法的时间性能，并与理论结果进行比较。以下具体做法可作为参考：
  - （1）第 1 组测试数据： n=1024 个已排序的整数序列（如 0 至 2048 之间的奇数）；第 2 组测试数据：第 1 组测试数据的随机序列。
  - （2）以上述两组测试数据作为输入，分别建立 BST 查找结构。
  - （3）编写程序计算所建的两棵 BST 的查找成功和查找失败的平均查找长度（主要是改造 Search 算法，对“比较”进行计数），并与理论结果比较。
  - （4）分别以上述 BST 查找结构的中序遍历序列作为折半查找算法的输入，编写程序分别计算折半查找的查找成功和查找失败的平均查找长度，并与理论结果比较。
  - （5）以上实验能否说明：就平均性能而言， BST 的查找与折半查找差不多，为什么？

关于BST

二叉搜索树（Binary Search Tree）又称二叉查找树或二叉排序树。

它是一棵树，满足以下性质：

对于任何一个节点，它的左子树上的所有节点的权值都小于它的权值，它的右子树上的所有节点的权值都大于它的权值。
不存在权值相等的节点。（不存在重复节点）
BST中最小权值的节点是整棵树最左下的叶子节点。
BST中最大权值的节点是整棵树最右下的叶子节点。
将任何一个点看作Root节点，则这个点的左子树也是BST，右子树也是BST。

定义

二叉搜索树实际上是一个二叉链表，所以它的数据结构定义如下：

typedef struct BST_Node{//二叉树
    int data;//数据
    struct BST_Node *lc, *rc;//左右孩子
}BST_Node, *BST;

搜索与插入

搜索与插入是非常相似的，插入就是在做完搜索后进行插入节点。

这里需要知道，BST在插入后，新节点一定是叶子节点，不会破坏原有的树。所以它的逻辑非常简单。

这里介绍递归版本。

//递归查找二叉排序树,father为搜索当前节点的父节点,T为搜索的当前节点,key为搜索的关键字指针,p指向查找的结果
Status Search(BST T, BST father, int key, BST *p)
{
    if(!T)//查找的节点不存在
    {
        *p = father;
        return FALSE;
    }else if(key == T->data)//查找成功，返回当前节点
    {
        *p = T;
        return TRUE;
    }else if(key < T->data)
    {
        return Search(T->lc, T, key, p);//递归左儿子
    }else
    {
        return Search(T->rc, T, key, p);//递归右儿子
    }
}

就是利用性质1进行判断和递归。

删除

如果删除的节点只有左子树或只有右子树或为叶子节点。

如上图中的1（叶子节点），10（只有左子树），27（只有右子树）。

删除后为：

很明显，“子承父业”，子树继承父节点。这样仍然是一个BST，这里用到了性质5。

那如果是删除的是左右子树都存在的节点呢？

有两种方案：

找该节点的前驱替代该节点。
找该节点的后继替代该节点。

前驱和后继是什么呢，这是二叉树的中序遍历的知识。

在中序遍历序列中，该节点的前一个就是前驱节点，后一个就是后继节点。

比如，我们现在要删除7这个节点。根据中序遍历，它的前驱是6，后继是8。

发现了吗？6和8就是整棵树最接近7的值。

而中序遍历是一个严格单调递增的序列！

序列：1 4 6 7 8 10 15 27 35

现在，我们试试这两种方法：

完全符合BST的性质！

测试数据

第一组测试数据：in1.txt

n=1024 个已排序的整数序列(0 至 2048 之间的奇数)。

点击查看第一组数据

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 
33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 
65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 
97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 
129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 
161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 
193 195 197 199 201 203 205 207 209 211 213 215 217 219 221 223 
225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 
257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 
289 291 293 295 297 299 301 303 305 307 309 311 313 315 317 319 
321 323 325 327 329 331 333 335 337 339 341 343 345 347 349 351 
353 355 357 359 361 363 365 367 369 371 373 375 377 379 381 383 
385 387 389 391 393 395 397 399 401 403 405 407 409 411 413 415 
417 419 421 423 425 427 429 431 433 435 437 439 441 443 445 447 
449 451 453 455 457 459 461 463 465 467 469 471 473 475 477 479 
481 483 485 487 489 491 493 495 497 499 501 503 505 507 509 511 
513 515 517 519 521 523 525 527 529 531 533 535 537 539 541 543 
545 547 549 551 553 555 557 559 561 563 565 567 569 571 573 575 
577 579 581 583 585 587 589 591 593 595 597 599 601 603 605 607 
609 611 613 615 617 619 621 623 625 627 629 631 633 635 637 639 
641 643 645 647 649 651 653 655 657 659 661 663 665 667 669 671 
673 675 677 679 681 683 685 687 689 691 693 695 697 699 701 703 
705 707 709 711 713 715 717 719 721 723 725 727 729 731 733 735 
737 739 741 743 745 747 749 751 753 755 757 759 761 763 765 767 
769 771 773 775 777 779 781 783 785 787 789 791 793 795 797 799 
801 803 805 807 809 811 813 815 817 819 821 823 825 827 829 831 
833 835 837 839 841 843 845 847 849 851 853 855 857 859 861 863 
865 867 869 871 873 875 877 879 881 883 885 887 889 891 893 895 
897 899 901 903 905 907 909 911 913 915 917 919 921 923 925 927 
929 931 933 935 937 939 941 943 945 947 949 951 953 955 957 959 
961 963 965 967 969 971 973 975 977 979 981 983 985 987 989 991 
993 995 997 999 1001 1003 1005 1007 1009 1011 1013 1015 1017 1019 1021 1023 
1025 1027 1029 1031 1033 1035 1037 1039 1041 1043 1045 1047 1049 1051 1053 1055 
1057 1059 1061 1063 1065 1067 1069 1071 1073 1075 1077 1079 1081 1083 1085 1087 
1089 1091 1093 1095 1097 1099 1101 1103 1105 1107 1109 1111 1113 1115 1117 1119 
1121 1123 1125 1127 1129 1131 1133 1135 1137 1139 1141 1143 1145 1147 1149 1151 
1153 1155 1157 1159 1161 1163 1165 1167 1169 1171 1173 1175 1177 1179 1181 1183 
1185 1187 1189 1191 1193 1195 1197 1199 1201 1203 1205 1207 1209 1211 1213 1215 
1217 1219 1221 1223 1225 1227 1229 1231 1233 1235 1237 1239 1241 1243 1245 1247 
1249 1251 1253 1255 1257 1259 1261 1263 1265 1267 1269 1271 1273 1275 1277 1279 
1281 1283 1285 1287 1289 1291 1293 1295 1297 1299 1301 1303 1305 1307 1309 1311 
1313 1315 1317 1319 1321 1323 1325 1327 1329 1331 1333 1335 1337 1339 1341 1343 
1345 1347 1349 1351 1353 1355 1357 1359 1361 1363 1365 1367 1369 1371 1373 1375 
1377 1379 1381 1383 1385 1387 1389 1391 1393 1395 1397 1399 1401 1403 1405 1407 
1409 1411 1413 1415 1417 1419 1421 1423 1425 1427 1429 1431 1433 1435 1437 1439 
1441 1443 1445 1447 1449 1451 1453 1455 1457 1459 1461 1463 1465 1467 1469 1471 
1473 1475 1477 1479 1481 1483 1485 1487 1489 1491 1493 1495 1497 1499 1501 1503 
1505 1507 1509 1511 1513 1515 1517 1519 1521 1523 1525 1527 1529 1531 1533 1535 
1537 1539 1541 1543 1545 1547 1549 1551 1553 1555 1557 1559 1561 1563 1565 1567 
1569 1571 1573 1575 1577 1579 1581 1583 1585 1587 1589 1591 1593 1595 1597 1599 
1601 1603 1605 1607 1609 1611 1613 1615 1617 1619 1621 1623 1625 1627 1629 1631 
1633 1635 1637 1639 1641 1643 1645 1647 1649 1651 1653 1655 1657 1659 1661 1663 
1665 1667 1669 1671 1673 1675 1677 1679 1681 1683 1685 1687 1689 1691 1693 1695 
1697 1699 1701 1703 1705 1707 1709 1711 1713 1715 1717 1719 1721 1723 1725 1727 
1729 1731 1733 1735 1737 1739 1741 1743 1745 1747 1749 1751 1753 1755 1757 1759 
1761 1763 1765 1767 1769 1771 1773 1775 1777 1779 1781 1783 1785 1787 1789 1791 
1793 1795 1797 1799 1801 1803 1805 1807 1809 1811 1813 1815 1817 1819 1821 1823 
1825 1827 1829 1831 1833 1835 1837 1839 1841 1843 1845 1847 1849 1851 1853 1855 
1857 1859 1861 1863 1865 1867 1869 1871 1873 1875 1877 1879 1881 1883 1885 1887 
1889 1891 1893 1895 1897 1899 1901 1903 1905 1907 1909 1911 1913 1915 1917 1919 
1921 1923 1925 1927 1929 1931 1933 1935 1937 1939 1941 1943 1945 1947 1949 1951 
1953 1955 1957 1959 1961 1963 1965 1967 1969 1971 1973 1975 1977 1979 1981 1983 
1985 1987 1989 1991 1993 1995 1997 1999 2001 2003 2005 2007 2009 2011 2013 2015 
2017 2019 2021 2023 2025 2027 2029 2031 2033 2035 2037 2039 2041 2043 2045 2047

第二组测试数据：in2.txt

第 1 组测试数据的随机序列。

点击查看第二组数据

83 71 381 1801 1475 729 429 1373 677 1825 1171 995 1507 887 1491 983 
1895 1357 1463 633 1295 537 1661 307 585 189 27 569 525 879 655 445 
871 549 1691 913 135 1399 1303 63 519 1205 1275 531 1137 1611 1087 1211 
1449 1943 2041 1837 2027 1163 1143 1063 1051 1811 1557 57 1975 1637 577 821 
1697 1501 1665 241 1645 507 1061 2029 1341 763 1683 953 347 671 1065 997 
649 1153 1741 417 1239 1417 1121 1391 101 119 835 69 1517 803 315 791 
1973 353 1429 1331 517 1907 1765 1851 147 601 1281 253 1419 427 2003 257 
869 2005 1939 409 1703 383 207 1919 1577 1453 1115 441 1309 717 775 991 
1199 195 2047 211 287 1219 1435 931 1085 1339 313 557 741 1485 59 993 
1695 661 1263 5 431 2001 115 89 679 1597 103 233 317 1561 1001 939 
1343 425 1865 179 1277 107 1951 581 1513 1433 1439 935 1313 145 1959 799 
747 1997 947 571 597 1995 897 1007 87 259 271 1673 541 1215 161 1537 
1731 1307 1917 247 11 43 15 1655 1127 1285 575 561 1249 293 949 201 
681 925 1891 267 637 723 1067 2033 141 213 9 1255 1565 1971 1581 95 
719 721 495 1685 1173 1441 1745 237 1525 1571 785 755 509 165 439 1159 
971 1657 489 1675 945 1105 1047 491 907 705 1147 1839 79 1813 691 1261 
91 929 1413 411 1233 243 1041 641 41 631 725 331 547 593 899 1305 
1363 1559 793 607 483 1323 387 1335 451 1921 1873 1845 335 269 875 1193 
1333 1999 435 1607 1195 1617 217 1347 205 669 963 97 1337 1533 227 831 
1989 1867 453 311 1385 1679 1739 1109 1677 1299 339 1797 757 749 711 1379 
1101 447 1107 1755 197 449 1325 1641 1407 1139 845 639 701 2019 731 1053 
1479 1241 61 1083 919 7 1663 1155 1039 1567 553 1547 567 395 1487 285 
1133 1553 1465 1511 337 1819 471 511 321 235 281 765 743 155 1953 261 
1405 1925 1165 131 599 1817 2037 1633 1279 1505 1359 1805 853 1719 461 1787 
277 55 1019 369 1253 1947 1563 481 137 117 1897 1869 535 33 1177 985 
1689 1035 361 611 341 917 591 667 2025 1267 1103 645 249 1849 1411 1521 
783 65 1095 1225 1905 299 153 1377 283 635 1217 1469 1793 859 529 643 
979 1743 1355 1481 1585 319 1579 1157 1025 77 1021 1955 67 1831 1119 1823 
1301 351 405 735 1551 1859 893 1227 873 617 1043 515 559 1709 397 1937 
1457 23 1297 771 1649 1751 1221 2035 1763 1169 1777 1317 781 1619 1843 1081 
1135 1835 1711 1515 1769 1815 647 1059 1005 1915 1519 881 1729 1245 759 709 
789 1721 1483 1933 903 867 847 149 1259 1759 1031 1237 2015 545 673 1847 
1671 81 493 1853 1283 1635 1351 1841 1057 1023 175 911 891 1543 1791 699 
1727 1129 157 817 1669 1381 1111 1901 1497 965 1699 1789 1969 777 1027 1965 
1091 1799 563 305 1113 1629 1011 889 1941 1321 1123 1887 795 363 1353 801 
1749 129 1017 769 663 1071 215 579 181 469 1393 1459 501 1889 297 1201 
1207 1857 1209 745 683 1957 345 565 1875 1613 183 839 615 883 1131 1809 
209 1883 533 1775 1387 1319 1329 2007 1983 1033 1861 1451 377 239 703 1415 
1311 851 521 35 861 1767 1723 941 139 1967 849 921 539 475 1181 1009 
111 1499 1269 1345 697 1803 797 989 355 779 37 1421 2009 327 13 1125 
371 1627 961 1539 497 837 17 623 1647 503 1509 589 19 245 1707 815 
1573 365 221 1985 1141 959 1979 1397 457 1079 385 707 459 1401 1623 391 
1715 21 29 1045 31 1927 951 1893 203 523 123 359 2043 937 987 915 
51 1151 1931 809 609 1735 1667 455 1467 1713 1461 1183 1949 479 715 1747 
905 863 1725 109 1175 1 173 1631 1289 999 1093 169 1651 751 657 1871 
1149 1029 877 685 443 733 975 1231 543 1575 289 1371 1687 127 1003 675 
605 651 1589 413 379 423 1427 1069 1293 1569 421 367 1389 753 1443 477 
333 1621 927 1473 291 1423 1361 1049 73 767 49 1431 3 713 1549 1287 
1601 583 99 1073 1555 1779 1273 1761 143 1753 1717 2013 1681 957 901 1899 
467 693 1903 1493 193 125 587 219 473 1013 969 1197 407 349 1409 133 
279 2031 1545 1885 1529 1257 1243 1855 1771 923 843 1807 1821 225 75 433 
613 1527 659 1603 1531 329 885 627 827 485 301 1535 265 1583 199 343 
2017 393 813 1963 375 401 1495 1327 1785 555 1877 1863 977 1185 1291 1991 
47 465 1929 415 1625 1733 1145 1615 855 373 1489 527 943 1161 909 1961 
687 865 1075 1099 1455 807 773 1523 1097 357 629 1055 229 829 1783 1203 
177 275 1089 1541 2011 2039 595 933 573 505 45 895 309 273 163 487 
967 727 1503 419 1117 1879 653 295 1445 603 1235 1659 159 811 737 1229 
1977 1737 39 399 1705 2021 263 223 1993 2023 1265 787 185 2045 323 53 
1639 1987 819 1403 167 1773 513 105 1587 1369 1609 1643 1829 1437 625 1923 
1315 1653 463 1447 85 1981 121 231 1935 1189 171 1477 621 1425 1701 1375 
1827 1833 389 1037 665 403 619 93 981 191 325 187 151 825 761 1595 
499 303 1213 1605 1247 1367 805 1781 25 1015 1077 1593 1911 1881 1187 841 
1349 1471 1757 739 1251 1693 1909 973 1271 1191 833 551 1913 1599 251 1395 
113 695 1591 1945 1383 1795 1365 857 1179 955 1223 1167 255 689 823 437

进行查找的测试数据为 0~2048，共2049个数。

理论分析（第三问和第四问）

BST查找

test1

有序的序列初始化BST，是一棵斜树。

可知查找成功的长度为（1 + 2 + 3 + ··· + n）。n = 1024。

则平均长度为512.5，与运行结果一致。

查找失败则为（2 + 3 + ··· + （n + 1） + （n + 1））。n = 1024。

计算得，平均长度为513.99，与运行结果一致。
test2

随机序列生成的BST的应为分布较为均匀的二叉树，也就是比较平衡的。

设

\[h=⌊log2(n+1)⌋，r=n−(2^h−1)，v=n−r \]
则平均查找成功长度

\[S=\frac{1}{n}(\sum_{j = 1}^{h}{j * 2^{j - 1} + r(h + 1)}) \]
化简得

\[S = \frac{1}{n}(v + 1)\log_{2}{(v + 1)} - v + \frac{1}{n}r(h + 1) \]
若为理想的满二叉树，即$$n = 2^{h} - 1$$。

则可得平均查找成功长度为

\[S = \frac{n + 1}{n}log_{2}{(n + 1)} - 1 \]
此时平均查找失败长度为 $$log_2(n + 1)$$ 。

考虑到为随机生成的序列，则运行结果应该比理论值偏大，结果说明，与理论一致。

折半查找

两组数据在BST上中序遍历生成的序列都是0~2048顺序的奇数序列，是有序的。

所以两组测试的折半查找平均查找长度相同。

折半查找的平均查找长度借助二叉树来计算。

与上述BST的test2的计算推导过程类似。

平均查找成功长度约$$S = \frac{n + 1}{n}log_{2}{(n + 1)} - 1$$。

平均查找失败长度为 $$log_2(n + 1)$$ 。

直接代入n = 1024，算得理论值约为9.01，10.00。与运行结果一致！

第五问

就一般情况下的平均查找性能来说，折半查找与BST的查找性能差不多。
但是对于特殊的数据，比如连续的已排序好的数，BST的查找性能会大幅度下降。
而折半查找却不会，但这是建立在折半查找在已排序好的数据上的。我们需要读入数据后排序，才可以进行折半查找。
所以，对于有插入和删除操作的查找来说，BST的的平均性能还是要比折半查找优的。

代码

点击查看代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

#define MAXN 1050
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef struct BST_Node{//二叉树
    int data;//数据
    struct BST_Node *lc, *rc;//左右孩子
}BST_Node, *BST;

typedef int Status;
int bs[MAXN];//中序遍历序列
int cnt, idx;
//idx 为生成的中序遍历序列大小，cnt 为查找次数

Status Search(BST T, BST father, int key, BST *p);//BST递归查找
Status Insert(BST *T, int key);//BST递归插入
Status Delete(BST *T, int key);//BST递归删除
void Del(BST *p);//BST删除
void Traverse(BST T);//BST中序遍历
void Test(BST T, int a[]);//平均查找长度的测试
int Binary_Search(int key, int a[], int l, int r);//折半查找
int main()
{  
    int temp;
    BST t1, t2;
    t1 = t2 = NULL;
    FILE* fp;
    
    fp = fopen("in1.txt", "r");
    if(fp == NULL) exit(1);

    //第一个测试样例，in1.txt，为0~2048的奇数序列，共1024个
    idx = 0;
    while(fscanf(fp, "%d", &temp) != EOF)
    {
        Insert(&t1, temp);
    }
    Traverse(t1);
    fprintf(stdout, "test<1>:\n");
    Test(t1, bs);

    fp = fopen("in2.txt", "r");
    if(fp == NULL) exit(1);

    //第二个测试样例，in2.txt，为上一个样例的一个随机排列
    idx = 0;
    while(fscanf(fp, "%d", &temp) != EOF)
    {
        Insert(&t2, temp);
    }
    Traverse(t2);
    fprintf(stdout, "test<2>:\n");
    Test(t2, bs);

    fclose(fp);


    return 0;
}
void Test(BST T, int a[])
{
    BST p;
    int cnt1, cnt2;
    int idx1, idx2;

    //BST查找
    cnt1 = cnt2 = 0;
    idx1 = idx2 = 0;
    for(int i = 0; i <= 2048; i ++ )
    {
        cnt = 0;
        int key = i;
        int res = Search(T, NULL, key, &p);
        if(res == FALSE)
        {
            cnt2 += cnt;
            idx2 ++;
        }else
        {
            cnt1 += cnt;
            idx1 ++;
        }
    }
    fprintf(stdout, "BST: %.2f %.2f\n", cnt1 * 1.0 / idx1, cnt2 * 1.0 / idx2);//计算平均值

    //折半查找
    cnt1 = cnt2 = 0;
    idx1 = idx2 = 0;
    int l = 0, r = idx - 1;//边界
    for(int i = 0; i <= 2048; i ++ )
    {
        cnt = 0;
        int key = i;
        int res = Binary_Search(key, a, l, r);
        if(res == -1)//查找失败
        {
            cnt2 += cnt;
            idx2 ++;
        }else
        {
            cnt1 += cnt;
            idx1 ++;
        }
    }
    fprintf(stdout, "BS:  %.2f %.2f\n", cnt1 * 1.0 / idx1, cnt2 * 1.0 / idx2);//计算平均值
}
int Binary_Search(int key, int a[],int l, int r)
{

    while(l <= r)
    {
        cnt ++;
        int mid = (l + r) / 2;
        if(a[mid] == key)
        {
            return mid;
        }else if(a[mid] < key)
        {
            l = mid + 1;
        }else
        {
            r = mid - 1; 
        }
    }
    return -1;
}

void Traverse(BST T)
{
    if(T == NULL) return;
    Traverse(T->lc);
    bs[idx ++] = T->data;
    //fprintf(stdout, "%d ", T->data);
    Traverse(T->rc);
}
void Del(BST *p)
{
    BST q, s;
    q = *p;
    if((*p)->lc == NULL)//左孩子为空
    {
        *p = (*p)->rc;
        free(q);
    }else if((*p)->rc == NULL)
    {
        *p = (*p)->lc;
        free(q);
    }else
    {
        s = (*p)->lc;
        while(s->rc != NULL)
        {
            q = s;
            s = s->rc;
        }
        (*p)->data = s->data;
        if((*p) != q)
        {
            q->rc = s->lc;
        }else
        {
            q->lc = s->lc;
        }
        free(s);
    }
    
}
//删除BST中关键字等于key的元素
Status Delete(BST *T, int key)
{
    if(*T == NULL)
    {
        return FALSE;
    }else
    {
        if(key == (*T)->data)
        {
            Del(T);
            return TRUE;
        }else if(key < (*T)->data)
        {
            return Delete(&((*T)->lc), key);
        }else
        {
            return Delete(&((*T)->rc), key);
        }
    }
}

//当二叉排序树中不存在关键字key的元素时
//插入key并返回TRUE，否则返回FALSE 
Status Insert(BST *T, int key)
{
    BST p, s;
    if(!Search(*T, NULL, key, &p))
    {
        s = (BST)malloc(sizeof (BST_Node));
        s->data = key;
        s->lc = s->rc = NULL;

        if(p == NULL)//根节点不存在
        {
            *T = s;
        }else if(key < p->data)//左孩子
        {
            p->lc = s;
        }else//右孩子
        {
            p->rc = s;
        }

        return TRUE;
    }
    return FALSE;
}
//递归查找二叉排序树,father为搜索当前节点的父节点,T为搜索的当前节点,key为搜索的关键字指针,p指向查找的结果
Status Search(BST T, BST father, int key, BST *p)
{
    cnt ++;
    if(!T)//查找的节点不存在
    {
        *p = father;
        return FALSE;
    }else if(key == T->data)//查找成功，返回当前节点
    {
        *p = T;
        return TRUE;
    }else if(key < T->data)
    {
        return Search(T->lc, T, key, p);//递归左儿子
    }else
    {
        return Search(T->rc, T, key, p);//递归右儿子
    }
}