记录手撸红黑树
今天得知学校提前返校，想到我整整一个暑假都在玩手机，有点内疚 ……一拍大腿，不行！
于是试着手撸红黑树
上网看了很多资料、博客，但还是一脸懵逼，幸好也做出来了一点。
学习数据结构的网站！！吹爆！！👇
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- 删除
- 代码优化
- 加入泛型
- 理解和2-3-4树的关系
- [ ?] 插入
- [ ?] 实现平衡
- [? ] BFS
手撸插入流程图
节点旋转
引用别人的动图
右旋
左旋
代码
红黑树代码
import java.util.LinkedList;
import java.util.Queue;
public class BlackRedTree {
static class Node{
int data;
Node father=null;
Node left=null;
Node right=null;
Node next=null;
boolean black=true;//每个节点默认为黑色 true为黑色；false为红色
Node(){}
Node(int data){
this.data=data;
}
}
//创建树头：
private Node TreeHeadNode= new Node();
//普通插入
private void insert(Node NewNode){
NewNode.black=false;
if(this.TreeHeadNode.next==null){
this.TreeHeadNode.next=NewNode;
NewNode.father=TreeHeadNode;
return;
}
Node pMove=this.TreeHeadNode.next;
while(pMove!=null){
if(NewNode.data<pMove.data){
if(pMove.left==null){
pMove.left=NewNode;
NewNode.father=pMove;
return;
}
pMove=pMove.left;
}
else{
if(pMove.right==null){
pMove.right=NewNode;
NewNode.father=pMove;
return;
}
pMove=pMove.right;
}
}
}
public void put(int data) {
Node NewNode=new Node(data);
insert(NewNode);
while(true){
if(this.TreeHeadNode.next==NewNode)
{
NewNode.black=true;
return;
}
else{//有父节点
Node Father=NewNode.father;
if(Father.black)//等于黑色
return;
else{//等于红色
Node GrandFather=Father.father;
Node Uncle=GetUncle(GrandFather,Father);
if(Uncle==null||Uncle.black)//叔节点为黑色或没有叔叔
{
//判断爷爷、我、父亲为什么形状
if(Shape(GrandFather,Father,NewNode)) // 直线
{
// 爷爷为旋转点去旋转
if (RotationDirection(Father,NewNode))
RightRotation(GrandFather);
else {
LeftRotation(GrandFather);
}
// 爷爷和父亲需要变色
GrandFather.black=!GrandFather.black;
Father.black=!Father.black;
// 维护树头颜色
UpdateTreeHeadColor();
return;
}
else//三角形
{
// 父亲为旋转点去旋转
if (RotationDirection(GrandFather,Father))//朝向左：先左旋（Father），再右旋（grandFather）
{
LeftRotation(Father);
RightRotation(GrandFather);
}
else//朝向右：先右旋（Father），再左旋（grandFather）
{
RightRotation(Father);
LeftRotation(GrandFather);
}
GrandFather.black=!GrandFather.black;
Father.black=!Father.black;
// 维护树头颜色
UpdateTreeHeadColor();
}
}
else {
Father.black=true;
Uncle.black=true;
GrandFather.black=false;
NewNode=GrandFather;
}
}
}
}
}
//维护树头颜色
private void UpdateTreeHeadColor(){
this.TreeHeadNode.next.black=true;
}
//确定旋转的方向，左true 右false
private boolean RotationDirection(Node Father,Node me){
return Father.left==me?true:false;
}
//左旋
private void LeftRotation(Node axis) {
Node Son=axis.right;
if(Son.left!=null) {
Node GrandSon=Son.left;
axis.right=GrandSon;
GrandSon.father=axis;
}
else
axis.right=null;
ConnectAxisFatherPoint(axis,Son);
Son.father=axis.father;
Son.left=axis;
axis.father=Son;
}
//右旋
private void RightRotation(Node axis){
Node Son=axis.left;
if(Son.right!=null){
Node GrandSon=Son.right;
axis.left=GrandSon;
GrandSon.father=axis;
}
else
axis.left=null;
ConnectAxisFatherPoint(axis,Son);
Son.father=axis.father;
Son.right=axis;
axis.father=Son;
}
//让旋转轴的父节点连接
private void ConnectAxisFatherPoint(Node axis,Node Son){
Node Father=axis.father;
if(Father==TreeHeadNode)
TreeHeadNode.next=Son;
else if(Father.left==axis)
Father.left=Son;
else
Father.right=Son;
}
//直线：true 三角形：false
private boolean Shape(Node GrandFather,Node Father,Node me){
// 左为true 右false
boolean line1=GrandFather.left==Father;
boolean line2=Father.left==me;
return line1==line2;
}
private Node GetUncle(Node GrandFather,Node Father){
return GrandFather.left==Father?GrandFather.right:GrandFather.left;
}
private void BFS(){
Queue<Node> queue=new LinkedList<>();
queue.add(this.TreeHeadNode.next);
while(!queue.isEmpty()){
Node TempNode=queue.poll();
System.out.println(TempNode.data);
if(TempNode.left!=null)
queue.add(TempNode.left);
if(TempNode.right!=null)
queue.add(TempNode.right);
}
}
}
测试main方法
public static void main(String[] args) {
BlackRedTree tree=new BlackRedTree();
// int [] a={3,2,7,5,6};
// for (int i:a) {
// tree.put(i);
// }
for (int i = 1; i <=8; i++) {
tree.put(i);
}
tree.BFS();
}
测试点：1，2，3，4，5，6，7，8
这是红黑树一系列旋转的示意图
对应的BFS为：4，2，6，1，3，5，7，8
测试点：3，2，7，5，6
这是红黑树一系列旋转的示意图
对应的BFS为：3，2，6，5，7