3.4 二叉检索树

二叉检索树的作用

1️⃣ 提供了查找元素花费logn的时间能力

2️⃣ 提供了插入和删除元素花费logn的时间能力

对于10000个数据

■使用线性表查找元素平均需要比较5000次

■使用二叉检索树查找元素平均则只需要14次

定义：二叉检索树的任何一个结点，设其值为K，则该结点左子树中任意一个结点的值都小于K；该结点右子树中任意一个结点的值都大于或等于K。

接口与结点定义

对于BST，其接口定义如下

public interface BSTADT <K extends Comparable<K>, V> {
    public void insert(K key, V value);//插入结点
    public V remove(K key);//根据key值删除结点
    public boolean update(BinNode<K, V> rt, K key, V value);//更新结点值
    public V search(K key);//搜索key所对应结点的value
    public int getHeight(BinNode<K, V> rt);//获得树高
    public boolean isEmpty();//判断是否为空
    public void clear();//清空树
}

树的结点定义如下

public class BinNode<K extends Comparable<K>, V> {
    private K key;
    private V value;

    private BinNode<K, V> left;
    private BinNode<K, V> right;

    public BinNode(K key, V value){
        left = right = null;
        this.key=key;
        this.value=value;
    }

    public BinNode() {
    }

    public boolean isLeaf() {
        return left == null && right == null;
    }

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public BinNode<K, V> getLeft() {
        return left;
    }

    public void setLeft(BinNode<K, V> left) {
        this.left = left;
    }

    public BinNode<K, V> getRight() {
        return right;
    }

    public void setRight(BinNode<K, V> right) {
        this.right = right;
    }
}

查找一个元素

在二叉检索树中查找一个元素的算法

1️⃣ 设置当前结点指向根结点

2️⃣ 重复以下步骤;

■如果当前结点为空，则退出，没有找到要匹配的元素

■如果当前结点所包含的元素的关键字大于要查找的元素的关键字，设当前结点指向其左子结点

■如果当前结点所包含的元素的关键字小于要查找的元素的关键字，设当前结点指向其右子结点

■否则，匹配元素找到，退出

public V search(K key) {
    return search(root, key);
}

private V search(BinNode<K, V> rt, K key) {
    try {
        if (key == null)
            throw new Exception("key is null");
        if (rt == null)
            return null;
        if (key.compareTo(rt.getKey()) < 0)
            return search(rt.getLeft(), key);//小于当前key值则往左子树查找
        if (key.compareTo(rt.getKey()) > 0)
            return search(rt.getRight(), key);//大于当前key值则往右子树查找
        return rt.getValue();//找到值
    } catch (Exception e) {
        e.printStackTrace();
        return null;
    }
}

查找与删除最小元素

查找最小元素比较简单，只需要一直往左边递归查找，直到左子结点为空

删除最小元素思想如下

private K getMinNode(BinNode<K, V> rt) {
    if (rt.getLeft() == null)
        return rt.getKey();
    else
        return getMinNode(rt.getLeft());
}
//返回的是更新以后的根结点
private BinNode<K, V> removeMinNode(BinNode<K, V> rt) {
    if (rt.getLeft() == null) {
        return rt.getRight();
    }//最后一个结点的右结点，为空则返回空，否则返回结点
    rt.setLeft(removeMinNode(rt.getLeft()));//不断递归更新
    //保证了二叉检索树的规范性
    return rt;
}

插入一个元素

先寻找该插入的叶结点或者分支结点

插入的位置应该是所属位置父结点的空子结点

