09_算法基本概念(Java、Kotlin描述)

    本篇文章介绍一些算法里用到的基本概念。

(1)递归

    一个微妙的递归算法，代码如下：

    public static int bad(int n) {
        if (n == 0)
            return 0;
        else
            return bad(n / 3 + 1) + n - 1;
    }

    初一看，好像没什么问题。但如果n=1，那么会出现bad(1) = bad(1)。而bad(1)的值究竟是多少，不知道。
    这里就需要了解递归的两个基本法则：
        1）基准情形(base case)，必须总有某些基准的情形，它们不用递归就能求解；
        2）不断推进，递归调用必须总能够朝着一个基准情形推进。
    上面的代码违反了第2)条，递归调用最终并没有推进到基准情形。推进到bad(1)就陷入死循环了。

(2)散列

• 散列(hashing)是一种用于以常数平均时间插入、删除和查找的技术。需要排序信息的操作则不支持，如findMax、findMin等。散列是散列表的一种实现；
• 散列函数：将关键字映射到0到size-1这个范围中的函数，称为散列函数；一个简单示例：key % size ；另外一个示例，Java版本：

    public static int hash(String key , int size){
        int hash = 0;
        for (int i =0 ; i < key.length() ; i++){
            hash += key.charAt(i);
        }
        return hash % size;
    }

    Kotlin版本：

    fun hash(key: String, size: Int): Int {
        var hash = 0
        for (i in 0 until key.length) {
            hash += key[i].code
        }
        return hash % size
    }

• 散列冲突：两个关键字散列到同一个值；
• 分离链接法：将冲突的元素保留到一个链表中，如Java中的HashMap、HashSet实现方式；

(3)中缀表达式转后缀表达式

    中缀表达式就是我们常见的算术表达式，如 a + b * c + (d * e + f) * g。后缀表达式是一种将操作数放在前，操作符放在后面的表达式，它不使用圆括号。最简单后缀表达式如“ab+”，它对应的中缀表达式是"a+b"。中缀表达式对于人来说非常容易理解，但对于计算机来说太复杂 。而后缀表达式则相反。
     a + b * c + (d * e + f) * g 转换为后缀表达式的结果是：abc * + de * f + q * +。
    这个转换需要用到Stack数据结构。对中缀表达式的每个字符，如果是操作数，则放到输出中；如果是操作符，则根据栈顶情况处理。
        1）如果栈顶的操作符优先级高，那么将它立即出栈；如果两者优先级一样，也立即出栈；如果栈顶操作符优先级低，则入栈。
        2）对于圆括号 "(" 和 ")"，左括号直接入栈；只有遇到右括号，才移走左括号。
    后缀表达式的求值：也使用一个栈，不过处理的不是操作符，而是操作数。对每个字符，如果是操作数，就入栈；如果是操作符，则从栈顶弹出2个操作数并进行计算，计算结果入栈。如此循环，直到处理完表达式中的所有字符。最后，栈中只剩下一个元素，就是表达式的求值结果。

(4)树的一些基本概念

• 树是一种非线性结构；
• 树是一些节点的集合。这个集合可以是空集，如果不是空集，则由根节点和子树组成；
• 一棵树是N个节点和N-1条边的集合。除了根节点外，每个节点都有一个父亲；
• 只有根节点没有直接前驱，其他节点有且仅有一个直接前驱；
• 每个节点可以有任意多个直接后继；
• 兄弟节点：具有同一个父节点的节点；
• 节点的度：一个节点所包含子树的数量；
• 树的度：该树所有节点中最大的度；
• 节点的层数：根节点的层数是1，依次向下。树是一种层次结构，每个节点都处在一定的层次上。
• 树的深度：树中节点的最大层数称为树的深度
• 树的表示法：层次括号法，如( A )表示只有一个根节点A；( A( B , C ) )表示3个节点组成的树，A是根节点，B、C是A的直接后继节点；以此类推；
• 有序树：树中各节点的子树是按一定次序从左向右安排的；
• 无序树：与有序树相反；
• 森林：多棵互不相交的树的集合；
• 先序遍历：先处理节点，再处理孩子；
• 后序遍历：先处理孩子，再处理节点；
• 二叉树：每个节点，子节点数不超过2；
• 中序遍历：先处理左孩子，再处理节点，最后处理右孩子。针对二叉树而言。

    二叉树的一般结构：

