树的概念
在客观世界中许多事物存层次关系,例如:
使用树这种结构的原因是因为层次管理具有更高的效率
树: N个节点构成的有限集合,含有一个称为根(Root)的特殊结点如上图的中国,其余的结点可分为若干个互不相交的树,称为原来结点的子树
基本术语
- 结点的度: 结点子树个数
- 树的度: 树中所有的节点中最大的度
- 叶结点: 度为0的结点
- 父结点: 有子树的结点是其子树的根节点的父结点
- 子结点: 若A是B的父结点,B就是A的子结点
- 结点的层次:根节点为1层子结点的层数是父结点层数+1
- 树的高度: 树中所有结点的最大层次就是这棵树的高度
注: 子树是不相交的除根结点外,每个结点有且只有一个父结点,一个N结点的树只有N-1条边
二叉树
树的度为2的树,且子树有左右之分
二叉树的应用
编码问题:
给定一段文本对字符串编码使其编码存储空间最少
设一段文本包含58个字符,由一下7个字符构成:
等长ASCII编码: 58 * 8 = 464位
等长3位编码: 58 * 3 = 174位
不等长编码: 10* 3+15 * 2+12 * 2+3 * 5+4 * 4+13 * 2+1*5 = 146位
不等长编码：出现频次高的字符用的编码短些，出现频次低的编码长些
使用二叉树进行编码:
二叉树分支 :0,1,为了避免二义性字符只在叶节点上
哈夫曼树的构造
构造一颗二叉树,该树的带权路径长度达到最小称为最优二叉树也就是哈夫曼树
构造方式:
- 每次把权重最小的两棵二叉树合并
- 左节点权值比右节点小
解决上述编码问题
具体代码实现
package 树;
import java.util.ArrayList;
import java.util.List;
/**
* @author peiqi
* @Title:
* @Package
* @Description: 哈夫曼树
* @date 2021/10/115:22
*/
public class HuffmanTree {
/**
* 节点
* @param <T>
*/
public static class Node<T>{
//数据,权重,左右子节点
private T data;
private int weight;
private Node leftChild;
private Node rightChild;
public Node(T data,int weight){
super();
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "Node["+weight+","+"data="+data+"]";
}
}
/**
* 构造哈夫曼树
* @param nodes 节点集合
* @return 构造出来的哈夫曼树根节点
*/
private static Node createTree(List<Node> nodes) {
//判断节点node列表中是否含有2哥及2个以上的节点
while (nodes.size() > 1) {
//将list排序按照权重增序方式进行排序,找到最小的
sort(nodes);
//左边比右边小
Node left = nodes.get(0);
Node right = nodes.get(1);
//生成一个新的节点,父结点权重为两个子结点之和,
Node parent = new Node(null, left.weight + right.weight);
//让子结点与父结点连接
parent.leftChild = left;
parent.rightChild = right;
//删除最小的
nodes.remove(0);
//删除第二小的
nodes.remove(0);
nodes.add(parent);
}
return nodes.get(0);
}
/**
* 冒泡排序，用于对节点进行排序（增序排序）
*
* @param nodes
*/
public static void sort(List<Node> nodes) {
if (nodes.size() <= 1){
return ;
}
/*循环数组长度的次数*/
for (int i = 0; i < nodes.size(); i++){
/*从第0个元素开始，依次和后面的元素进行比较
* j < array.length - 1 - i表示第[array.length - 1 - i]
* 个元素已经冒泡到了合适的位置，无需进行比较，可以减少比较次数*/
for (int j = 0; j < nodes.size() - 1 - i; j++){
/*如果第j个节点比后面的第j+1节点权重大，交换两者的位置*/
if (nodes.get(j + 1).weight < nodes.get(j).weight) {
Node temp = nodes.get(j + 1);
nodes.set(j+1,nodes.get(j));
nodes.set(j,temp);
}
}
}
return ;
}
/*
* 递归打印哈夫曼树(先左子树，后右子树打印)
*/
public static void printTree(Node root) {
System.out.println(root.toString());
if(root.leftChild !=null){
System.out.print("left:");
printTree(root.leftChild);
}
if(root.rightChild !=null){
System.out.print("right:");
printTree(root.rightChild);
}
}
/**
* 测试
*/
public static void main(String[] args) {
List<Node> nodes = new ArrayList<Node>();
//把节点加入至list中
nodes.add(new Node("a", 10));
nodes.add(new Node("b", 15));
nodes.add(new Node("c", 12));
nodes.add(new Node("d", 3));
nodes.add(new Node("e", 4));
nodes.add(new Node("f", 13));
nodes.add(new Node("g", 1));
//进行哈夫曼树的构造
Node root = HuffmanTree.createTree(nodes);
//打印哈夫曼树
printTree(root);
}
}
二叉排序树
定义
- 左子树的所有的值小于根节点的值
- 右子树的所有的值大于根节点的值
- 左右子树满足以上两点
Find
查找的值x从根节点开始
- 如果x小于根节点的值,则在左子树中继续查找
- 如果x大于根节点的值,则在右子树中继续查找
- 如果x等于根节点的值则返回该节点
- 查不到就返回null
查找的效率决定于树的高度,最大元素在树的最右支的节点,最小元素在树的最左支的节点上
Insert
插入的值从根节点开始查找
- 如果x小于根节点的值,则在左子树中继续查找
- 如果x大于根节点的值,则在右子树中继续查找
- 如果该节点是叶节点,x小于该节点值则插入左子节点,否则插入右节点
delete
插入的值从根节点开始查找
- 如果该节点的值为x则删除
- 如果x小于根节点的值,则在左子树中继续查找
- 如果x大于根节点的值,则在右子树中继续查找
AVL树
他是一颗二叉排列树,左右2个子树的高度差(平衡因子)的绝对值
不超过1,且左右2个子树都是一颗平衡二叉树
目的: 使得树的高度最低,因为树查找的效率决定于树的高度
二叉平衡树的调整
调整原则根据插入的节点和失衡节点的位置上关系来划分
-
LL旋转
插入节点在失衡结点的左子树的左边,需要经过一次左旋转即可达到平衡 -
RR旋转
插入节点在失衡结点的右子树的右边,需要经过一次右旋转即可达到平衡 -
LR旋转
插入的节点在失衡节点的左子树的右边,失衡节点的左子树先做RR旋转,失衡节点再做LL旋转 -
RL旋转
插入的节点在失衡节点的右子树的左边,失衡节点的右子树先做LL旋转,失衡节点再做RR旋转
代码实现
package 树;
/**
* @author peiqi
* @Title:
* @Package
* @Description: AVLTree
* @date 2021/10/29:57
*/
public class AVLTree {
//节点
public static class Node {
//数据,左子节点,右子节点,记录该节点所在的高度
int data;
Node leftChild;
Node rightChild;
int height;
public Node(int data) {
this.data = data;
}
}
/**
* 获取节点的高度
* @param p
* @return 节点的高度
*/
public static int getHeight(Node p){
//空树高度为-1
return p==null?-1:p.height;
}
/**
* 打印树
* @param root
*/
public static void printTree(Node root) {
System.out.println(root.data);
if(root.leftChild !=null){
System.out.print("left:");
printTree(root.leftChild);
}
if(root.rightChild !=null){
System.out.print("right:");
printTree(root.rightChild);
}
}
/**
* AVL树的插入方法
* @param root
* @param data
* @return
*/
public static Node insert(Node root,int data){
if(root==null){
root = new Node(data);
return root;
}
if (data<= root.data){
//插入到其左子树上
root.leftChild = insert(root.leftChild,data);
//平衡调整---高度差大于1
if(getHeight(root.leftChild)-getHeight(root.rightChild)>1){
//插入的节点在失衡节点的左子树的左边
if (data<=root.leftChild.data){
System.out.println("LL旋转");
//LL旋转调整
root = LLRotate(root);
//插入的节点在失衡节点的左子树的右边
}else{
System.out.println("LR旋转");
//LR旋转调整
root = LRRotate(root);
}
}
//插入到右子树上
}else{
root.rightChild = insert(root.rightChild,data);
//平衡调整
if(getHeight(root.leftChild)-getHeight(root.rightChild)>1) {
//插入节点在失衡结点的右子树的左边
if (data <= root.rightChild.data) {
System.out.println("RL旋转");
root = RLRotate(root);
//插入节点在失衡结点的右子树的右边
} else {
System.out.println("RR旋转");
root = RRRotate(root);
}
}
}
//重新调整root节点的高度值
root.height = Math.max(getHeight(root.leftChild),getHeight(root.rightChild))+1;
return root;
}
/**
* LL旋转
* 左旋示意图(对结点20进行左旋)
* 30 20
* / \ / \
* 20 40 10 30
* / \ --LL旋转- / / \
* 10 25 5 25 40
* /
* 5
* 30为失衡点
* @param p
* @return LsubTree
*/
public static Node LLRotate(Node p){
//失衡点的左子树的根节点作为新节点
Node LsubTree = p.leftChild;
//将新节点的右子树25作为失衡点30的左子树
p.leftChild = LsubTree.rightChild;
//将失衡点30作为新节点的右子树
LsubTree.rightChild = p;
//重新设置失衡点和新节点的高度
p.height = Math.max(getHeight(p.rightChild),getHeight(p.leftChild))+1;
LsubTree.height = Math.max(getHeight(LsubTree.leftChild),p.height)+1;
//新的节点取代原失衡点
return LsubTree;
}
/**
* RR旋转
* 右旋示意图(对结点30进行左旋)
* 20 30
* / \ / \
* 10 30 20 40
* / \ --RR旋转- / \ \
* 25 40 10 25 50
* \
* 50
*
* 20作为失衡点
* @param p
* @return RsubTree
*/
public static Node RRRotate(Node p){
//失衡点的右子树的根节点作为新节点
Node RsubTree = p.rightChild;
//将新节点的左子树25作为失衡点20的右子树
p.rightChild = RsubTree.leftChild;
//将失衡点20作为新节点的左子树
RsubTree.leftChild = p;
//重新设置失衡点和新节点的高度
p.height = Math.max(getHeight(p.rightChild),getHeight(p.leftChild))+1;
RsubTree.height = Math.max(getHeight(RsubTree.rightChild),getHeight(RsubTree.leftChild))+1;
//新的节点取代原失衡点
return RsubTree;
}
/**
* RL旋转
* @param p
* @return
*/
public static Node RLRotate(Node p){
// 先将失衡点p的右子树进行LL平衡旋转
p.rightChild = LLRotate(p.rightChild);
//再将失衡点p进行RR平衡点旋转返回新节点代替原失衡点p
return RRRotate(p);
}
/**
* LR旋转
* @param p
* @return
*/
public static Node LRRotate(Node p){
// 先将失衡点p的左子树进行RR旋转
p.leftChild = RRRotate(p.leftChild);
// 再将失衡点p进行LL平衡旋转并返回新节点代替原失衡点p
return LLRotate(p);
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
Node root = null;
root = insert(root,30);
root = insert(root,20);
root = insert(root,40);
root = insert(root,10);
root = insert(root,25);
//插入节点在失衡结点的左子树的左边
root = insert(root,5);
//打印树，按照先打印左子树，再打印右子树的方式
printTree(root);
}
}
测试结果:
红黑树
一种特殊的二叉查找树,拥有以下特征
- 节点非红即黑
- 根节点和Null节点是黑色的
- 所有Null节点称为叶节点,且颜色为黑色
- 所有红色节点的子结点都是黑色
- 从任意节点到其叶节点的所有路径都包含相同数目的黑色节点
- 从根节点到叶节点的最长路径不多于最短的可能路径的2倍
插入
插入原则:因为插入节点的颜色为黑色的话那么久破坏了红黑树的性质,所以每次插入的点首先都是红节点
情况一:插入的新节点N位于树的根上,插入的新节点的父结点是黑色的
变色
叔父节点来指新节点的父节点的兄弟节点、祖父节点新节点的父节点的父节点
情况二: 如果新节点的父结点和叔父节点都是红色节点,先插入新节点(红色),新节点的父结点,叔父节点和祖父节点都要变色的
情况三:如果新节点父结点是红色同时叔父节点是黑色,同时新节点是其父结点的左子节点,而父结点是祖父节点的左子节点,这时要进行一次右旋转调整新节点和其父节点的角色(以父结点为轴)
这里因为根节点是红色所以进行了一次变色,为了满足红黑树的性质所以叔父节点也进行一次变色
情况四: 如果新节点的父结点是红色同时叔父节点都是黑色,新节点是其父节点的右子节点而父结点是祖父节点的右子节点,此时需要对祖父节点进行一次左旋转(以父结点为轴)
这里变色与上述同理
情况五: 如果新节点的父节点是红色同时叔父节点都是黑色，同时新节点是其父节点的右子节点而父节点又是其父节点的左子节点。进行一次左旋转调换新节点和其父节点的角色（第一次旋转），同时发现节点符合情况3，再进行一次右旋转（第二次旋转）
情况六: 如果新节点的父结点是红色同时叔父节点是黑色,同时新节点是其父节点的左子节点而父节点是祖父节点的右子节点,这是要进行一次右旋转变成情况四,在进行一次左旋转
代码实现
package 树;
/**
* @author peiqi
* @Description: 红黑树
* @date 2021/10/217:25
*/
public class RBTree<T extends Comparable<T>> {
//根节点
private RBTNode<T> mRoot;
//设置红色为false
private static final boolean RED = false;
//设置黑色是true
private static final boolean BLACK = true;
public class RBTNode<T extends Comparable<T>>{
//颜色,键值,左孩子,右孩子,父结点
boolean color;
T key;
RBTNode<T> left;
RBTNode<T> right;
RBTNode<T> parent;
public RBTNode(boolean color, T key, RBTNode<T> left, RBTNode<T> right, RBTNode<T> parent) {
this.color = color;
this.key = key;
this.left = left;
this.right = right;
this.parent = parent;
}
public T getKey() {
return key;
}
@Override
public String toString() {
return ""+key+(this.color==RED?"(R)":"B");
}
}
public RBTree() {
mRoot=null;
}
private RBTNode<T> parentOf(RBTNode<T> node) {
return node!=null ? node.parent : null;
}
private boolean colorOf(RBTNode<T> node) {
return node!=null ? node.color : BLACK;
}
private boolean isRed(RBTNode<T> node) {
return ((node!=null)&&(node.color==RED)) ? true : false;
}
private boolean isBlack(RBTNode<T> node) {
return !isRed(node);
}
private void setBlack(RBTNode<T> node) {
if (node!=null) {
node.color = BLACK;
}
}
private void setRed(RBTNode<T> node) {
if (node!=null) {
node.color = RED;
}
}
private void setParent(RBTNode<T> node, RBTNode<T> parent) {
if (node!=null) {
node.parent = parent;
}
}
private void setColor(RBTNode<T> node, boolean color) {
if (node!=null) {
node.color = color;
}
}
/**
* (递归实现)查找"红黑树x"中键值为key的节点
* @param x 红黑树
* @param key
* @return
*/
private RBTNode<T> search(RBTNode<T> x,T key){
if (x==null){
return x;
}
int cmp = key.compareTo(x.key);
//小于则去左子树找,大于则去右子树找
if (cmp<0){
return search(x.left,key);
}else if (cmp>0){
return search(x.right,key);
}else{
return x;
}
}
/**
* 查找最小结点：返回tree为根结点的红黑树的最小结点。
* @param tree
* @return
*/
private RBTNode<T> minNum(RBTNode<T> tree){
if (tree== null){
return null;
}
//在左子树上找
while (tree.left!=null){
tree = tree.left;
}
return tree;
}
/**
* 得到最小结点的值
* @return
*/
public T miniNum(){
RBTNode<T> p = minNum(mRoot);
if (p!=null){
return p.key;
}
return null;
}
/**
* 查找最大结点：返回tree为根结点的红黑树的最大结点。
* @param tree
* @return
*/
private RBTNode<T> maxiNum(RBTNode<T> tree) {
if (tree == null) {
return null;
}
while(tree.right != null) {
tree = tree.right;
}
return tree;
}
public T maxiNum() {
RBTNode<T> p = maxiNum(mRoot);
if (p != null) {
return p.key;
}
return null;
}
/**
* 找节点的后继节点,即查找红黑树中数据值大于该节点的最小节点
* @param x
* @return
*/
public RBTNode<T> successor(RBTNode<T> x){
//如果存在右孩子,则x的后继节点为以其右孩子为根的子树的最小节点
if (x.right!=null){
return minNum(x.right);
}
//如果没有右孩子,则x有一下2种可能:
// (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
// (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
RBTNode<T> y = x.parent;
while ((y!=null) && (x==y.right)) {
x = y;
y = y.parent;
}
return y;
}
/*
* 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
*/
public RBTNode<T> predecessor(RBTNode<T> x) {
// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
if (x.left != null) {
return maxiNum(x.left);
}
// 如果x没有左孩子。则x有以下两种可能：
// (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
// (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
RBTNode<T> y = x.parent;
while ((y!=null) && (x==y.left)) {
x = y;
y = y.parent;
}
return y;
}
/**
*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋)：
* 13 17
* / \ / \
* nul 17 13 27
* / \ --(左旋)-. / \ / \
* nul 27 nul nul nul nul
* / \
* nul nul
* @param x(13)
*/
private void leftRotate(RBTNode<T> x){
//设置右孩子为y(17)
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;
// 如果 “x的父亲” 是空节点，则将y设为根节点
if (x.parent == null) {
this.mRoot = y;
} else {
// 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
if (x.parent.left == x) {
x.parent.left = y;
} else {
// 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
x.parent.right = y;
}
}
// 将 “x” 设为 “y的左孩子”
y.left = x;
// 将 “x的父节点” 设为 “y”
x.parent = y;
}
/**
* 对红黑树的节点(8)进行右旋转
*
* 右旋示意图(对节点8进行右旋)：
* 13 8
* / \ / \
* 8 nul 1 13
* / \ --(右旋)- / \ / \
* 1 nul nul nul nul nul
* / \
* nul nul
* @param 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) {
// 如果 “y的父亲” 是空节点，则将x设为根节点
this.mRoot = x;
} else {
if (y == y.parent.right) {
// 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
y.parent.right = x;
} else {
// (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
y.parent.left = x;
}
}
// 将 “y” 设为 “x的右孩子”
x.right = y;
// 将 “y的父节点” 设为 “x”
y.parent = x;
}
/**
* 红黑树插入修正函数
*
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 插入的结点
* @param 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){
RBTNode<T> uncle = gparent.right;
//情况二:叔叔节点是红色的
if (uncle!=null&&isRed(uncle)){
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
//情况五:叔叔是黑色的,当前节点是右孩子(两次旋转,先左后右)
if (parent.right == node){
RBTNode<T> temp;
//左旋转
leftRotate(parent);
temp = parent;
parent = node;
node = temp;
}
//情况三:叔叔是黑色的,当前节点是左孩子(一次右旋转)
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
}else {
//父结点是祖父节点的右孩子
RBTNode<T> uncle = gparent.left;
// 情况2：叔叔节点是红色
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
//情况六:叔叔是黑色的,当且节点是左孩子(先右后左)
if (parent.left==node){
RBTNode<T> temp;
rightRotate(parent);
temp = parent;
parent = node;
node = temp;
}
//情况四:叔叔是黑色的,当前节点是右孩子(一次左旋)
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
//将根节点设为黑色
setBlack(this.mRoot);
}
/**
* 将结点插入到红黑树中
* @param 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);
}
/**
* 新建结点(key)，并将其插入到红黑树中
* @param key
*/
public void insert(T key){
RBTNode<T> node = new RBTNode<T>(BLACK,key,null,null,null);
// 如果新建结点失败，则返回。
if (node != null) {
insert(node);
}
}
/**
* 红黑树删除修正函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 待修正的节点
*/
private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
RBTNode<T> other;
while ((node==null || isBlack(node)) && (node != this.mRoot)) {
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.right==null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mRoot;
break;
}
} else {
other = parent.left;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left==null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mRoot;
break;
}
}
}
if (node!=null) {
setBlack(node);
}
}
/*
* 删除结点(node)，并返回被删除的结点
*
* 参数说明：
* node 删除的结点
*/
private void remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被删除节点的"左右孩子都不为空"的情况。
if ( (node.left!=null) && (node.right!=null) ) {
// 被删节点的后继节点。(称为"取代节点")
// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
RBTNode<T> replace = node;
// 获取后继节点
replace = replace.right;
while (replace.left != null) {
replace = replace.left;
}
// "node节点"不是根节点(只有根节点不存在父节点)
if (parentOf(node)!=null) {
if (parentOf(node).left == node) {
parentOf(node).left = replace;
} else {
parentOf(node).right = replace;
}
} else {
// "node节点"是根节点，更新根节点。
this.mRoot = replace;
}
// child是"取代节点"的右孩子，也是需要"调整的节点"。
// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
child = replace.right;
parent = parentOf(replace);
// 保存"取代节点"的颜色
color = colorOf(replace);
// "被删除节点"是"它的后继节点的父节点"
if (parent == node) {
parent = replace;
} else {
// child不为空
if (child!=null) {
setParent(child, parent);
}
parent.left = child;
replace.right = node.right;
setParent(node.right, replace);
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
if (color == BLACK) {
removeFixUp(child, parent);
}
node = null;
return ;
}
if (node.left !=null) {
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
// 保存"取代节点"的颜色
color = node.color;
if (child!=null) {
child.parent = parent;
}
// "node节点"不是根节点
if (parent!=null) {
if (parent.left == node) {
parent.left = child;
} else {
parent.right = child;
}
} else {
this.mRoot = child;
}
if (color == BLACK) {
removeFixUp(child, parent);
}
node = null;
}
/*
* 删除结点(z)，并返回被删除的结点
*
* 参数说明：
* tree 红黑树的根结点
* z 删除的结点
*/
public void remove(T key) {
RBTNode<T> node;
if ((node = search(mRoot, key)) != null) {
remove(node);
}
}
/*
* 销毁红黑树
*/
private void destroy(RBTNode<T> tree) {
if (tree==null) {
return ;
}
if (tree.left != null) {
destroy(tree.left);
}
if (tree.right != null) {
destroy(tree.right);
}
tree = null;
}
public void clear() {
destroy(mRoot);
mRoot = null;
}
/*
* 打印"红黑树"
*
* key -- 节点的键值
* direction -- 0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。
*/
private void print(RBTNode<T> tree, T key, int direction) {
if(tree != null) {
if(direction==0){ // tree是根节点
System.out.printf("%2d(B) is root\n", tree.key);
} else{ // tree是分支节点
System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left");
}
print(tree.left, tree.key, -1);
print(tree.right,tree.key, 1);
}
}
public void print() {
if (mRoot != null) {
print(mRoot, mRoot.key, 0);
}
}
/*
* 前序遍历"红黑树"
*/
private void preOrder(RBTNode<T> tree) {
if(tree != null) {
System.out.print(tree.key+" ");
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
/*
* 中序遍历"红黑树"
*/
private void inOrder(RBTNode<T> tree) {
if(tree != null) {
inOrder(tree.left);
System.out.print(tree.key+" ");
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
/*
* 后序遍历"红黑树"
*/
private void postOrder(RBTNode<T> tree) {
if(tree != null)
{
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key+" ");
}
}
public void postOrder() {
postOrder(mRoot);
}
}