12.1、二叉搜索树的定义
1、一颗二叉搜索树是以二叉树来组织的，它具有如下性质： 设x是二叉搜索树中的一个节点，如果y是x左子树中的一个节点，那么y.key <= x.key；如果y是x右子树中的一个节点，那么y.key >= x.key。我们用left、right、p分别表示二叉搜索树的左子树、右子树和父节点。 2、根据二叉搜索树的性质，对二叉搜索树进行中序遍历，即可得到一个递增的序列；也就是说，为了检查一个树是否是二叉搜索树，可以使用中序遍历。 中序遍历的伪代码为(递归)： InorderTreeWalk(x) if(x != NIL) InorderTreeWalk(x.left); print x.key; InorderTreeWalk(x.right); 练习： 12.1-2: 二叉搜索树：左子树关键字<根结点关键字<右子树关键字 最小堆：根结点关键字 <= 左子树关键字 && 根结点关键字 <= 右子树关键字 不能，因为在最小堆中，左子树和右子树的大小关系不能确定，而如果通过比较算法来进行排序的话，其下界为n*lgn 。 12.1-3： 用栈实现：见算法导论-10.4-有根树的表示中的10.4-3 不用栈实现：见算法导论-10.4-5 12.1-4： 和中序遍历类似。只不过遍历根节点的顺序不同，其伪代码如下： PreorderTreeWalk(x) if(x != NIL) print x.key; InorderTreeWalk(x.left); InorderTreeWalk(x.right); PostorderTreeWalk(x) if(x != NIL) InorderTreeWalk(x.left); InorderTreeWalk(x.right); print x.key; 12.1-5: 反证法。假设存在一种基于比较的算法，从n个元素的任意序列中构造一颗二叉搜索树，其最坏情况下的时间复杂度Ω低于n*lgn。则可以构造一种基于比较的排序模型，首先，构造一颗二叉搜索树(时间复杂度为Ω)，然后以中序遍历输出该二叉搜索树的元素(时间复杂度为n)，即可完成排序。最终，该算法的时间复杂度为max(Ω,n),小于n*lgn，这与题设中所有基于比较的排序模型的算法的时间复杂度的下界为n*lgn矛盾，因此假设不成立，原命题得证。 12.2、查询二叉搜索树 1、查找。 二叉搜索树查找操作的伪代码为(递归)： TreeSearch(x,k) if(x == NIL || x .key == k) return x; if(k < x.key) return TreeSearch(x.left,k); else return TreeSearch(x.right,k); 二叉搜索树查找操作的伪代码为(循环)： TreeSearch(x) while(x != NIL || x .key != k) if(k < x.key) x = x.left; else x = x.right; return x; 2、最大和最小关键字元素 根据二叉搜索树的性质：通过从树根开始沿着left孩子的指针直到遇到NIL,我们总能在一颗二叉搜索树中找到一个元素，该元素就是以x为根的二叉搜索树的最小关键字元素；同理，从树根开始沿着right孩子的指针直到遇到NIL，即可获得最大关键字元素。 获得最小关键字元素的伪代码为(循环)： TreeMinimum(x) while(x.left != NIL) x = x.left; return x; 获得最小关键字元素的伪代码为(递归)： TreeMinimum(x) if(x.left == NIL) return x; return TreeMinimum(x.left); 获取最大关键字元素和获取最小关键字元素的伪代码是对称的，为： 循环： TreeMaximum(x) while(x.right != NIL) x = x.right; return x; 递归： TreeMaximum(x) if(x.right == NIL) return x; return TreeMaximum(x.right); 3、前驱和后继 给定一个二叉搜索树中的一个节点，有时需要按中序遍历查找它的前驱和后继。如果所有关键字互不相同，则一个节点x的后继是大于x.key的最小关键字节点，x的前驱是小于x.key的最大关键字节点。如果x就是该二叉搜索树的最小或最大关键字，则x的前驱或后继为NIL。 获取二叉搜索树后继的伪代码为： TreeSuccessor(x) if(x.right != NIL) return TreeMinimum(x.right); y = x.p; while( y != NIL && x == y.right) x = y; y = y.p; return y; 把TreeSuccessor分为两种情况：如果x的右子树非空，那么x的后继恰是x右子树中最左的节点，通过TreeMinimum(x.right)可以找到；另一方面，如果x的右子树为空并且有一个后继y，那么y就是x的有左孩子的最底层祖先。 获取二叉搜索树前驱与获取二叉搜索树后继的行为是对称的，其伪代码为： TreePredecessor(x) if(x.left != NIL) return TreeMaximum(x.left); y = x.p; while(y != NIL && x == y.left) x= y; y = y.p; return y; 练习： 12.2-1： 根据二叉搜索树查找的特点，遇到比363小的数，就往右找，查找序列中的数会越来越大；反之，遇到比363大的数，就往左找，查找序列中的数就越来越小。因此，比363大的数是按降序排列的，比363小的数是按升序排列的。所以c和e不是查找过的序列。 12.2-2、12.2-3:见前面的伪代码。 12.2-4 反例太多了... 12.2-5: 如果二叉搜索树有右孩子，则它的后继为TreeMinimum(x.right),为最左边的元素，没有左孩子；同理可知，它的前驱没有右孩子。 12.3 插入和删除 1、插入 要将一个新值v插入到一颗二叉搜索树T中，需要调用TreeInsert。该过程以节点z作为输入，其中z.key = v,z.left = NIL,z.right = NIL。插入过程的伪代码为： TreeInsert(T,Z) y = NIL; x = T.root; while (x != NIL) y = x; if(z.key < x.key) x = x.left; else x = x.right; z.p = y; if(y == NIL) //树是空的 T.root = z; else if(z.key < y.key) y.left = z; else y.right = z; 2、删除 从一颗二叉搜索树T中删除一个节点z分为三种情况： a：如果z没有孩子节点，那么只需要简单的将它删除，并修改它的父节点，用NIL作为孩子替换z即可。 b:如果z只有一个孩子节点，那么将这个孩子提升到树z的位置中，并修改z的父节点，用z的孩子来替换z c：如果z有两个孩子，那么找到z的后继y，并让y占据树中z的位置。z原来的右子树部分成为y的新的右子树，z原来的左子树成为y的新的左子树。 P167的图12-4总结了删除二叉搜索树节点时的四种情况。 从一颗二叉搜索树T中删除一个节点z的伪代码为： 首先定义一个在二叉搜索树内迁移节点的函数Transplant.它是用一颗子树v替换一颗子树u，并成为u的双亲的孩子节点。 Transplant(T,u,v) //u是根节点 if(u.p == NIL) T.root = v; //u是其双亲的左孩子 else if(u == u.p.left) u.p.left = v; //u是其双亲的右孩子 else u.p.right = v; if(v != NIL) v.p = u.p; 最后是TreeDelete的伪代码： TreeDelete(T,z) if(z.left == NIL) Transplant(T,z,z.right);//z.right为NIL也能正常删除 else if(z.right == NIL) Transplant(T,z,z.left); else //找z的后继，因为z有右子树，所以直接调用TreeMinimum即可 y = TreeMinimum(z.right); if(y.p != z) Transplant(T,y,y.right); y.right = z.right; y.right.p = y; Transplant(T,z,y); y.left = z.left; y.left.p = y;