class BinaryNode {
    Object element;
    BinaryNode left;
    BinaryNode right;
}

• 表达式树：树叶是操作数，其他是操作符。从后缀表达式可以构造一个表达式树；
• 二叉查找树：对于每个节点X，它的左子树中所有项的值都小于X中的项，右子树则相反；它的平均深度是O(log N);
• AVL树：带有平衡条件的二叉查找树，每个节点的左子树和右子树的高度最多相差1；除去插入操作外(惰性删除)，所有的树操作都是O(log N)。插入操作可能会破坏AVL树的特性，这种特性需要“旋转”操作来维持。插入一个新节点后，如果节点A的AVL性质被破坏了，那么新节点的位置存在下列几种情况：

1. A的左儿子的左子树；
2. A的左儿子的右子树；
3. A的右儿子的左子树；
4. A的右儿子的右子树；

    这可以归为两种情况，一种是插入发生在“外边”的情况，即左-左、右-右，另外一种是插入发生在“内部”的情况，即左-右、右-左。第一种情况需要“单旋转”来进行调整；第二种情况需要“双旋转”进行调整。
    Java实现如下：

public class AVLTree {
    //节点
    class Node {
        int data;
        Node leftChild;
        Node rightChild;
        int height;

        public Node(int data) {
            this(data, null, null);
        }

