您的位置：程序门 -> c/c++ -> c++ 语言

一个算法问题

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

一个算法问题

发表于：2008-01-21 19:45:57 楼主

suppose we want to add the operation findkth to our repertoire. the operation findkth returns the kth smallest item in the tree. assume all items are distinct. explain how to modify the binary search tree to support this operation in o（log n) time without sacrificing the time bounds of any other operation.
中文版：设我们想要把运算findkth添加到指令集中去。该运算findkth（k)返回树的第k个最小项。假设所有的项都是互异的。解释如何修改二叉树以平均o（log n)时间支持这种运算，而又不影响任何其他操作的时间界。

发表于：2008-01-21 21:12:291楼得分:0

友情帮顶

发表于：2008-01-21 21:18:362楼得分:0

其他操作都有些啥?

发表于：2008-01-22 14:51:553楼得分:0

其他操作包括：
// void insert（ x ) --> insert x
// void remove（ x ) --> remove x
// bool contains（ x ) --> return true if x is present
// comparable findmin（ ) --> return smallest item
// comparable findmax（ ) --> return largest item
// boolean isempty（ ) --> return true if empty; else false
// void makeempty（ ) --> remove all items
// void printtree（ ) --> print tree in sorted order