文章目录

• • 1 范围查找keys()
  • 2 性能分析
  • 3 综合测试
  • 4 后记

1 范围查找keys()

既然是范围查找呢，需要遍历整个二叉树，上一篇我们讲解了二叉树遍历，这里我们就需要用到。

以中序遍历为例，范围[lo,hi][lo,hi][lo,hi]算法如下：

• 遍历二者查找树，如果当前节点lo≤key≤hilo\le key\le hilo≤key≤hi，符合要求

代码如下：

/*** [lo,hi]范围内键的迭代器* @param lo    范围下限* @param hi    范围上限* @return      范围内键的迭代器*/
@Override
public Iterable keys(K lo, K hi) {Queue q = new LinkQueue<>();Stack> l = new Stack<>();Node current = root;while (current != null || !l.isEmpty()) {while (current != null) {l.push(current);current = current.left;}if (!l.isEmpty()) {current = l.pop();if (lo.compareTo(current.key) <= 0 && hi.compareTo(current.key) >= 0) {q.offer(current.key);}current = current.right;}}return q;
}

2 性能分析

二叉查找树中和有序性有关的操作的性能如何？要研究这个问题，我们首先要知道树的高度（任意节点的最大深度或称树的深度)。给定一棵树，树的高度决定了所有操作在最坏的情况下的性能（我们实现的范围查找增长数量级N)

在一棵二叉查找树中，所有操作在最坏情况下所需的时间都和树的高度成正比。

目前位置3中符号表实现成本比较，如下表：

下面看下符号表的初始实现的性能特点，如下表4-1所示：

3 综合测试

代码如下：

public class TestBst {public static void main(String[] args) {testBst();}public static void testBst() {BST bst = new BST<>();bst.put(33, "a");bst.put(23, "b");bst.put(82, "c");bst.put(3, "d");bst.put(25, "e");bst.put(70, "f");bst.put(100, "g");System.out.println("初 始：" + bst);Integer key = 3;
//        System.out.println(key + "-" + bst.get(key));
//
//        System.out.println("最大键: " + bst.max());
//        System.out.println("最小键: " + bst.min());
//
//        key = 5;
//        System.out.println(key + " 向上取整：" + bst.ceiling(key));
//        System.out.println( key + " 向下取整：" + bst.floor(key));
//        key = 26;
//        int index = bst.rank(key);
//        System.out.println("rank(" + key + ")=" + index);
//        System.out.println("select(" + index + ")=" + bst.select(index));//        key = 70;
//        System.out.println("删除： " + key + "=" + bst.delete(key));
//        System.out.println("删除后： " + bst);//        System.out.println("删除最小键： " + bst.deleteMin());
//        System.out.println("删除后：" + bst);
//        System.out.println("删除最大键： " + bst.deleteMax());
//        System.out.println("删除后：" + bst);int lo = 0, hi = 80;Iterator iterator = bst.keys(lo, hi).iterator();System.out.println("范围查找：" + lo + "~" + hi);while (iterator.hasNext()) {System.out.print(iterator.next() + " ");}System.out.println();}
}

我目前没测出bug，如果小伙伴有测出bug或者其他可以联系我或者留言。

4 后记

​ 如果小伙伴什么问题或者指教，欢迎交流。

❓QQ:806797785

⭐️源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考：

[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10