数据结构之二叉搜索树（Binary Search-Tree）

在开始之前现给大家安利一个网站，visoAlgo，非常有意思的一个网站，对于算法初学者来说非常友好，它可以把算法执行的过程用图形的方式表现出来，包括常见的排序算法、链表、树算法、图算法、递归、动态规划等。不得不感叹现在能有的学习资源真是太丰富了，要是当时我学习算法的时候能有这样一个网站来参考学习，也许也不会匆匆就结束的我ACM之旅了（太丢人，不多说了）。
这是树结构系列文章第二篇，阅读本篇之前建议阅读第一篇数据结构之二叉树（Binary-Tree）

1、定义

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

如图，上图就一个典型的二叉搜索树，它每一个节点的左子树都比它要小，同时它的右子树的节点的值都比它大。

2、查找

  二叉搜索树的查找其实还是很简单的，我们可以根据二叉搜索树的定义，轻松写出查找算法。核心思路就是从二叉树的根（root）开始查找，如果要查找的的值假设为A，如果A大于当前node的值，则从当前节点的右子树再查找；如果A小于当前node的值，则从当前节点的左子树再查找；如果A的值正好等于当前node的值，那么就代表找到了。如果遍历完整个树也没有找到，则说明要查找的A不在树中。看代码。

	/**
     * 二叉搜索树查找的递归实现
     */
    private Node<K, V> findInternalR(Node<K, V> node, K key) {
        if (node == null) {
            return null;
        }
        int cpr = key.compareTo(node.key);
        if (cpr == 0) {
            return node;
        } else if (cpr > 0) {
            return findInternalR(node.right, key);
        } else {
            return findInternalR(node.left, key);
        }
    }

3、插入

  二叉搜索树的插入其实也很简单，和查找类似，从二叉树的根（root）开始查找，

• 如果要插入的值假设为A，如果A大于当前node的值，如果node的右子树是null，这将A当作node的右子树；如果node的右子树不为null，则从node的右子树寻找插入位置；
• 如果A小于当前node的值，如果node的左子树是null，这将A当作node的左子树；如果node的左子树不为null，则从node的左子树寻找插入位置；如果A的值正好等于当前node的值，说明该节点已经插入到了树中，不需要再插入了。看代码

    /**
     * 二叉搜索树插入的递归实现
     */
    private Node<K, V> insertInternalR(Node<K, V> node, Node<K, V> parent, K key, V value) {
        if (node == null) {
            return new Node<>(key, value, parent);
        }
        int cpr = key.compareTo(node.key);
        if (cpr > 0) {
            node.right = insertInternalR(node.right, node, key, value);
        } else if (cpr < 0) {
            node.left = insertInternalR(node.left, node, key, value);
        } else {
            //tree has the same key,can not insert again.
            System.out.println("tree has the same key,can not insert again.");
            return null;
        }
        return node;
    }

4、删除

  不同于二叉搜索树的查找和插入，二叉搜索树的删除还是有点难度的。要理解二叉搜索树的删除，必须要先要了解几个概念，以节点为根（root）的树最小节点和最大节点，节点的前驱结点和后继节点。
  首先说一下以A节点为根（root）的树最小节点和最大节点，首先最小节点在哪里呢，根据定义一定是在A节点的左孩子节点–>左孩子节点–>左孩子节点…–>左孩子节点，直到左子树为空，那么前一个节点就是最小节点。同样A节点的最大节点一定是在A节点的右孩子节点–>右孩子节点–>右孩子节点…–>右孩子节点，直到右子树为空，那么前一个节点就是最大节点。
  什么叫节点（A节点）的前驱结点呢？顾名思义，就是该节点（A节点）的前面的节点并且紧靠着该节点（A节点），我们可以认为就是大于该节点，并且是大于该节点的值的最小的。同理A节点的后继节点就是A节点的后面的节点，并且紧挨着A节点，也就是小于A节点的值，但是小于A节点中的最大的那个。看图，

那么我们怎么用代码来求节点的前驱结点和后继节点呢？以节点的前驱结点为例。

• 如果A节点有右子树，那么A节点的前驱结点一定在A的右子树里。为啥呢？当然是因为定义啊，只有比A大的才能进入A的右子树啊。所以A的右子树的所有节点都比A大！但是我们要找的前驱结点是所有比A大的节点中最小的节点，也就是要从A的右子树中找到最小的那个。怎么找上面我们也已经介绍了。
• 那么如果A的右子树为空怎么办?这个时候我们需要看一下A节点有没有父节点，并且A节点是不是父节点的左孩子节点，如果是(这个时候根据定义说明A的父节点比A的值要大)，再循环判断A的父亲节点的父亲节点，也就是A的祖父节点是不是满足以上条件，直到不满足条件为止，然后前一个节点就是比A节点所有节点中最小的那个。

A的后继节点和前驱结点的求法逻辑上是一样。下面我们看看图和代码吧

    /**
     * @return 前驱结点
     */
    public Node<K, V> predecessor() {
        if (this.right != null) {
            Node<K, V> p = this.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            Node<K, V> p = this.parent;
            Node<K, V> ch = this;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

    /**
     * @return 后继节点
     */
    public Node<K, V> successor() {
        if (this.left != null) {
            Node<K, V> p = this.left;
            while (p.right != null)
                p = p.right;
            return p;
        } else {
            Node<K, V> p = this.parent;
            Node<K, V> ch = this;
            while (p != null && ch == p.left) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

理解了前驱结点和后继节点，我们正式开始讲二叉搜索树的删除。要想从树中删除某个节点，我们得先从树中找到它。先用查找函数找到要删除的节点A，如果没找到就返回。找到A之后，然后进行判断

• A是不是叶子节点（就是左右孩子节点都没有的节点），如果是，就直接删除；
• A是不是只有一个孩子节点，如果是，则将A删除，然后将A的父亲指向A的孩子。
• 如果以上两种情况都不满足，说明A既有左孩子，又有有孩子。这个时候要删除A，我们可以先找到A的前驱结点A-predecessor（后继节点也可以），然后将A的值替换成A的前驱结点A-predecessor的值，然后删除A-predecessor节点，这样就相当于删除了A节点。因为A-predecessor节点一定不会同时包含左右孩子节点，所以我们就可以考虑前两种情况的删除了。

那为什么我们要在删除A节点的将A的前驱结点替换A节点呢？考虑一下，我们能不能直接删除A节点？不能。为啥，因为A节点有两个孩子，我们该把哪个孩子链接到A的父亲节点呢？事实上没办法。如果我们不改变树的拓朴结构能不能把A删除呢？当然可以，但是我们要找到能替换A的节点，这个节点要满足以下两点，首先它要比它的左子树都要大，然后还要比右子树小，这样就不会改变原来书的拓扑结构。这两点要满足，不就是A的前驱结点或者后继节点嘛！所以只需要找到A的前驱（或者后继）节点，然后将A的值替换成前驱（后继）节点的值，然后再删除掉前驱节点就可以了！

5、源码

对代码有兴趣的小伙伴，可以直接去github上查看，Algorithm，代码路径fresh.lee.algorithm.java.tree。欢迎fork，star，讨论!