二叉查找树

2018-07-27 本文已影响147人 yifyif

转载请注明出处！https://www.jianshu.com/p/89e5b811cf9c

Github源码地址

注：此篇需要链表的构成与数组基础排序相关知识

对于一般的链表或无序数组，灵活性和高效性无法得到很好的统一。于是这里介绍一种能将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。

二叉查找树的性能在 logN ~ N 之间

二叉查找树是每个结点都含有两个链接的链表数据结构。

定义：二叉查找树是一颗二叉树，其每个结点都含有一个Comparable（可比较）键。

二叉树结构
每个结点的键都大于任意左子节点而小于任意右子节点。
二叉树结构

    private class Node {
        private Key key;
        private Value value;
        private Node left, right;
        private int size;

        public Node(Key key, Value value, int size) {
            this.key = key;
            this.value = value;
            this.size = size;
        }
    }

大小 size：

    private int size(Node x) {
        if (x == null) return 0;
        return x.size;
    }

    public int size() {
        return size(root);
    }

假设结点为 x ：size(x) = size(x.left) + size(x.right) + 1

查找 get：

设查找的键值为key，根节点为root：

如果树是空的，则查找未命中（null）
如果key == root，则查找命中
如果key < root ，则在root.left中继续查找
如果key > root ，则在root.right中继续查找

    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key 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.value;
    }

插入 put:

如果树是空的，就返回一个含有新键值对的新结点
如果key < root ，则继续在左子树进行插入
如果key > root ，则继续在右子树进行插入

    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    private Node put(Node x, Key key, Value value) {
        if (x == null) return new Node(key, value, 1);
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = put(x.left, key, value);
        else if (cmp > 0) x.right = put(x.right, key, value);
        else x.value = value;
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

最小值 min：

由于我们二叉树的性质，x.left < x < x.right，故最小值一定是整个树的最左边的子结点。

    public Key min() {
        return min(root).key;
    }

    private Node min(Node x) {
        if (x.left == null) return x;
        return min(x.left);
    }

最大值 max:

理由同上，直接上代码：

    public Key max() {
        return max(root).key;
    }

    private Node max(Node x) {
        if (x.right == null) return x;
        return max(x.right);
    }

删除最小（大）值 deleteMin/deleteMax:

在我们讨论如何删除任意结点前，我们先讨论如何删除最小（大）值。
假设结点为x，以删除最小值为例：

如果x的左子结点存在，则删除即可。
如果x的左子结点不存在，则删除x，此时只剩下x的右子结点返回。
进行删除操作会改变大小，需要更新树的大小。

删除最小值

    public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x) {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

删除最大值则是将操作对象翻转一下，变为x.right即可：

    public void deleteMax() {
        root = deleteMax(root);
    }

    private Node deleteMax(Node x) {
        if (x.right == null) return x.left;
        x.right = deleteMax(x.right);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

删除 delete:

删除是二叉树中比较复杂的操作之一，主要在于删除会碰到几种情况，这里我们分情况讨论。

如果key < x.key ，则继续在x.left中寻找删除的结点。
如果key > x.key ，则继续在x.right中寻找删除的结点。
如果key == x.key ，则删除当前x的结点。但是，重点来了！！！

x为树的末结点，则直接删除即可。
x不是树的末结点，若直接删除会造成空缺，树不连续，我们需要变换一下。
(1). 如果x只有一个子结点，则删除x，x的位置用子结点代替即可。
(2). 如果x含有两个子结点，则我们删除x后，需要寻找x的右子结点中最小的（或者x的左子结点中最大的）来代替x的位置，保证二叉树的性质“每个结点的键都大于任意左子节点而小于任意右子节点”。

最后，删除会影响树的大小，需要更新大小。

删除

    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = delete(x.left, key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else {
            if (x.right == null) return x.left;
            if (x.left == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.left = t.left;
            x.right = delete(t.right, key);
        }
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

返回有序的键 keys():

二叉树看起来不像是一个有序线性数列，我们需要稍微换个视角来看。如果把二叉树压扁，从高到低一脚踩扁的那种，则此时二叉树就有那么点像了。（发挥你的想象力）
对于代码里则需要进行中序遍历:

    public Iterable<Key> keys() {
        return keys(min(), max());
    }

    public Iterable<Key> keys(Key lo, Key hi) {
        Queue<Key> queue = new Queue<>();
        keys(root, queue, lo, hi);
        return queue;
    }
    
    private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
        if (x == null) return;
        int cmplo = lo.compareTo(x.key);
        int cmphi = hi.compareTo(x.key);
        if (cmplo < 0) keys(x.left, queue, lo, hi);
        if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
        if (cmphi > 0) keys(x.right, queue, lo, hi);
    }

返回出来的队列则可以用于进行有序操作，比如遍历等:

    Iterator it = keys().iterator();
    while(it.hasNext()) {
        ...
    }

性能:

在一般情况下，假设我们输入的数据是随机的，随机组成一个二叉树耗时接近O(logN)。
一般情况
在最好的情况下，形成完全对称的二叉树，我们称之为平衡二叉树，此时树的高度h最小，h=logN，此时性能为 O(logN)。
最好情况
在最坏的情况下，形成单边高度h为N的二叉树，此时耗时O(N)。
最差情况
查找、插入、删除操作的耗时均与h正相关，故树的高度直接影响整体的性能。

结束语:

如何维持树的高度 h 始终不超过 logN ，成为提高性能的直接途径。

在我的后续文章中会带来一种自平衡的二叉树——红黑树，在红黑树的所有操作中，不论什么情况，均可以在 logN 的时间内完成战斗，这是多么高效且激动人心的发现！这种伟大的数据结构也被直接用于JAVA底层 Set 和 Map 的实现中！

参考出处：《算法导论》《Algorithm, 4th Edition》