数据结构与算法09 -- 二叉搜索树(Binary Search Tree)

二叉搜索树(Binary Search Tree)

首先引入一个案例：

在n个动态的整数中搜索某个整数，查看其是否存在？
如果使用动态数组无序，从第0位开始遍历搜索，其时间复杂度为：O(n)
如果使用动态数组有序，可使用二分查找，其最坏时间复杂度为：O(logn)
在动态数组中插入与删除需要移动数组元素，其平均时间复杂度为：O(n)
针对上面的需求，使用二叉搜索树，添加，删除，搜索的最坏时间复杂度均可优化至O(n)

二叉搜索树定义

二叉搜索树是二叉树的一种，应用十分广泛，简称BST，有被称为二叉查找树，二叉排序树；
任意一个节点的数值都大于其左子树所有节点的数值；
任意一个节点的数值都小于其右子树所有节点的数值；
它的左右子树也是一棵二叉搜索树；
二叉搜索树可以大大提高搜索数据的效率；
二叉搜索树存储的元素必须具备可比较性，即指定元素比较的规则；

如下图所示：

Snip20210407_30.png

二叉搜索树的接口设计

二叉搜索树YYBinarySearchTree继承自二叉树YYBinaryTree，所以大部分接口在YYBinaryTree父类中已经实现，二叉搜索树YYBinarySearchTree只需要重写自己的特性方法：

节点数据元素的比较规则；
添加元素；
删除元素；
是否包含某个元素；

需要注意的是：

针对于二叉树而言，它的数据元素是没有索引概念的；

二叉搜索树的代码实现如下：

import java.util.Comparator;

public class YYBinarySearchTree<E> extends YYBinaryTree{

    /**
     * 比较器
     */
    private Comparator<E> comparator;

    /**
     * 构造方法 -- 没有比较器
     */
    public YYBinarySearchTree(){
        this(null);
    }

    /**
     * 构造方法 -- 有比较器
     */
    public YYBinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public void addObject(E element){
        elementNotNullCheck(element);

        //添加第一个节点 -- 根节点
        if (root == null){
            root = createNode(element,null);
            size++;
            afterAdd(root);
            return;
        }

        //查找父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null){
            cmp = compare(element,node.element);
            parent = node;
            if (cmp > 0){
                node = node.right;
            }else if (cmp < 0){
                node = node.left;
            }else {//相等
                node.element = element;//针对模型而言 -- 覆盖合理
                return;
            }
        }

        //判断最后一次的比较结果：
        Node newNode = createNode(element,parent);
        if (cmp > 0){
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        size++;

        afterAdd(newNode);
    }

    public void removeObject(E element){
        removeNode(node(element));
    }

    public void clear(){
        root = null;
        size = 0;
    }

    public boolean containsObject(E element){
        return node(element) != null;
    }

    private Node<E> node(E element){
        Node<E> node = root;
        while (node != null){
            int cmp = compare(element,node.element);
            if (cmp == 0){
                return node;
            }else if (cmp > 0){
                node = node.right;
            }else {
                node = node.left;
            }
        }
        return null;
    }

    private void removeNode(Node<E> node){
        if (node == null) return;
        size--;

        if (node.hasTwoNode()){
            //找到后继节点
            Node<E> sNode = succeedNode(node);
            //用后继节点的值覆盖度为2的节点的值
            node.element = sNode.element;
            //删除后继节点
            //node是要删除的节点,现在现将node指向后继节点,然后在下面的逻辑中进行删除操作
            node = sNode;
        }

        //删除node节点
        //能来到这里说明node的度为1或者0
        Node<E> childNode = node.left != null ? node.left : node.right;

        //说明node的度为1
        if (childNode != null){
            childNode.parent = node.parent;
            if (node == null){//node为根节点
                root = childNode;
                childNode.parent = null;
            }else if (node == node.parent.left){
                node.parent.left = childNode;
            }else {
                node.parent.right = childNode;
            }
        }else {//node的度为0,即叶子节点
            if (node.parent == null){//node为根节点
                root = null;
            }else {//node为叶子节点,但不是根节点
                if (node == node.parent.left){//node是其父节点的左子节点
                    node.parent.left = null;
                }else {//node是其父节点的右子节点
                    node.parent.right = null;
                }
            }
        }
    }

