数据结构与算法(7) -- 二叉查找树
程序员文章站
2022-08-31 17:26:40
上一个博客介绍了堆结构,这种结构非常有利于查找最大/最小元素。但是其也有一个非常显著的缺点,对于其他的元素的查找非常困难。这一节将要介绍的是二叉查找树,这种结构保持了这样的特性:其父节点大于左子节点,而小于其右子节点。 另外因为放假的原因将博客停了一段时间,接下来会恢复这个系列。由于后面博主主要打算 ......
上一个博客介绍了堆结构,这种结构非常有利于查找最大/最小元素。但是其也有一个非常显著的缺点,对于其他的元素的查找非常困难。这一节将要介绍的是二叉查找树,这种结构保持了这样的特性:其父节点大于左子节点,而小于其右子节点。
另外因为放假的原因将博客停了一段时间,接下来会恢复这个系列。由于后面博主主要打算找java开发相关的岗位,后续的实例代码和讲解可能要偏向于java,这点和之前一直用c++讲解稍有区别。
数据表示
二叉查找树和其他的树结构一样都是基于节点node的一种数据结构。每个节点都含有一个键、一个值、一条左链接和一条右链接。这里有所不同的是,为了后续某些操作的方便,每个节点还有一个节点计数器。如下代码所示(java):
private class node { private key key; // 键 private value val; // 值 private node left, right; // 左和右子节点 private int size; // 以该节点为根的子树中的节点总数 public node(key key, value val, int size) { this.key = key; this.val = val; this.size = size; } }
基本操作的分析
查找
在二叉查找树里进行查找是简单的。假设我们在一棵根节点为root的二叉查找树中查找值为value的节点。我们只需将value和root.val相比较就行了,如果value更大,则在右子树里进行查找;反之则在左子树里进行查找。如此迭代下去即可。代码如下:
public value get(key key) { return get(root, key); } private value get(node x, key key) { if (key == null) throw new illegalargumentexception("calls get() with a null key"); if (x == null) return null; int cmp = key.compareto(x.key); if (cmp < 0) return get(x.left, key); else if (cmp > 0) return get(x.right, key); else return x.val; }
插入
插入也是类似的,只不过这里要注意的是:由于插入改变了树的结构,所以一定不要忘了更新被插入元素的size。如果是递归的话,将更新写在最后就能够保证先计算子节点的size,再计算父节点的size,这一点一定要注意,代码如下:
public void put(key key, value val) { if (key == null) throw new illegalargumentexception("calls put() with a null key"); if (val == null) { delete(key); return; } root = put(root, key, val); assert check(); } private node put(node x, key key, value val) { if (x == null) return new node(key, val, 1); int cmp = key.compareto(x.key); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else x.val = val; x.size = 1 + size(x.left) + size(x.right); return x; }
总结
以上就是二叉查找树的两个核心操作了,另外还有更多的代码和操作请戳这里。由于二叉查找树不能保证树的平衡性,最差的时候其性能会退化到n(平均情况下是1.39lgn)。所以在实际中很少使用,在java集合以及c++ stl中用的是平衡的二叉树,例如红黑树等。这是后一博客要讨论的内容。
参考资料:
《算法》第四版
《stl源码剖析》
see you next time. happy coding!!!