二叉搜索树

作者: 范柏柏 | 来源:发表于2020-05-12 21:00 被阅读0次

引入

上一节讲的是二叉树，那二叉搜索树是为什么出现的呢？它解决了二叉树的什么问题？

可以简单理解为：二叉树和散列表是并列的，查询查找删除都很快，任何散列表都可以用二叉树实现，二叉树也可以使用散列表实现。

但散列表是无序的，怎么让散列表有序呢，通过双向链表串联数组上挂的单链表，详情可以看散列表这一章节。
二叉树也是无序的，怎么让二叉树也有序呢？这就引出了本章的内容 二叉搜索树。

二叉搜索树（Binary Search Tree）

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？

这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉搜索树.png

查找操作

来看看如何在二叉搜索树中查找一个节点。我们先获取根节点，如果等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中查找。

查找.png

插入操作

新插入的数据，都是在 叶子节点上，所以我们只需要从跟节点开始，依次比较要插入的数据和节点的大小关系。

如果新插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插入到右子节点的位置；如果不为空，就再遍历右子树，查找插入位置。同理，如果要插入的数据比节点值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，递归遍历左子树，查找插入位置。

插入55.png

删除操作

删除相比查找和插入较复杂一些，分3种情况。

第一种情况：如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为null。比如图中删除节点55

第二种情况：如果要删除的节点只有一个子节点（只有左子节点或只有右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中删除节点13

第三种情况：如果要删除的节点有两个子节点，就比较复杂了。我们需要找到这个节点右子树中的最小节点，把它替换到删除的节点上。然后删除这个最小节点。因为最小节点肯定没有左节点（有左节点就不是最小节点了），所以，应用上两条来删除这个最小节点就可以了。比如图中删除节点18

删除操作.png

实际上，删除操作还有个非常简单、取巧的方法，就是单纯的将要删除的节点标记为"已删除"，也就是"逻辑删除"。这样做只是比较浪费内存，但大大减少了代码实现的难度。这点内存在现阶段，其实可以忽略不计。

上代码

public class BinarySearchTree extends BinaryTree {

    /**
     * 定义根节点
     */
    private static TreeNode root;

    /**
     * 查找
     */
    private static TreeNode find(int data) {
        TreeNode p = root;
        while (p != null) {
            if (p.key == data) {
                return p;
            } else if (p.key < data) {
                p = p.leftChild;
            } else {
                p = p.rightChild;
            }
        }
        return null;
    }

    /**
     * 插入
     */
    private static void insert(int data) {
        if (root == null) {
            root = new TreeNode(data, "");
            return;
        }

        TreeNode p = root;
        while (p != null) {

            if (data < p.key) {

                if (p.leftChild == null) {
                    p.leftChild = new TreeNode(data, "");
                    return;
                } else {
                    p = p.leftChild;
                }
            } else {

                if (p.rightChild == null) {
                    p.rightChild = new TreeNode(data, "");
                    return;
                } else {
                    p = p.rightChild;
                }
            }
        }
    }

    /**
     * 删除
     */
    private static void delete(int data) {

        TreeNode p = root;

        // pp 记录的是p的父节点
        TreeNode pp = null;

        // 先找到它，再分情况
        while (p != null && p.key != data) {

           if (p.key < data) {
                pp = p;
                p = p.leftChild;
            } else {
                pp = p;
                p = p.rightChild;
            }
        }

        // 到这里就是找到了, 或者轮训完了
        if (p == null) {
            // 没找到
            return;
        }

        // 1.要删除的节点有左右两个子节点
        if (p.leftChild != null && p.rightChild != null) {

            // 现在要做的就是找到右子树里面最小的那个节点  跟现在这个节点换一下
            TreeNode minP = p.rightChild;
            TreeNode minPP = p;

            while (minP.leftChild != null) {
                minPP = minP;
                minP = minPP.leftChild;
            }

            // 现在minP就是 右子树里面最小的那个节点 了
            // 1.1 先把这个节点的值，赋值给删除节点
            p.data = minP.data;

            // 1.2 删除这个 最小节点
            minPP.leftChild = null;

            return;
        }

        // 2.要删除的节点没有子节点 或 只有一个叶子节点
        // 那直接挂过去就行了
        TreeNode child;
        if (p.leftChild != null) {
            child = p.leftChild;
        } else if (p.rightChild != null) {
            child = p.rightChild;
        } else {
            child = null;
        }

        if (pp == null) {
            // 删除的是根节点
            root = child;
        } else if (pp.leftChild == p) {
            pp.leftChild = child;
        } else {
            pp.rightChild = child;
        }
    }

    public static void main(String[] args) {

        insert(1);
        insert(2);
        insert(3);
        insert(4);
        insert(5);
        insert(6);
        insert(11);
        insert(12);
        insert(13);
        insert(14);
        insert(15);
        insert(16);

        System.out.println("=============原始树=================");
        inOrder(root);
        System.out.println("=====================================");

        System.out.println("=============添加99=================");
        insert(99);
        inOrder(root);
        System.out.println("=====================================");

        System.out.println("=============删除12=================");
        delete(12);
        inOrder(root);
        System.out.println("=====================================");

        System.out.println("=============查询11=================");
        TreeNode node = find(11);
        visited(node);
        System.out.println("=====================================");
    }
}

支持重复数据的二叉搜索树

和散列表一样的问题。当一样的数据，被放到同一个格里时，要怎么处理呢？
1、放入右子树，也就是说，把这个新插入的数据当做大于这个节点的值来处理
2、也是链表法。在这个节点上存链表。