划分操作为找出二叉树中第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 }
原文：https://www.cnblogs.com/ningjing213/p/12878689.html