        public Node(int data, Node leftChild, Node rightChild) {
            this.data = data;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

    int height(Node node) {
        return node == null ? -1 : node.height;
    }

    /**
     * 更新节点node的高度
     *
     * @param node
     */
    void updateHeight(Node node) {
        int leftHeight = height(node.leftChild);
        int rightHeight = height(node.rightChild);
        node.height = Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 节点左、右子树的高度差
     * 如果返回值为正，说明右子树较高
     *
     * @param node
     * @return
     */
    int balanceFactor(Node node) {
        return height(node.rightChild) - height(node.leftChild);
    }

    //右旋
    Node rotateRight(Node node) {
        Node left = node.leftChild;
        node.leftChild = left.rightChild;
        left.rightChild = node;
        updateHeight(left);
        updateHeight(node);
        return left;
    }

    //左旋
    Node rotateLeft(Node node) {
        Node right = node.rightChild;
        node.rightChild = right.leftChild;
        right.leftChild = node;
        updateHeight(right);
        updateHeight(node);
        return right;
    }

    //使节点node保持AVL树特性
    Node reBalance(Node node) {
        //如果为正，说明右子树高；如果为副，说明左子树高。绝对值如果大于1，说明AVL特性被破坏
        int balanceFactor = balanceFactor(node);
        if (balanceFactor < -1) {//左子树高，特性被破坏
            if (balanceFactor(node.leftChild) < 0) { //左-左情况，右旋
                node = rotateRight(node);
            } else { //左-右情况，先左旋，再右旋
                node.leftChild = rotateLeft(node.rightChild);
                node = rotateRight(node);
            }
        }
        if (balanceFactor > 1) {//右子树高
            if (balanceFactor(node.rightChild) > 0) {//右-右情况，左旋
                node = rotateLeft(node);
            } else {//右-左情况，先右旋，再左旋
                node.rightChild = rotateRight(node);
                node = rotateLeft(node);
            }
        }
        return node;
    }

    //插入一个新节点
    Node insertNode(int data, Node node) {
        if (node == null) {
            return new Node(data);
        }
        if (data < node.data) {
            node.leftChild = insertNode(data, node.leftChild);
        } else if (data > node.data) {
            node.rightChild = insertNode(data, node.rightChild);
        } else { //重复了
            return node;
        }

        updateHeight(node);
        return reBalance(node);
    }

    //删除节点
    Node deleteNode(int data, Node node) {
        if (node == null) return null;
        if (data < node.data) {
            node.leftChild = deleteNode(data, node.leftChild);
        } else if (data > node.data) {
            node.rightChild = deleteNode(data, node.rightChild);
        } else if (node.leftChild == null && node.rightChild == null) {
            return null;
        } else if (node.leftChild == null) {//节点只有右孩子
            node = node.rightChild;
        } else if (node.rightChild == null) { //节点只有左孩子
            node = node.leftChild;
        } else { //节点左右孩子都有
            //找到右子树的最小节点
            Node minNode = node.rightChild;
            while (minNode.leftChild != null) {
                minNode = minNode.leftChild;
            }
            //将最小点的值保存到node
            node.data = minNode.data;
            node.rightChild = deleteNode(minNode.data,node.rightChild); //删除右子树的最小点，因为它已经移到node了
        }
        updateHeight(node);
        return reBalance(node);
    }
}

• 层序遍历：所有深度为d的节点，要在深度为d+1的节点之前处理。

• 满二叉树：除了叶子节点外，其他节点都有2个子节点；

• 完全二叉树：除最后一层外，其他各层的节点数都是2，且最后一层叶节点按照从左至右的顺序连续存在，只缺最后一层右侧若干节点；

• B树：当数据结构非常大，内存装不下时，就需要用到B树。它用来平衡cpu计算速度和磁盘访问速度不匹配的问题。

• M叉查找树：有M路分支的查找树，一颗完全M叉查找树的高度大约是logN 。

• 摊还时间：当M次操作的序列总的最坏情形运行时间为O(M f(N))时，我们就说它的摊还运行时间为O(f(N))。

• 伸展树：从空树开始，连续M次对树的操作最多花费O(M logN)时间的一种二叉树。伸展树的摊还时间是O(log N)。它的基本想法如下：

    当一个节点被访问后，它就要经过一系列AVL树的旋转被推到根上；如果一个节点很深，那么在其路径上就存在许多相对较深的节点，通过重新构造可以减少对这些节点的进一步访问时间。伸展树在节点过深时，具有平衡这棵树(某种程度上)的作用。在实际的许多应用中，当一个节点被访问时，它很可能不久再被访问。使用伸展树结构，可以减少查找时间。
    此外，伸展树不要求保留高度或平衡信息。根节点、左孩子和右孩子也没有大小关系，它不是查找树。

(5)图的一些基本概念

• 每个数据元素之间，可以任意关联，构成了一个图结构；
• 图结构包括两个部分：顶点Vertext和边Edge，所有的顶点构成一个顶点集合，记为V(G)；所有的边构成一个边集合，记为E(G)；
• 在数学上，图结构记为：G = (V , E) 或者 G = ( V(G) , V(E) ) ; V(G)必须是非空，V(E)可以为空；
• V(G)示例：V(G) = { V1 , V2 , V3 , V4} ;
• E(G)示例：E(G) = { (V1, V2) , (V1 , V3) , (V2, V4) ,(V1 , V4)} ;
• 在一个图中，所有的边都没有方向性，则它是无向图；无向图中对顶点顺序没有要求，(V1 , V2) 和 (V2 , V1)是一样的；
• 在一个图中，边是有方向性的，则它是有向图；顶点顺序表示指向；用尖括号表示：<V1 , V2> ;
• 顶点的度：连接顶点的边的数量称为度；对于无向图，即为连接顶点的边的数量，记为D(V)；对于有向图，则分为入度ID(V)和出度OD(V)；有向图中顶点的度是入度+出度，D(V) = ID(V) + OD(V)；
• 邻接顶点：一条边的两个顶点；有向图中根据边的方向，分为起始顶点和结束顶点，也分别称为入边邻接点和出边邻接点；
• 无向完全图：如果一个无向图中，每两个顶点之间都存在一条边，那么它是无向完全图；
• 有向完全图：如果一个有向图中，每两个顶点之间都存在方向相反的两条边，那么它是有向完全图；包含N个顶点的有向完全图，边数是N(N-1);
• 子图：类似于子集合，子图的顶点和边都应该是父图的顶点和边的子集；
• 路径：路径是图结构中两个顶点之间的连线；路径上边的数量称为路径长度；两个顶点之间的路径可能有多条，路径长度可能不一样；
• 简单路径：如果一条路径上顶点不重复出现，则称为简单路径；
• 环：如果一条路径的第一个顶点和最后一个顶点相同，则称之为环，也称为回路；
• 简单回路：如果第一个顶点和最后一个顶点相同，其余各点都不重复的回路称为简单回路；
• 连通：如果图结构中，两个顶点之间有路径，则称为这两个顶点是连通的；这两个顶点可以不邻接；
• 连通图：如果无向图中，任意两个顶点都是连通的，那么这个图便称为连通图；
• 连通分量：无向图的极大连通子图；对于一个连通图，其连通分量有且只有一个，就是它自身；非连通图，有多个连通分量；
• 强连通图：如果有向图中，任意两个顶点都是连通的，则称该图为强连通图；注意有向图中边具有方向性；
• 强连通分量：有向图的极大连通子图称为该图的强连通分量；强连通图只有一个强连通分量，就是它自身；
• 权：将边表示为某种数值，这个数值就是权；无向图中加入权，称为无向带图权；有向图中加入权，称为有向带图权；在交通图中，权可以代表路径长度；
• 网：边上带权值的图的另一种名称；
• 邻接矩阵：保存顶点之间关系的数组；示例如下：

char vertex = new char[N] ;// 保存顶点信息
int[][] edgeWeight = new int[N][N];// 保存边的权或者连接关系

• 根据两个顶点的编号，从邻接矩阵中获取值，如果为0表示这两个顶点之间没有边；如果为1，则表示有边；如果大于1，表示权；
• 对于无向图，邻接矩阵左下角和右上角是对称的；
• 图结构，Java语言描述：

public class Graph {
    static final int NUM = 20; //图的顶点数
    char[] vertex = new char[NUM]; //顶点集合
    int gType; //图类型，0表示无向图；1表示有向图
    int vertexNum;//顶点数量
    int[][] edgeWeight = new int[NUM][NUM] ; //邻接矩阵
    int[] isTrav = new int[NUM];
}

    Kotlin版本：

class Graph {
    var vertex = CharArray(NUM) //顶点集合
    var gType //图类型，0表示无向图；1表示有向图
            = 0
    var vertexNum //顶点数量
            = 0
    var edgeWeight = Array(NUM) { IntArray(NUM) } //邻接矩阵
    var isTrav = IntArray(NUM)

    companion object {
        const val NUM = 20 //图的顶点数
    }
}

• 图的遍历，深度优先算法，Java版本：

    void deepTraOne(Graph g,int n){ //从第n个顶点开始
        int i;
        g.isTrav[n] = 1; //标记该顶点已经访问过
        System.out.println(g.vertex[n]); //输出节点数据
        for (i = 0;i<g.vertexNum;i++){
            if (g.edgeWeight[n][i] != 0 && g.isTrav[i] == 0){
                deepTraOne(g,i);
            }
        }
    }
    
    //深度优先遍历
    void deepTraGraph(Graph g){
        int i;
        for (i =0;i<g.vertexNum;i++){
            if (g.isTrav[i] == 0){
                deepTraOne(g,i);
            }
        }
    }

    Kotlin版本：

    fun deepTraOne(g: Graph, n: Int) { //从第n个顶点开始
        var i: Int
        g.isTrav[n] = 1 //标记该顶点已经访问过
        println(g.vertex[n]) //输出节点数据
        i = 0
        while (i < g.vertexNum) {
            if (g.edgeWeight[n][i] != 0 && g.isTrav[i] == 0) {
                deepTraOne(g, i)
            }
            i++
        }
    }

    //深度优先遍历
    fun deepTraGraph(g: Graph) {
        var i: Int
        i = 0
        while (i < g.vertexNum) {
            if (g.isTrav[i] == 0) {
                deepTraOne(g, i)
            }
            i++
        }
    } 

• 生成树：满足这3个条件的的树称为原图的一颗生成树，1)子图的顶点与原图相同；2）子图的边是原图的子集，且这部分边刚好将图中所有顶点连通；3）子图中的边不构成回路；
• 对于有n个顶点的连通图，其生成树有且只有n-1条边。如果边数少于此数，就不可能将所有顶点连通；如果多于此数，则必须产生回路；
• 最小生成树：一个图的生成树可能有多个，其中权值最小的生成树就称为图的最小生成树；

(6)堆

• 优先队列：某些作业应该具有优先权，支持这种特点的队列称为优先队列；
• 优先队列是一种特殊的数据结构，至少支持两种操作：insert 和 deleteMin，即插入和删除最小者；一种简单实现是：以一个单链表为基础，在表头插入数据，并遍历该链表，以删除最小元；
• 堆：也叫二叉堆，可以实现优先队列。堆是一颗完全二叉树，一个高为h的完全堆，有2到2 -1个节点，高是logN ;
• 堆可以用数组来表示，对于数组中任一位置i(为维持特性，从下标1开始)上的元素，其左儿子在位置2i上，右儿子在位置(2i + 1)上，它的父亲则在i/2上；例如一个包含3元素的堆，A(B,C) ，A是根节点，B、C分别为左右子树，那么对应的数组array[ ]大小为3+2，a[1] = A，a[2] = B, a[3] = C ;其中a[0] 和a[4]为空，不使用。
• 对于元素为N个的堆来说，N/2刚好是最后一个非叶节点；
• 大根堆：在堆中，对于每个节点，它的key比左、右孩子的key大或者等，这样的堆称为大根堆；
• 小根堆：在堆中，对于每个节点，它的key比左、右孩子的key小或者等，这样的堆称为小根堆；
• 堆的插入：在size-1位置后，再创建一个空的可用位置，简称空穴，这样保持了堆的特性。如果放入X后，不破坏堆的特性，那么插入完成；如果破坏了，则将空穴朝着根的方向向上冒一步，直至完成。Java版本：

public class BinaryHeap {
    private static final int CAPACITY = 10;
    private int currentSize;
    private int[] heapArray;

