• 12.3-1 二叉搜索树insert操作的递归版本
  1. void insert1(Node* pRoot, Node* pAdd)
  2. {
  3.     bool bLeft = pAdd->key < pRoot->key;
  4.     Node* pNextRoot = bLeft ? pRoot->left : pRoot->right;
  5.     if(pNextRoot)
  6.         insert1(pNextRoot, pAdd);
  7.     else
  8.     {
  9.         pAdd->parent = pRoot;
  10.         if(bLeft)
  11.             pRoot->left = pAdd;
  12.         else
  13.             pRoot->right = pAdd;
  14.     }
  15. }

  • 12.3-2 insert过程途经n个节点后遇到了空节点，便将待插入的元素安放上去了，接下来的search过程先路过同样的n个节点，最后与第n+1个节点比较发现相同，于是search完毕。

  • 12.3-3 由12.3-2可得，insert过程和search过程一样，是O(h)-time的，h代表树的高度。

    设一共有n个节点，构建一棵树需要调用n次insert，这个过程耗时O(nh)，后续的中序遍历耗时是O(n)。所以排序过程的时间复杂度是由构建过程决定的。

    最坏的情况集合按照正序或者倒序排列，则h = n，总时间是O(n^2)。

    最好情况是集合按照层次遍历顺序排列，最后构建成一棵完全二叉树，h = lg(n) ,总时间为O(n*lg(n))。

  • 12.3-4 从同一棵二叉搜索树上先删除x再删除y，和先删除y再删除x，最终得到的树一定是一样的吗？

    不一定，举个反例：

  1. //现在有一棵树，上面有1,2,3,4四个节点：
  2.         2
  3.     /        \
  4. 1            4
  5.             /
  6.            3
  7. //如果 先删除1 再删除2，结果是：
  8.         2                            2                            4
  9.     /        \                            \                        /
  10. 1            4        -->                4        -->       3
  11.             /                              /
  12.            3                            3
  13. //如果 先删除2 再删除1，结果是：
  14.         2                                3                    3
  15.     /        \                          /    \                     \
  16. 1            4        -->         1        4        -->        4
  17.             /
  18.            3
  19. //得到的结果是不一样的。

下面说说，我是怎样想到这个反例的。

要删除x，根据删除的规则，如果x没有孩子，直接删除；如果x只有一个孩子，就用唯一的孩子顶替x的位置；如果x有两个孩子，就将x的后继节点s顶替x的位置。

从这个规则中可以发现，x有几个孩子会影响到x的接班人人选。如果删除的顺序可以影响到删除x时候x的孩子个数，就会影响到最终树的形状。

那么，y在x的什么位置上，删除y会对x孩子个数造成影响呢？y本身就是x的一个孩子，而且y没有孩子。下面分左孩子和右孩子讨论。因为x只有一个孩子y的情况太简单，也不能成为反例，不做讨论，下面对x有两个孩子的情况进行分析。称以x为根的树为X树。

如果y是x的左孩子，先删y，删除之后，x的孩子个数变成1，此时删除x，X树被其右子树取代，X树的根变为x的右孩子。反过来，先删除x，此时x有两个孩子，X树的根变为x的后继，只要其后继不是它的右孩子本身，那么结果就是不一样的。这也就是上面给出的反例。

如果y是x的右子树，先删y，再删x，X树被x左子树取代，先删x，y顶替x的位置，再删y，X树仍然被x的左子树取代，结果是一样的，不能作为反例。

