3.2 二叉查找树

各种符号表预览

使用的数据结构	实现	优点	缺点
链表(顺序查找)	SequenceSearchST	适用于小型数组	大型数组慢
有序数组(二分查找)	BinarySearchST	最优的查找效率	插入比较慢
二叉查找树	BST	实现简单,能进行有序性相关操作	没有性能上界,链接需要额外空间
平衡二叉查找树	RedBlackBST	最优的查找和插入效率,能进行有序性相关操作	链接需要额外的空间
散列表	SeparateChainHashST LinearProbingHashST	能快速的查找和插入常见类型的数据	需要计算每种类型的hashcode,无法有序,链接和空节点需要额外空间

定义:

一颗二叉查找数(BST)是一棵二叉树,每个节点都有一个Comparable键(以及相关的键值),每一个结点的键都大于其左子树任意结点的键值,小于其右子树任意结点的键值.

image.png

3.2.1数据表示

每个结点都会有一个 :键,一个值,一个左链接,一个右链接,一个结点计数器 .size(x)=size(x.left)+size(x.right)+1 ;// 表示结点计数器,从下面到这个结点一共有几个结点.

同一个集合可以用不同的二叉查找树表示.

例如下图3.2.3. image.png

代码如下 :

package algorithm.sortAlgorithm.search;
/**
 * Created by leon on 18-1-28.
 * 查找二叉树
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;
    private class Node {
        private Node left;
        private Node right;
        private Value value;
        private Key key;
        private int N;//当前的结点数
        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }
    public int size() {
        return size(root);
    }
    private int size(Node node) {
        if (node == null) {
            return 0;
        }
        return node.N;
    }
    public void put(Key key, Value value) {
        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.right = put(x.right, key, value);
        } else if (cmp < 0) {
            x.left = put(x.left, key, value);
        } else {
            put(x, key, value);
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    public Value get(Key key) {
        return get(root, key);
    }
    private Value get(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            return get(node.right, key);
        } else if (cmp < 0) {
            return get(node.left, key);
        } else {
            return node.value;
        }
    }
}

分析:
二叉查找树的最好的情况是 ,一颗含有N结点的完全平衡树,查找的时间为~lgN,而最坏的情况是搜索路径上有N个结点,查找的时间复杂度为N.但是一般情况下实际和最好情况接近.
二叉查找树和快速排序几乎是双胞胎.因为树的根节点就是树中第一个切分点,得到一下性质:

命题C:

在由N个结点构造的二叉查找树中,查找命中所需要的平均时间为~2lnN 约1.39lgN.

命题D:

在由N个结点构成的二叉查找树中,插入操作和查找未命中平均需要时间为~2lnN 约1.39lgN

3.2.3 有序性相关方法与删除操作:

删除最大键和最小键,这是二叉查找树中最难实现的部分.
删除最小键 :deleteMin().先遍历左子树节点,直到遇到一个左节点是空的.把指向当前节点链接指向其右子树,删除当前的节点.
如何删除拥有两个子结点的结点呢?
在删除结点x后,用x的右子树的后继结点(最左结点)填补它的位置.

image.png	image.png

二叉查找树代码:

package algorithm.sortAlgorithm.search;
/**
 * Created by leon on 18-1-28.
 * 二叉树查找
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;
    private class Node {
        private Node left;
        private Node right;
        private Value value;
        private Key key;
        private int N;//当前的结点数
        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }
    public int size() {
        return size(root);
    }
    private int size(Node node) {
        if (node == null) {
            return 0;
        }
        return node.N;
    }
    public void put(Key key, Value value) {
        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.right = put(x.right, key, value);
        } else if (cmp < 0) {
            x.left = put(x.left, key, value);
        } else {
            put(x, key, value);
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    public Value get(Key key) {
        return get(root, key);
    }
    private Value get(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            return get(node.right, key);
        } else if (cmp < 0) {
            return get(node.left, key);
        } else {
            return node.value;
        }
    }
    public void deleteMin() {
        root = deleteMin(root);
    }
    /**
     * 递归x.left ,直到 node 没有左结点 ,还是返回当前的树
     *
     * @param x
     * @return 最终返回替换被删除的结点的 链
     */
    private Node deleteMin(Node x) {
        if (x.left == null) {
            return x.right;
        } else {
            x.left = deleteMin(x.left);
            x.N = size(x.left) + size(x.right) + 1;
            return x;
        }
    }
    public void delete(Key key) {
        root = delete(root, key);
    }
    private Node delete(Node x, Key key) {
        if (x == null) {
            return null;
        }
        //接下来 左,右结点都存在,需要比较下,这个key 在左右那个子节点下
        int cmp = key.compareTo(x.key);
        //right
        if (cmp > 0) {
            //遍历右子树,删除
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            x.left = delete(x.left, key);
        } else {
            //就是当前的结点 需要删除.
            if (x.left == null) {
                return x.right;
            } else if (x.right == null) {
                return x.left;
            } else {
                Node t = x;
                x = min(t.right);
                x.right = deleteMin(t.right);
                x.left = t.left;
            }
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    private Node min(Node x) {
        if (x.left == null) {
            return x;
        } else {
            return min(x.left);
        }
    }
}