    public void insert(int x){
        if (currentSize == heapArray.length -1){
            // 扩展大小，暂略
        }
        int hole = ++currentSize;
        for(;hole >1 && x < heapArray[hole];hole /= 2){
            heapArray[hole] = heapArray[hole/2];
        }
        heapArray[hole] = x;
    }
}

    Kotlin版本：

class BinaryHeap {
    private var currentSize = 0
    private var heapArray: IntArray
    fun insert(x: Int) {
        if (currentSize == heapArray.size - 1) {
            // 扩展大小，暂略
        }
        var hole = ++currentSize
        while (hole > 1 && x < heapArray[hole]) {
            heapArray[hole] = heapArray[hole / 2]
            hole /= 2
        }
        heapArray[hole] = x
    }

    companion object {
        private const val CAPACITY = 10
    }
}

• 堆的构造，Java版本：

public class BinaryHeap {
    private static final int CAPACITY = 10;
    private int currentSize;
    private int[] heapArray;

    public BinaryHeap(int[] items) {
        currentSize = items.length;
        heapArray = new int[(currentSize + 2) * 11 / 10];

        int i = 1;
        for (int item:items){
            heapArray[i++] = item;
        }
        buildHeap();
    }

    private void buildHeap(){
        for (int i = currentSize/2;i>0;i--){ //对每个非叶节点依次处理
            percolateDown(i);
        }
    }