还有一种可能，删除x，x的接班人是自己的后继s，原以s为根的树S会发生改变，从S树上节点能否找出一个y作为反例，我暂时没有想清楚。

  • 12.3-5 二叉搜索树的每个节点保存“后继”，“左孩子”，“右孩子”三个属性，在O(h)时间内实现insert delete search。（这道题在《算法导论》第三版的中文版翻译有误）

    为什么要把“父亲”属性替换成“后继”属性呢？相比保存“父亲”，保存“后继”属性的优势在于查找后继节点时间O(1),排序虽然都是O(n)但是常数项较小。执行这两种操作时，性能相当于单向链表。而执行插入、删除、查找操作时，性能相当于二叉树。

    我们先来总结一下这些操作需要读写哪些属性。

    insert操作需要修改的有：父亲节点的孩子属性，前驱节点和新插入节点的后继属性

    delete操作需要修改的有：父亲节点的孩子属性，前驱节点的后继属性

    search操作需要读取的有：节点的孩子属性

    根据上面的总结可以发现，这道题的关键点是在O（h）时间内找到父亲节点和前驱节点。

    查找父亲节点的做法是从Root向下逐级查找；如果当前节点没有左孩子，那么查找前驱节点的做法也是从Root向下查找，可以和父亲节点的查找工作合并起来。如果当前节点有左孩子，那么前驱节点是左孩子的最大节点。

  1. #include <iostream>
  2. #include <cassert>
  3. using namespace std;
  4. struct Node
  5. {
  6.     int key;
  7.     Node* succ;
  8.     Node* left;
  9.     Node* right;
  10.     Node(int k):key(k),succ(nullptr),left(nullptr),right(nullptr){}
  11. };
  13. Node* minimum(Node* pRoot);
  14. Node* parent_pred(Node* pRoot, int key, Node*& pPred);//为新插入节点，找父亲的同时从父亲中找前驱
  16. void insert(Node* pRoot, int key)
  17. {
  18.     Node* pNew = new Node(key);
  19.     Node* pPred;
  20.     Node* pParent = parent_pred(pRoot, key, pPred);
  21.     Node* pHead = minimum(pRoot);
  22.     //upate parent\'s child
  23.     if(key < pParent->key)
  24.         pParent->left = pNew;
  25.     else
  26.         pParent->right = pNew;
  27.     //update pPred\'s succ and pNew\'s succ
  28.     if(pPred)
  29.     {
  30.         pNew->succ = pPred->succ;
  31.         pPred->succ = pNew;
  32.     }
  33.     else
  34.     {
  35.         pNew->succ = pHead;//注意：这个头结点一定要在插入之前获取
  36.     }
  37. }
  39. Node* pred(Node* pNode);                                                            //从左子树上找前驱
  40. Node* parent(Node* pRoot, Node* pNode);                                    //找父亲
  41. Node* parent_pred(Node* pRoot, Node* pNode, Node*& pPred);    //为已有节点，找父亲的同时从父亲中找前驱
  42. void Delete(Node*& pRoot, Node* pDelete)
  43. {
  45.     Node* pDeleteReplace = nullptr;
  47.     if(!pDelete->left)
  48.     {
  49.         pDeleteReplace = pDelete->right;//no child    //only right
  50.     }
  51.     else
  52.     {
  53.         pDeleteReplace = pDelete->left; //only left
  54.         if(pDelete->right)              //both
  55.         {
  56.             Node* pSucc = pDelete->succ;
  57.             if(pSucc != pDelete->right)
  58.             {
  59.                 Node* pSuccParent = parent(pRoot, pSucc);
  60.                 if(pSucc->key < pSuccParent->key)
  61.                     pSuccParent->left = pSucc->right;
  62.                 else
  63.                     pSuccParent->right = pSucc->right;
  64.                 pSucc->right = pDelete->right;
  65.             }
  66.             pSucc->left = pDelete->left;
  67.             pDeleteReplace = pSucc;
  68.         }
  69.     }
  70.     //update parent\'s child, pred\'s succ
  71.     Node* pPred;
  72.     Node* pDeleteParent = parent_pred(pRoot, pDelete, pPred);
  73.     bool bLeft;
  74.     if(pDeleteParent)
  75.         bLeft = pDeleteParent->left == pDelete;
  77.     if(pDeleteParent)
  78.     {
  79.         if(bLeft)
  80.             pDeleteParent->left = pDeleteReplace;
  81.         else
  82.             pDeleteParent->right = pDeleteReplace;
  83.     }
  84.     else
  85.     {
  86.         pRoot = pDeleteReplace;
  87.     }
  89.     if(pPred)
  90.     {
  91.         pPred->succ = pDelete->succ;
  92.     }
  93. }
  95. Node* search(Node* pRoot, int key)
  96. {
  97.     Node* pCurrent = pRoot;
  98.     int keyCurrent;
  99.     while(pCurrent)
  100.     {
  101.         keyCurrent = pCurrent->key;
  102.         if(key == keyCurrent)
  103.             break;
  104.         if(key < keyCurrent)
  105.             pCurrent = pCurrent->left;
  106.         else
  107.             pCurrent = pCurrent->right;
  108.     }
  109.     return pCurrent;
  110. }
  112. Node* minimum(Node* pRoot)
  113. {
  114.     Node* pMin = pRoot;
  115.     while(pMin->left)
  116.     {
  117.         pMin = pMin->left;
  118.     }
  119.     return pMin;
  120. }
  122. Node* parent_pred(Node* pRoot, int key, Node*& pPred)
  123. {
  124.     Node* pCurrent = pRoot;
  125.     Node* pParent = nullptr;
  126.     pPred = nullptr;
  127.     while(pCurrent)
  128.     {
  129.         pParent = pCurrent;
  130.         if(key < pCurrent->key)
  131.         {
  132.             pCurrent = pCurrent->left;
  133.         }
  134.         else
  135.         {
  136.             pCurrent = pCurrent->right;
  137.             pPred = pParent;
  138.         }
  139.     }
  140.     return pParent;
  141. }
  143. Node* parent(Node* pRoot, Node* pNode)
  144. {
  145.     Node* pCurrent = pRoot;
  146.     Node* pParent = nullptr;
  147.     while(pNode != pCurrent)
  148.     {
  149.         assert(pCurrent);
  150.         pParent = pCurrent;
  151.         if(pNode->key < pCurrent->key)
  152.             pCurrent = pCurrent->left;
  153.         else
  154.             pCurrent = pCurrent->right;
  155.     }
  156.     return pParent;
  157. }
  159. Node* parent_pred(Node* pRoot, Node* pNode, Node*& pPred) 
  160. {
  161.     Node* pCurrent = pRoot;
  162.     Node* pParent = nullptr;
  163.     pPred = nullptr;
  164.     while(pNode != pCurrent)
  165.     {
  166.         assert(pCurrent);
  167.         pParent = pCurrent;
  168.         if(pNode->key < pCurrent->key)
  169.             pCurrent = pCurrent->left;
  170.         else
  171.         {
  172.             pCurrent = pCurrent->right;
  173.             pPred = pParent;
  174.         }
  175.     }
  176.     return pParent;
  177. }
  179. Node* pred(Node* pNode) 
  180. {
  181.     Node* pPred = pNode->left;
  182.     while(pPred->right)
  183.         pPred = pPred->right;
  184.     return pPred;
  185. }
  188. void walk(Node* pRoot)
  189. {
  190.     Node* pCurrent = minimum(pRoot);
  191.     while(pCurrent)
  192.     {
  193.         cout << pCurrent->key << "\t";
  194.         pCurrent = pCurrent->succ;
  195.     }
  196.     cout << endl;
  197. }
  199. void test()
  200. {
  201.     //build
  202.     Node* pRoot = new Node(4);
  203.     insert(pRoot, 2);
  204.     insert(pRoot, 5);
  205.     insert(pRoot, 1);
  206.     insert(pRoot, 3);
  207.     insert(pRoot, 7);
  208.     insert(pRoot, 6);
  209.     insert(pRoot, 8);
  210.     walk(pRoot);
  211.     //search
  212.     cout << search(pRoot, 3)->key << endl;
  213.     cout << search(pRoot, 6)->key << endl;
  214.     cout << search(pRoot, 4)->key << endl;
  215.     //delete
  216.     Delete(pRoot, pRoot->right);//delete 5
  217.     Delete(pRoot, pRoot->left); //delete 2
  218.     Delete(pRoot, pRoot->left); //delete 3
  219.     Delete(pRoot, pRoot);// delete 4
  220.     Delete(pRoot, pRoot->left);//delete 1
  221.     walk(pRoot);
  222.     //destroy
  223.     Node* pCurrent = minimum(pRoot);
  224.     while(pCurrent)
  225.     {
  226.         delete pCurrent;
  227.         pCurrent = pCurrent->succ;
  228.     }
  229.     pCurrent = nullptr;
  230. }
  231. /*output
  232. 1	2	3	4	5	6	7	8
  233. 3
  234. 6
  235. 4
  236. 6	7	8
  237. */
  • 12.3-6 当x有两个孩子的时候，x的接班人y取x的前驱和后继都是可以的，具体实现方法是：用一个bool量控制下一个y取两者中的哪一个，交替着选取。在y取后继节点时，需要将y现有的右孩子托付给自己的父亲（已经在《算法导论》12.3节习题 实现）；若y取前驱节点，需要做的修改是把自己的左孩子托付给自己的父亲。

版权声明：本文为meixiaogua原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/meixiaogua/p/9895377.html