欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构与算法(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!!!