红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。
红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。
除了具备该特性之外，红黑树还包括许多额外的信息。
红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。
红黑树的特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
package com.binarytree; public class RedBlackTree<T extends Comparable<T>> { class Node { T t; Node parent; Node left; Node right; Color color; public Node(T t, Node parent,Node left,Node right, Color color) { super(); this.t = t; this.parent = parent; this.left = left; this.right = right; this.color = color; } public void setColor(Color color) { this.color=color; } } private enum Color{ Red, Black, } Node root; Node nil=new Node(null,null,null,null,Color.Black); /* * 获取祖父节点 */ public Node getGrandParent(Node node) { if(node.parent==null) { return null; } return node.parent.parent; } /* * 获取当前节点的叔节点 */ public Node getUncle(Node node) { Node grandParent=getGrandParent(node); if(grandParent==null) { return null; } if(node.parent==grandParent.left) { return grandParent.right; }else { return grandParent.left; } } /* x * * a y * * b z */ //左旋 public Node leftRotate(Node x) { Node y=x.right; Node b=y.left; x.right=b; y.left=x; x.parent=y; if(b!=null) { b.parent=x; } return y; } /* x * * y a * * z b */ //右旋 public Node rightRotate(Node x) { Node y=x.left; Node b=y.right; x.left=b; y.right=x; x.parent=y; if(b!=null) { b.parent=x; } return y; } public void addNode(T t) { if(t!=null) { addNode(root,t); } } public void addNode(Node current,T t) { Node node=current; Node parent = null; boolean isLeft=true; while(node!=null) { if(t.compareTo(node.t)<0) { isLeft=true; parent=node; node=node.left; }else if(t.compareTo(node.t)>0) { isLeft=false; parent=node; node=node.right; } } if(node==null&&parent==null) { root=new Node(t,null,null,null,Color.Black); }else if(node==null&&parent!=null) { Node newNode=new Node(t,null,null,null,Color.Red); newNode.parent=parent; if(isLeft) { parent.left=newNode; }else { parent.right=newNode; } setBalance(newNode); } } //使红黑树保持平衡 public void setBalance(Node node) { Node current=node; Node grandparent; Node uncle; while(current.parent!=null&¤t.parent.color==Color.Red) { grandparent=getGrandParent(current); uncle=getUncle(current); //父节点是祖父节点的左孩子L if(grandparent.left==current.parent) { //叔节点存在 且为红 if(uncle!=null&&uncle.color==Color.Red) { uncle.color=Color.Black; current.parent.color=Color.Black; grandparent.color=Color.Red; current=grandparent; }else {//叔节点不存在或者为黑 LL //只旋转一次 要变色 if(current.parent.left==current) { Node gpp=grandparent.parent;//祖父节点的父节点 grandparent.color=Color.Red; current.color=Color.Red; current.parent.color=Color.Black; if(gpp!=null&&gpp.left==grandparent) { gpp.left=rightRotate(grandparent); }else if(gpp!=null&&gpp.right==grandparent) { gpp.right=rightRotate(grandparent); }else { root= rightRotate(grandparent); } }else {//LR Node gpp=grandparent.parent;//祖父节点的父节点 grandparent.left=leftRotate(current.parent); //先变色在旋转 grandparent.left.color=Color.Black; current.color=Color.Red; grandparent.color=Color.Red; if(gpp!=null&&gpp.left==grandparent) { gpp.left=rightRotate(grandparent); }else if(gpp!=null&&gpp.right==grandparent) { gpp.right=rightRotate(grandparent); }else { root=rightRotate(grandparent); } } } }else {//R //叔节点存在 且为红 if(uncle!=null&&uncle.color==Color.Red) { uncle.color=Color.Black; current.parent.color=Color.Black; grandparent.color=Color.Red; current=grandparent; }else {//叔节点不存在或者为黑 if(current.parent.left==current) {//RL Node gpp=grandparent.parent;//祖父节点的父节点 grandparent.right=rightRotate(current.parent); //先变色在旋转 grandparent.right.color=Color.Black; current.color=Color.Red; grandparent.color=Color.Red; if(gpp!=null&&gpp.left==grandparent) { gpp.left=leftRotate(grandparent); }else if(gpp!=null&&gpp.right==grandparent) { gpp.right=leftRotate(grandparent); }else { root= leftRotate(grandparent); } }else {//RR Node gpp=grandparent.parent;//祖父节点的父节点 grandparent.color=Color.Red; current.color=Color.Red; current.parent.color=Color.Black; if(gpp!=null&&gpp.left==grandparent) { gpp.left=leftRotate(grandparent); }else if(gpp!=null&&gpp.right==grandparent) { gpp.right=leftRotate(grandparent); }else { root= leftRotate(grandparent); } } } } } root.color=Color.Black; } public void deleteNode(T t) { if(t!=null) { root= deleteNode(root,t); } } public Node deleteNode(Node current,T t) { if(current==null) { return null; } if(t.compareTo(current.t)<0) { current.left=deleteNode(current.left,t); }else if(t.compareTo(current.t)>0) { current.right=deleteNode(current.right,t); }else { } return current; } /* * 前序遍历 */ public void preTraversal(Node current) { if(current!=null) { System.out.println(current.t+" "+current.color); preTraversal(current.left); preTraversal(current.right); } } public static void main(String[] args) { RedBlackTree<Integer> rbt=new RedBlackTree<Integer>(); rbt.addNode(10); rbt.addNode(5); rbt.addNode(15); rbt.addNode(3); rbt.addNode(12); rbt.addNode(8); rbt.addNode(17); rbt.addNode(6); rbt.addNode(9); rbt.preTraversal(rbt.root); } }
原文：https://www.cnblogs.com/kjcc/p/13291777.html