红黑树的解析与实现（一）二叉查找树（Binary Sort Tree）

关于红黑树

        虽然可以直接看，但是个人是参考了《算法》这本书，然后关于红黑树的部分，忽略了与AVL树的相关内容，但是是按照：二叉查找树、2-3树、红黑树的顺序写的，然后我个人也就按照这样的方式实现一遍了。这三篇博文（大概）会忽略很多原理的东西，简单的查找等方法就不多说了，专注于实现以及相关解析以及比较少用的一些操作，例如向下取整等，算法复杂度分析之类的都忽略了，毕竟网上讲得也很多。然后后面的实现都是Java语言，并没有C/C++版本。

二叉查找树

        实际上，如果对二叉查找树还不知道的话= =也没必要看红黑树了，关于性质之类的可以参考wiki、百度百科或者其他博客。这里说明一点：至少从我个人的角度，是因为在分析Java容器Map的时候觉得需要先看一下红黑树，也是因为这个容器才知道有红黑树这个数据结构（当然也是网上都说难的不行= =）。但是关于二叉查找树，我们一般是类比二分搜索，仿佛跟Key-Value这样的结构并不一致。但是，在Java上，如果我们能在定义节点的时候，专门声明了Key与Value，并且在Key上定义comparator，那么是否就是通过对Key的排序，获取一个顺序序列，并且根据Key可以找到对应的Value。

        那么如果说红黑树是二叉查找树的升级版，因为红黑树是保证平衡的，也就可以理解为什么Map的底层是一棵红黑树。我们这样来定义树，也可以完成Key-Value的模式。从而支持了高效查找。例如下图：

对于这个节点，编号就是Key，名字就是Value，如果设定Key的comparator，那么就按照编号来排序，在搜索某个编号的时候就能以O(logn)的复杂度搜索到对应的人的名字。

二叉查找树的定义与结点的定义

        key与value是必须的，此外，想要同时对key定义一个comparator。由于Java语言，我们可以声明一个BST类，其中的内部类（或者可以专门写出来）可以有Node作为结点。那么可以这样来写：

class BST<Key extends Comparable<Key>, Value>{
    private Node root;

    private class Node{
        private Key key;
        private Value value;
        private Node left;
        private Node right;
        
        public Node(Key key,Value value){
            this.key = key;
            this.value = value;
        }
    }
}

这里说明一下，泛型是必要的，并且让Key继承Comparable，这样，我们在实际算法中，使用compareTo方法，就可以进行比较。使用的话，先new出来BST对象，然后调用例如put、get方法等等，这个后面再实现。

二叉查找树的查找

        很简单，就跟二分一样，从根开始搜，如果比该结点的key小，那么则进入左子树，大则进入右子树。若相等，则表示搜索到了，若最终搜索到null仍未找到，那么就返回未搜索到。

        自然，递归是非常简单明了的表现方式，但是递归的效率相对略低，但是比较容易理解。这里先写一个递归的写法：

    public Value get(Key key){
        if(key == null) return null;
        return get(this.root,key);
    }
    public Value get(Node root,Key key){
        if(root == null) return null;
        int cmp = key.compareTo(root.key);
        if(cmp == 0){
            return root.value;
        }else{
            if(cmp < 0){
                return get(root.left,key);
            }else{
                return get(root.right,key);
            }
        }
    }

