《算法导论》二叉查找树：12.2-4(二叉查找树的性质)

12.2-4
Bunyan教授认为他发现了二叉搜索树的一个重要性质。假设在二叉搜索树中，对某关键字k的查找在一个叶结点处结束，考虑三个集合：A，包含查找路径左边的关键字；B，包含查找路径上的关键字；C，包含查找路径右边的关键字一个叶结点处结束，考虑三个集合：A，包含查找路径左边的关键字；B，包含查找路径上的关键字；C，包含查找路径右边的关键字。Bunyan教授宣称，任何三个关键字a∈A，b∈B，c∈C，必定满足a≤b≤c。请给出该命题的一个最小可能的反例.

证明：
集合A,B,C的最大值分别为Amax,Bmax,Cmax
显然，Bmax的值即树的根节点。
对于二叉搜索树，一个节点x的左子树中任意节点left,有left<=x,右子树中任意节点right，有right>=x
所以，只需要保证Cmax在根节点左子树即可
      Bmax
      /\      
        b2
       / \
       k  Cmax

 

12.2-5
如果二叉查找树中的某个结点有两个子女，则其后继没有左子女，其前趋没有右子女。
证明：
后继部分：
假设node有两个子女，其后继为x，则x必定位于node的右子树中。若x有左子女left，则有x>left,且left>node。即x>left>node。
根据二叉树的性质，node的后继节点必定为比node大且值最接近的结点，即x-node< x-left 即 left所以有：
  对于一个结点x，如果其右子树为空，则x的后继结点为右子树中最左的结点。

同理可证前趋部分。