09_算法基本概念(Java、Kotlin描述)
2023-01-03 本文已影响0人
刘加城
本篇文章介绍一些算法里用到的基本概念。
(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性质被破坏了，那么新节点的位置存在下列几种情况：
- A的左儿子的左子树；
- A的左儿子的右子树；
- A的右儿子的左子树；
- 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叉查找树的高度大约是log
N 。
-
摊还时间：当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)时间。红黑树的每个节点，要么是红色，要么是黑色。它有如下性质：
- 每一个节点或者是黑色，或者是红色；
- 根节点是黑色的；
- 每个叶子节点是黑色的(指为null的节点)；
- 如果一个节点是红色的，那么它的子节点必须是黑色的；
- 从一个节点到该节点的子孙节点所有路径包含相同数目的黑色节点。
红黑树的基本结构和插入操作如下：
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 !