    private void percolateDown(int hole){
        int child;
        int tmp = heapArray[hole];

        for (;hole *2 <= currentSize;hole = child){
            child = hole *2;
            if (child != currentSize && heapArray[child +1] < heapArray[child]){
                child ++;
            }

            if (heapArray[child]<tmp){
                heapArray[hole]= heapArray[child];
            }else {
                break;
            }
        }
        heapArray[hole] = tmp;

    }

    Kotlin版本：

class BinaryHeap(items: IntArray) {
    private val currentSize: Int
    private val heapArray: IntArray

    init {
        currentSize = items.size
        heapArray = IntArray((currentSize + 2) * 11 / 10)
        var i = 1
        for (item in items) {
            heapArray[i++] = item
        }
        buildHeap()
    }

    private fun buildHeap() {
        for (i in currentSize / 2 downTo 1) {
            percolateDown(i)
        }
    }

    private fun percolateDown(hole: Int) {
        var hole = hole
        var child: Int
        val tmp = heapArray[hole]
        while (hole * 2 <= currentSize) {
            child = hole * 2
            if (child != currentSize && heapArray[child + 1] < heapArray[child]) {
                child++
            }
            if (heapArray[child] < tmp) {
                heapArray[hole] = heapArray[child]
            } else {
                break
            }
            hole = child
        }
        heapArray[hole] = tmp
    }