public void insert(K key, V value) {
    try {
        if (key == null) {
            throw new Exception("Key is null, insert fault!");
        }
        if (value == null) {
            throw new Exception("Value is null, insert fault!.");
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
    root = insertHelp(root, key, value);
} 

private BinNode<K, V> insertHelp(BinNode<K, V> rt, K key, V value) {
    if (rt == null) {
        return new BinNode<K, V>(key, value);
    }

    if (key.compareTo(rt.getKey()) < 0) {
        rt.setLeft(insertHelp(rt.getLeft(), key, value));
    }//跟删除结点有异曲同工之妙

    else if (key.compareTo(rt.getKey()) > 0) {
        rt.setRight(insertHelp(rt.getRight(), key, value));
    }//跟删除结点有异曲同工之妙

    else {
        rt.setValue(value);
    }
    return rt;
}

平衡性

平衡因子：左右子树的高度之差

只要平衡因子的绝对值小于等于1，就说明这棵树是平衡的

对于二叉检索树，如果给定的元素序列顺序性好，则平衡性很差、

可以通过旋转来解决平衡因子被破坏的情况（之后会细讲）

删除一个元素

若删除结点有两个结点，则比较特殊，要考虑二叉检索树的结构不被破坏

利用替换，将带有两个子结点的删除换成带有一个子结点的删除

将右子树中的最小结点替换待删除的结点

/**
 *
 * @param key 关键字
 * @return 删除的结点的值
 */
public V remove(K key) {
    removeValue = null;
    try {
        if (key == null)
            throw new Exception("Key is null, remove failure");
        root = removeHelp(root, key);
        return removeValue;
    } catch (Exception e) {
        e.printStackTrace();
        return null;
    }
}

private BinNode<K, V> removeHelp(BinNode<K, V> rt, K key) {
    if (rt == null)
        return null;
    if (key.compareTo(rt.getKey()) < 0) {
        rt.setLeft(removeHelp(rt.getLeft(), key));
    } else if (key.compareTo(rt.getKey()) > 0) {
        rt.setRight(removeHelp(rt.getRight(), key));
    } else {
        if (rt.getLeft() == null) {
            removeValue = rt.getValue();
            rt = rt.getRight();
            //左子结点为空，直接将右子结点作为当前根结点
        } else if (rt.getRight() == null) {
            removeValue = rt.getValue();
            rt = rt.getLeft();
            //右子结点为空，直接将左子结点作为当前根结点
        } else {
            //待删除结点有两个子结点
            rt.setKey((K) getMinNode(rt.getRight()).getKey());
            rt.setValue((V) getMinNode(rt.getRight()).getValue());
            //将当前结点的key和value更新为右子树中的最小结点的值
            rt.setRight(removeMinNode(rt.getRight()));
            //将当前结点的右子结点进行更新
        }
    }
    return rt;
}

各个时间代价

搜索代价

平衡二叉检索树的操作代价为O(logn)

非平衡的二叉检索树最差的代价为O(n)

插入、删除的代价与搜索代价类同

周游一个二叉检索树的代价为O(n)

使一个二叉检索树保持平衡才能真正发挥二叉检索树的作用

源代码

/**
 * @author yjq
 * @version 1.0
 * @date 2021/11/20 22:51
 */

public class BinarySearchTree<K extends Comparable<K>, V> implements BSTADT<K, V> {
    private BinNode<K, V> root;
    private V removeValue;

    public BinarySearchTree() {
        root = null;
    }

    public BinNode<K, V> getRoot() {
        return root;
    }

    public void insert(K key, V value) {
        try {
            if (key == null) {
                throw new Exception("Key is null, insert fault!");
            }
            if (value == null) {
                throw new Exception("Value is null, insert fault!.");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        root = insertHelp(root, key, value);
    }

    private BinNode<K, V> insertHelp(BinNode<K, V> rt, K key, V value) {
        if (rt == null) {
            return new BinNode<K, V>(key, value);
        }

        if (key.compareTo(rt.getKey()) < 0) {
            rt.setLeft(insertHelp(rt.getLeft(), key, value));
        }//跟删除结点有异曲同工之妙

        else if (key.compareTo(rt.getKey()) > 0) {
            rt.setRight(insertHelp(rt.getRight(), key, value));
        }

        else {
            rt.setValue(value);
        }//key值相同则更新
        return rt;
    }

    /**
     *
     * @param key 关键字
     * @return 删除的结点的值
     */
    public V remove(K key) {
        removeValue = null;
        try {
            if (key == null)
                throw new Exception("Key is null, remove failure");
            root = removeHelp(root, key);
            return removeValue;
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }
    }

    private BinNode<K, V> removeHelp(BinNode<K, V> rt, K key) {
        if (rt == null)
            return null;
        if (key.compareTo(rt.getKey()) < 0) {
            rt.setLeft(removeHelp(rt.getLeft(), key));
        } else if (key.compareTo(rt.getKey()) > 0) {
            rt.setRight(removeHelp(rt.getRight(), key));
        } else {
            if (rt.getLeft() == null) {
                removeValue = rt.getValue();
                rt = rt.getRight();
                //左子结点为空，直接将右子结点作为当前根结点
            } else if (rt.getRight() == null) {
                removeValue = rt.getValue();
                rt = rt.getLeft();
                //右子结点为空，直接将左子结点作为当前根结点
            } else {
                //待删除结点有两个子结点
                rt.setKey((K) getMinNode(rt.getRight()).getKey());
                rt.setValue((V) getMinNode(rt.getRight()).getValue());
                //将当前结点的key和value更新为右子树中的最小结点的值
                rt.setRight(removeMinNode(rt.getRight()));
                //将当前结点的右子结点进行更新
            }
        }
        return rt;
    }

    private BinNode getMinNode(BinNode<K, V> rt) {
        if (rt.getLeft() == null)
            return rt;
        else
            return getMinNode(rt.getLeft());
    }

    //返回的是更新以后的根结点
    private BinNode<K, V> removeMinNode(BinNode<K, V> rt) {
        if (rt.getLeft() == null) {
            return rt.getRight();
        }
        rt.setLeft(removeMinNode(rt.getLeft()));
        //保证了二叉检索树的规范性
        return rt;
    }

    public V search(K key) {
        return search(root, key);
    }

    private V search(BinNode<K, V> rt, K key) {
        try {
            if (key == null)
                throw new Exception("key is null");
            if (rt == null)
                return null;
            if (key.compareTo(rt.getKey()) < 0)
                return search(rt.getLeft(), key);//小于当前key值则往左子树查找
            if (key.compareTo(rt.getKey()) > 0)
                return search(rt.getRight(), key);//大于当前key值则往右子树查找
            return rt.getValue();//找到值
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }
    }

    public boolean update(K key, V value) {
        return update(root, key, value);
    }

    public boolean update(BinNode<K, V> rt, K key, V value) {
        try {
            if (key == null)
                throw new Exception("Key is null, update failure.");
            if (value == null)
                throw new Exception("value is null, update failure");
            if (key.compareTo(rt.getKey()) == 0) {
                rt.setValue(value);
                return true;
            }
            if (key.compareTo(rt.getKey()) < 0)
                return update(rt.getLeft(), key, value);
            if (key.compareTo(rt.getKey()) > 0)
                return update(rt.getRight(), key, value);
            return false;
        } catch (Exception e) {
            e.printStackTrace();
            return false;
        }
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void clear() {
        root = null;
    }


    public int getHeight(BinNode<K, V> rt) {
        int height = 0;
        if (rt == null)
            return 0;
        else
            height++;
        height += Math.max(getHeight(rt.getLeft()), getHeight(rt.getRight()));
        return height;
    }

}