二叉搜索树的划分

划分操作为找出二叉树中第k个最小关键字的数据项，并通过一些操作使其位于树根。

为了找出一棵二叉搜索树中含有第k个最小关键字的数据项，我们检查左子树的节点数量。若那里存在k个节点，那么我们返回树根处的数据项。否则，若左子树拥有k个以上节点，我们就递归地在那里寻找第k个最小的节点。如果这两个条件都不成立，则左子树拥有t个元素且t<k，二叉搜索树中第k个最小元素就是右子树的第k-t-1个最小元素。找到该元素后，递归的通过根插入中的旋转操作使其成为整棵树的根。

 1 private:
 2     Item selectR(link h, int k)
 3     { if (h == 0) return nullItem;
 4        int t = (h->l == 0) ? 0:h->l->N;
 5        if (t > k) return selectR(h->l, k);
 6        if (t < k) return selectR(h->r, k-t-1);
 7        return h->item;
 8      }
 9 public:
10     Item select(int k)
11     { return selectR(head, k);}

1 void partR(link& h, int k)
2 { int t = (h->l == 0) ? 0:h->l->N;
3    if (t > k)
4    { partR(h->l, k); rotR(h);}
5    if (t < k)
6    { partR(h->r, k-t-1); rotL(h);}
7 }