    companion object {
        private const val CAPACITY = 10
    }
}

(7)算法设计思想

    本小节将介绍几种算法设计思想，有：贪婪算法、分治算法、动态规划、回溯算法。

贪婪算法：贪婪算法可谓是大名鼎鼎，使用得非常广泛。它分阶段地工作，每个阶段，可以认为所做决定是好的，而不考虑将来的后果。这常常在局部达到最优，“眼下能够拿到的就拿”。当算法终止时，如果局部最优等于全局最优，那么算法就是正确的；否则，算法得到的就是一个次最优解。代表算法有：Dijkstra算法、Prim算法和Kruskal算法，见 14_业界经典算法第(3)、(4)、(5)小节。

分治算法：将大问题分解成若干子问题，子问题之间相互独立，从子问题的解构建原问题的解。典型的应用如快速排序、归并排序(见 10_经典排序查找算法第(5)、(7)小节)，求最大子序列和算法(见 14_业界经典算法第(1)条中的第三种算法)也用到了它。

动态规划：基本思想和分治算法类似，也是将大问题分解成若干个子问题(阶段)，不同点是这些子问题不是相互独立的，后一个子问题需要用到前一个子问题的结果。将递归算法改为迭代算法时经常要用到这种思想。如斐波那契数列的迭代版本(见 《13_经典数学问题算法》第(8)小节)，就是使用两个参数保留上一次的计算结果，从而将算法由指数版本改为线性版本；迭代版本实现数学递推公式(见 《13_经典数学问题算法》第(10)小节)也用到了它。

回溯算法：很多情况下，回溯算法相当于穷举搜索的巧妙实现，它是一种试探性的算法，在尝试过程中寻找问题的解，如果不满足，就回溯到别的路径。见 《12_经典趣题算法》第(10)小节渔夫捕鱼问题。

(8)红黑树

    红黑树(red-black树)是一种特殊的二叉查找树。对红黑树的操作在最坏情况下花费O(log N)时间。红黑树的每个节点，要么是红色，要么是黑色。它有如下性质：

1. 每一个节点或者是黑色，或者是红色；
2. 根节点是黑色的；
3. 每个叶子节点是黑色的(指为null的节点)；
4. 如果一个节点是红色的，那么它的子节点必须是黑色的；
5. 从一个节点到该节点的子孙节点所有路径包含相同数目的黑色节点。

    红黑树的基本结构和插入操作如下：

public class RBTree<T extends Comparable<T>> {

    public class RBTNode<T extends Comparable<T>> {
        boolean color;        // 颜色
        T key;                // 关键字(键值)
        RBTNode<T> left;    // 左孩子
        RBTNode<T> right;    // 右孩子
        RBTNode<T> parent;    // 父结点

        public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
            this.key = key;
            this.color = color;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

    }

    private RBTNode<T> mRoot;    // 根结点
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    //左旋
    private void leftRotate(RBTNode<T> x) {
        // 设置x的右孩子为y
        RBTNode<T> y = x.right;

        // 将 “y的左孩子” 设为 “x的右孩子”；
        // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
        x.right = y.left;
        if (y.left != null)
            y.left.parent = x;

        // 将 “x的父亲” 设为 “y的父亲”
        y.parent = x.parent;

        if (x.parent == null) {
            this.mRoot = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点
        } else {
            if (x.parent.left == x)
                x.parent.left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
            else
                x.parent.right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
        }

        // 将 “x” 设为 “y的左孩子”
        y.left = x;
        // 将 “x的父节点” 设为 “y”
        x.parent = y;
    }

    //右旋
    private void rightRotate(RBTNode<T> y) {
        // 设置x是当前节点的左孩子。
        RBTNode<T> x = y.left;

        // 将 “x的右孩子” 设为 “y的左孩子”；
        // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
        y.left = x.right;
        if (x.right != null)
            x.right.parent = y;

        // 将 “y的父亲” 设为 “x的父亲”
        x.parent = y.parent;

        if (y.parent == null) {
            this.mRoot = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点
        } else {
            if (y == y.parent.right)
                y.parent.right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
            else
                y.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
        }

        // 将 “y” 设为 “x的右孩子”
        x.right = y;

        // 将 “y的父节点” 设为 “x”
        y.parent = x;
    }