    /**
     * 添加节点之后的调整
     * @param node
     */
    protected  void afterAdd(Node<E> node){}


    /**
     * 返回值 = 0 --> e1 = e2
     * 返回值 > 0 --> e1 > e2
     * 返回值 < 0 --> e1 < e2
     * @param e1
     * @param e2
     * @return
     */
    private int compare(E e1,E e2){
        //优先使用比较器
        if (comparator != null){
            return comparator.compare(e1,e2);
        }
        //来到这里说明比较器为空,我们必须要提供比较规则,让对象去实现Comparable接口，提供比较规则
        return ((Comparable<E>)e1).compareTo(e2);
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        toString(root,sb,"");
        return sb.toString();
    }

    private void toString(Node<E> node,StringBuffer sb,String prefix){
        if (node == null) return;
        sb.append(prefix).append(node.element).append("\n");
        toString(node.left,sb,prefix+"L---");
        toString(node.right,sb,prefix+"R---");
    }
}

comparator(比较器)，是指节点元素之间的比较规则，是必须要存在的，只有存在比较规则才能确定节点在二叉搜索树中的位置；
public void addObject(E element)：添加节点，代码如下：代码实现如下：

public void addObject(E element){
        elementNotNullCheck(element);

        //添加第一个节点 -- 根节点
        if (root == null){
            root = new Node(element,null);
            size++;
            return;
        }

        //查找父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null){
            cmp = compare(element,node.element);
            parent = node;
            if (cmp > 0){
                node = node.right;
            }else if (cmp < 0){
                node = node.left;
            }else {//相等
                node.element = element;//针对模型而言 -- 覆盖合理
                return;
            }
        }

        //判断最后一次的比较结果：
        Node newNode = new Node(element,parent);
        if (cmp > 0){
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        size++;
    }

1>判断根节点是否存在，若不存在直接添加为根节点；
2>遍历找到添加节点的父节点parent；添加节点与二叉树中的节点node进行比较，从根节点开始，大于二叉树中的节点，node取右节点，小于node取左节点，依次循环，当node = null时遍历结束；
3>创建新的节点node；
4>parent.left = node或者parent.right = node
public void removeObject(E element)：删除节点，代码实现如下：

    public void removeObject(E element){
        removeNode(node(element));
    }

    private Node<E> node(E element){
        Node<E> node = root;
        while (node != null){
            int cmp = compare(element,node.element);
            if (cmp == 0){
                return node;
            }else if (cmp > 0){
                node = node.right;
            }else {
                node = node.left;
            }
        }
        return null;
    }

    private void removeNode(Node<E> node){
        if (node == null) return;
        size--;

        if (node.hasTwoNode()){
            //找到后继节点
            Node<E> sNode = succeedNode(node);
            //用后继节点的值覆盖度为2的节点的值
            node.element = sNode.element;
            //删除后继节点
            //node是要删除的节点,现在现将node指向后继节点,然后在下面的逻辑中进行删除操作
            node = sNode;
        }

        //删除node节点
        //能来到这里说明node的度为1或者0
        Node<E> childNode = node.left != null ? node.left : node.right;

        //说明node的度为1
        if (childNode != null){
            childNode.parent = node.parent;
            if (node == null){//node为根节点
                root = childNode;
                childNode.parent = null;
            }else if (node == node.parent.left){
                node.parent.left = childNode;
            }else {
                node.parent.right = childNode;
            }
        }else {//node的度为0,即叶子节点
            if (node.parent == null){//node为根节点
                root = null;
            }else {//node为叶子节点,但不是根节点
                if (node == node.parent.left){//node是其父节点的左子节点
                    node.parent.left = null;
                }else {//node是其父节点的右子节点
                    node.parent.right = null;
                }
            }
        }
    }

删除度为2的节点：
- 找到待删除节点的前驱或者后继节点，然后用前驱或者后继节点的值去覆盖待删除节点的值；
- 最后将待删除节点的前驱或者后继节点删除。

如下图所示：删除节点7

Snip20210421_37.png

删除度为1的节点：
- 用待删除节点的子节点child 替代待删除节点的位置，
- 若待删除节点是其父节点的左子节点：
  - 待删除节点的父节点的left指向待删除节点的子节点，即node.parent.left = child
  - 待删除节点的子节点的父节点指向待删除节点的父节点，即child.parent = node.parent

如下所示：删除节点4