还是比较简单明了的，其实转化成非递归也非常容易：

    public Value get(Key key){
        if(key == null) return null;
        return get(this.root,key);
    }
    public Value get(Node root,Key key){
        while(root != null){
            int cmp = key.compareTo(root.key);
            if(cmp == 0) return root.value;
            if(cmp < 0){
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return null;
    }

为什么要写get的两个重载方法？这样对于用户比较友好，用户只用输入Key就行了，其他一概不管。主要是这样写，root就作为引用传入重载方法，那么我们对root的操作，不会影响到这棵树的真实root值。这个是Java SE的内容，如果有疑惑的同学可以自己试试不用重载方法，会出bug的——在操作的时候，root对应的Node变了。或者改成下面的写法也可以，用一个变量引用root。就像下面的max()方法。

二叉查找树-查找最大值与最小值

        更简单了，一直向右子树前进直到叶子节点，就是最大值，反之则是最小值。简单的不行，就写个查最大值的算法：

    public Value max(){
        if(root == null) return null;
        Node n = root;
        while(n.right != null){
            n = n.right;
        }
        return n.value;
    }

二叉查找树-查找的时候向下取整或者向上取整

        这个略微麻烦一点，并且可能有点不太懂。这个向上取整和向下取整是书上的翻译，感觉有点不合适，其实就是对于一个二叉查找树而言，查找其中的key为x的元素对应的value。查找到了就返回，若没有查找到：返回比x小的最接近x的元素，或者返回比x大的最接近x的元素。例如对于序列：[1,2,3,4,5,7,8,9]。如果搜索6，实际上是没有6的，那么向下取整方法floor()，的返回值是5，向上取整方法ceiling()则返回7。

        整个算法有点蛋疼，但是我们一floor，向下取整方法为例，分析一下在搜索过程中可能碰见的几种情况，首先当然是从根开始，这些跟正常搜索一样，关键在于对根第一次匹配，如果小或者大了该怎么处理，抽象一下，对于任意子树的根节点，有几种判定情况：

1.key = root.key。找到了，那就不多说，返回就完事了，没啥好说的，大团圆。

2.key < root.key。此时小了，那么也就是说该树的根以及右子树完全不存在答案，我们应该从左子树开始继续搜索。但是需要明确一点，左子树中一定存在答案。那么直接搜left就行了，递归的话，就可以开始递归调用了。

3.key > root.key。此时大了，那么也就是说，我们需要向右子树开始继续搜索。但是这里注意一点，root.key可能就是答案。假设树的局部是这样的：

而我们搜索的是2。那么刚开始是1，进入右子树，而右子树是3，并且是叶子了。那么最终的答案是1。但是如果3的左子树就是2呢，答案其实就是2了。所以说，在进入右子树的时候，root是有作为答案输出的可能的，所以需要记录root。

        总结：找到就不说了，当进入左子树的时候，就是正常进入。当进入右子树的时候，需要临时记录root为res，如果res存在，则更新res。

        这样分析，算法就比较简单了，而向上取整，就是相反，进入左子树的时候临时记录更新，右子树直接进入。同样，没有写递归算法（当然递归是真的简单），仅仅实现向下取整floor：

    public Value floor(Key key){
        if(root == null || key == null) return null;
        return floor(root,key);
    }
    public Value floor(Node root,Key key){
        Value res = null;
        while(root != null){
            int cmp = key.compareTo(root.key);
            if(cmp == 0) return root.value;
            if(cmp < 0){
                root = root.left;
            }else{
                res = root.value;
                root = root.right;
            }
        }
        return res;
    }

二叉查找树-插入

        首先明白一点，根据二叉查找树的性质，插入的位置一定作为一个叶子结点，不可能是在中间进行插入的。但是删除是可以从中间删除，甚至是删除根。但是这个是删除需要考虑的，一般删除的算法也是最麻烦的。对于插入算法而言，首先是应该搜索——如果搜索到了，对于我们Key-Value这样的写法，是应该更新value的。如果没有搜索到，就new出来结点。

        根据这样的情况，我们可以先搜索，再根据搜索结果判定如何插入。但是不能直接调用get()，而是应该手动实现。自然，下面就不用递归写法了，直接写非递归的。当然，刚开始得考虑root为空的情况，此时直接new出来作为root。

    public void put(Key key,Value value){
        if(key == null || value == null) return;
        if(root == null){
            root = new Node(key,value);
            return;
        }
        put(root,key,value);
    }
    public void put(Node root,Key key,Value value){
        while(root != null){
            int cmp = key.compareTo(root.key);
            if(cmp == 0){
                root.value = value;
                return;
            }
            if(cmp < 0){
                if(root.left == null){
                    root.left = new Node(key,value);
                    return;
                }else{
                    root = root.left;
                }
            }else{
                if(root.right == null){
                    root.right = new Node(key,value);
                    return;
                }else{
                    root = root.right;
                }
            }
        }
    }

嵌套可能略多了，不好看，但是懂意思就行= =。

二叉查找树-删除最小值与最大值

        删除最核心的问题是：删除某个结点后，该结点的左右子树应该怎么办。1962年Hibbard提出了现在一般使用的删除算法。这个算法首先需要先了解如何删除最小值与最大值。

        首先比较容易想到的就是：一直左搜索就能找到最小值，一直向右就是最大值。但是删除需要考虑的问题是，最大/小结点可能存在子树。例如找最小值，一直左搜到最后的结点，该结点如果是叶子结点——直接删除，但是如果有右子树的话，就需要一些其他处理了。

        还是以删除最小值为例：在一路向左搜索直到碰见null，那么将右结点直接接到最小值的父结点即可，例：

那么代码也就显而易见了：