    public void insert(T key) {
        RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);

        // 如果新建结点失败，则返回。
        if (node != null)
            insert(node);
    }

    //将结点插入到红黑树中
    private void insert(RBTNode<T> node) {
        int cmp;
        RBTNode<T> y = null;
        RBTNode<T> x = this.mRoot;

        // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
        while (x != null) {
            y = x;
            cmp = node.key.compareTo(x.key);
            if (cmp < 0)
                x = x.left;
            else
                x = x.right;
        }

        node.parent = y;
        if (y != null) {
            cmp = node.key.compareTo(y.key);
            if (cmp < 0)
                y.left = node;
            else
                y.right = node;
        } else {
            this.mRoot = node;
        }
        // 2. 设置节点的颜色为红色
        node.color = RED;

        // 3. 将它重新修正为一颗二叉查找树
        insertFixUp(node);
    }

    /*
     * 红黑树插入修正函数
     *
     * 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
     * 目的是将它重新塑造成一颗红黑树。
     */
    private void insertFixUp(RBTNode<T> node) {
        RBTNode<T> parent, gparent;

        // 若“父节点存在，并且父节点的颜色是红色”
        while (((parent = parentOf(node))!=null) && isRed(parent)) {
            gparent = parentOf(parent);

            //若“父节点”是“祖父节点的左孩子”
            if (parent == gparent.left) {
                // Case 1条件：叔叔节点是红色
                RBTNode<T> uncle = gparent.right;
                if ((uncle!=null) && isRed(uncle)) {
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(gparent);
                    node = gparent;
                    continue;
                }

                // Case 2条件：叔叔是黑色，且当前节点是右孩子
                if (parent.right == node) {
                    RBTNode<T> tmp;
                    leftRotate(parent);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }

                // Case 3条件：叔叔是黑色，且当前节点是左孩子。
                setBlack(parent);
                setRed(gparent);
                rightRotate(gparent);
            } else {    //若“z的父节点”是“z的祖父节点的右孩子”
                // Case 1条件：叔叔节点是红色
                RBTNode<T> uncle = gparent.left;
                if ((uncle!=null) && isRed(uncle)) {
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(gparent);
                    node = gparent;
                    continue;
                }

                // Case 2条件：叔叔是黑色，且当前节点是左孩子
                if (parent.left == node) {
                    RBTNode<T> tmp;
                    rightRotate(parent);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }

                // Case 3条件：叔叔是黑色，且当前节点是右孩子。
                setBlack(parent);
                setRed(gparent);
                leftRotate(gparent);
            }
        }

        // 将根节点设为黑色
        setBlack(this.mRoot);
    }

    private void setRed(RBTNode<T> node) {
        node.color = RED;
    }

    private void setBlack(RBTNode<T> node) {
        node.color = BLACK;
    }

    private boolean isRed(RBTNode<T> node) {
        return node.color == RED;
    }

    private RBTNode<T> parentOf(RBTNode<T> node) {
        return node.parent;
    }
}

    这其中的左旋、右旋和AVL树是非常类似的，不同点在于需要额外处理节点的parent成员。
    红黑树有几种扩展：BB树、AA树、treep树，分别介绍如下：

BB树全称是二叉B树(binary B-tree)，它是一个带附加条件的红黑树：一个节点最多可以有一个红儿子。

AA树：用level代替color的一种红黑树，如果节点是树叶，level = 1；如果该节点是红色的，level等于它的父节点的level；如果该节点是黑色的，level等于父节点的level减1。

    结构如下：

    class AANode<T> {
        T element;
        AANode<T> left;
        AANode<T> right;
        int level;
        
        AANode(T element,AANode<T> left,AANode<T> right){
            this.element = element;
            this.left = left;
            this.right = right;
            level = 1;
        }
    }

treep树：用优先级代替color的一种红黑树，优先级满足小根堆的性质。

    结构如下：

    class TreepNode<T>{
        T element;
        TreepNode<T> left;
        TreepNode<T> right;
        int priority;
        
        TreepNode(T element,TreepNode<T> left,TreepNode<T> right){
            this.element = element;
            this.left = left;
            this.right = right;
            priority = random.nextInt();
        }
        
        static Random random = new Random();
    }

     Over !