实现一颗红黑树
程序员文章站
2022-03-26 11:25:02
...
实现一个红黑树，记录一下，以后忘了也能有篇文章可以复习复习
使用的Java语言实现
红黑树介绍
- 红黑树的介绍
红黑树是一颗特殊的二叉查找树。它包含二叉查找树的所有特性。
二叉树查找树的特性：
1、每一个节点只有2个分支
2、左子树的结点值要小于或等于它的根结点的值。
3、右子树的结点值要大于或等于它的根结点的值。
红黑树的特性
1、加入了颜色（红色、黑色。非红即黑），用其他颜色也行，只要你记住颜色的作用区分就行
2、根节点是黑色、插入的新节点是红色
3、当前节点不能与父节点同为红色（如果一个节点为红色，它的2个子节点必须是黑色）
4、每个叶节点（NIL）是黑的。（所有NULL结点称为叶子节点）
-
时间复杂度
二叉查找树最好的情况是O(Log2n)，退化成链表后时间复杂度为O(n)
红黑树的时间复杂度每次都是O(Log2n) -
红黑树旋转
当红黑树不满足特性时，需要对树进行调整
左旋
左图以x点做左旋操作
1、将x的右节点设置成y的左节点， y的左节点(ly)的父节点设置为x
2、将y的父节点设置成x的父节点(px)， 如果px节点的左节点为x的话，那将px的左节点设置为y， 否则将px的右节点设置为y
3、将x的父节点设置为y， y的左节点设置为x
右旋
左图 以y点做一个右旋操作
1、将y的左节点设置为x的右节点，x的右节点(rx)的父节点设置为y
2、将x的父节点设置为y的父节点(py)，如果y的父节点(py)的左节点为y的话，那就将py的左节点设置为x，否则将py的右节点设置x
3、将y的父节点设置为x，x的右节点设置为y
要跟深入的一些理论知识，可以多查查，网上很多，我这里就不写太多了，我自身的理论知识还有待提高，要是写错了就尴尬了，就不误人子弟了…直接上代码吧
代码实现
主要类代码
package com.rbt.redBlackTree.RBTree;
/**
* 红黑树
*
* @author FJC
* @date 2020年6月6日09:38:18
* @version 1.0
*
*/
public class RedBlackTree<K extends Comparable<K>,V> {
private static final String RED="red";
private static final String BLACK="black";
private Node rootNode;//根节点
private int nodeSize = 0;
/**
* 查找
* @return
*/
public String get(K key){
Node node = new Node();
node.setKey(key);
return get(node).toString();
}
private Object get(Node node){
Node TreeNode = rootNode;
while(TreeNode!=null){
int cmp = node.key.compareTo(TreeNode.key);
if(cmp==0){
return TreeNode.getValue();
}else if(cmp>0){
TreeNode = TreeNode.rightNode;
}else{
TreeNode = TreeNode.leftNode;
}
}
throw new RuntimeException("RedBlackTree中没有找到"+node.getKey()+"的值!");
}
/**
* 树大小
*
* @return
*/
public int size(){
return nodeSize;
}
/**
* 插入
*
* @param key
* @param value
*/
public void put(K key,V value){
Node node = new Node();
node.setKey(key);
node.setValue(value);
node.setColor(RED);
put(node);
}
private void put(Node node){
// 用来记录 nextNode 为null前的最后一个节点
Node parentNode = null;
/*
* 作为一个判断是否有下一个的条件
* 如果 nextNode 为 null
* 说明 需要将插入的node放到 nextNode 为null前的最后一个节点下
*/
Node nextNode = rootNode;
/*
* 查找当前节点的父节点
*/
while(nextNode!=null){
parentNode = nextNode;
/*
* 根据自然顺序进行排序
* 如果node.key大于当前节点上的key，那就向右边插入数据
* 如果等于 那就说明key重复了，替换当前key里面的value值
* 如果小于那就向左边插入
*/
int cmp = node.key.compareTo(nextNode.key);
if(cmp>0){
nextNode = nextNode.rightNode;
}else if(cmp==0){
nextNode.value = node.value;
return;
}else{
nextNode = nextNode.leftNode;
}
}
// 设置插入节点的父节点
node.parentNode = parentNode;
/*
* 如果当前树不是一颗空树
*
* parentNode应该是不会为空的
* 在将 node.key 与插入的 parentNode.key 做比较
* 如果大于说明需要插入parentNode节点的右边
* 否则就是插入节点的左边
* 这个时候不可能有等于，因为如果等于的话 上面if块中已经做了替换操作并退出了
*
* 如果parentNode为空说明是一颗空树
* 是第一次插入数据
* 只要将当前插入的node设置为根节点即可
*
*/
if(parentNode != null){
int cmp = node.key.compareTo(parentNode.key);
if(cmp>0){
parentNode.rightNode = node;
}else if(cmp<0){
parentNode.leftNode = node;
}
}else{
rootNode = node;
}
insertFixUp(node);
nodeSize++;
}
/**
* 修复红黑树
*
*/
private void insertFixUp(Node node){
Node parentNode = parentOf(node);
Node gparentNode = parentOf(parentNode);
/*
* 当插入的父节点为红色才做修复处理
* 为黑色是满足红黑树的特性 不做处理
*
*/
if(parentNode!=null && isRed(parentNode)){
Node uncle = null;
// 如果父节点为爷爷节点的左节点
if(gparentNode.leftNode == parentNode){
uncle = gparentNode.rightNode;
/*
* 如果叔叔节点同为红色时
* 要将 父节点 和 叔叔节点 染黑，爷爷节点染红，
* 在将爷爷节点作为当前节点 进行递归向上处理
*
*/
if(uncle!=null && isRed(uncle)){
setBlack(parentNode);
setBlack(uncle);
setRed(gparentNode);
insertFixUp(gparentNode);
return;
}
// 将 叔叔节点为黑色时
if(uncle==null || !isRed(uncle)){
/*
* 如果当前插入的节点在 父节点的左边
* 那只需要 将父节点染黑，爷爷节点染红，在做一次右旋操作
*/
if(node == parentNode.leftNode){
setBlack(parentNode);
setRed(gparentNode);
rightRotat(gparentNode);
return;
}
/*
* 需要首先做一步 左旋操作
* 然后递归进入上面if块 进行处理
*/
if(node == parentNode.rightNode){
leftRotat(parentNode);
insertFixUp(parentNode);
return;
}
}
}else{ // 父节点为爷爷节点的右节点 处理方式与上面相反
uncle = gparentNode.leftNode;
/*
* 如果叔叔节点同为红色时
* 要将 父节点 和 叔叔节点 染黑，爷爷节点染红，
* 在将爷爷节点作为当前节点 进行递归向上处理
*
* 这个方法不变，是同样的操作
*/
if(uncle!=null && isRed(uncle)){
setBlack(parentNode);
setBlack(uncle);
setRed(gparentNode);
insertFixUp(gparentNode);
return;
}
// 将 叔叔节点为黑色时
if(uncle==null || !isRed(uncle)){
/*
* 这个时候是判断条件是
* 当前插入的节点在 父节点的右边
* 那只需要 将父节点染黑，爷爷节点染红，在做一次左旋操作
*
*/
if(node == parentNode.rightNode){
setBlack(parentNode);
setRed(gparentNode);
leftRotat(gparentNode);
return;
}
/*
* 这个是先右旋
* 然后递归进入上面if块 进行处理
*/
if(node == parentNode.leftNode){
rightRotat(parentNode);
insertFixUp(parentNode);
return;
}
}
}
}
// 最后将 根节点设置为黑色
setBlack(rootNode);
}
/**
* 右旋
*
* py py
* / /
* y x
* / \ --(右旋)-. / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*
* 写旋转的时候 有一个这个图 写的思路会比较清晰写
* 左图 以y点做一个右旋操作
* 1、将y的左节点设置为x的右节点
* x的右节点(rx)的父节点设置为y
* 2、将x的父节点设置为y的父节点(py)
* 如果y的父节点(py)的左节点为y的话
* 那就将py的左节点设置为x
* 否则将py的右节点设置x
* (如果y的父节点为null 说明是第一次插入，将x节点设置为根节点就好了)
* 3、将y的父节点设置为x
* x的右节点设置为y
*
* 注：第3步一定要写在第2步后面，要不然....嘿嘿你们可以尝试一下（曾经踩过的坑）
*/
private void rightRotat(Node y){
Node x = y.leftNode;
y.leftNode = x.rightNode;
if(x.rightNode!=null){
x.rightNode.parentNode = y;
}
if(y.parentNode!=null){
Node gparentNode = parentOf(y);
x.parentNode = gparentNode;
if(gparentNode.leftNode == y){
gparentNode.leftNode = x;
}else{
gparentNode.rightNode = x;
}
}else{
rootNode = x;
rootNode.parentNode=null;
}
y.parentNode = x;
x.rightNode = y;
}
/**
* 左旋
*
* px px
* / /
* x y
* / \ --(左旋)-. / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
* 左图以x点做左旋操作
* 1、将x的右节点设置成y的左节点
* y的左节点(ly)的父节点设置为x
* 2、将y的父节点设置成x的父节点(px)
* 如果px节点的左节点为x的话
* 那将px的左节点设置为y
* 否则将px的右节点设置为y
* (如果x的父节点为null 说明是第一次插入，将y节点设置为根节点就好了)
* 3、将x的父节点设置为y
* y的左节点设置为x
*/
private void leftRotat(Node x){
Node y = x.rightNode;
x.rightNode = y.leftNode;
if(y.leftNode!=null){
y.leftNode.parentNode = x;
}
if(x.parentNode!=null){
Node gparentNode = parentOf(x);
y.parentNode=gparentNode;
if(gparentNode.leftNode == x){
gparentNode.leftNode=y;
}else{
gparentNode.rightNode=y;
}
}else{
rootNode = y;
rootNode.parentNode = null;
}
x.parentNode=y;
y.leftNode=x;
}
/**
* 前序打印
*/
public void pointTreeValbefor(){
pointTreeValbefor(rootNode);
}
/**
* 中序打印红黑树
*
*/
public void pointTreeVal(){
pointTreeVal(rootNode);
}
private void pointTreeValbefor(Node node){
if(node!=null){
System.out.print(node.getKey()+"("+node.getColor()+"),");
//System.out.println("key="+node.getKey()+";value="+node.getValue());
pointTreeValbefor(node.getLeftNode());
pointTreeValbefor(node.getRightNode());
}
}
private void pointTreeVal(Node node){
if(node!=null){
pointTreeVal(node.getLeftNode());
System.out.print(node.getKey()+"("+node.getColor()+"),");
//System.out.println("key="+node.getKey()+";value="+node.getValue());
pointTreeVal(node.getRightNode());
}
}
/**
* 设置当前节点为红色
*
* @param node
*/
private void setRed(Node node){
if(node!=null){
node.color = RED;
}
}
/**
* 设置当前节点为黑色
*
* @param node
*/
private void setBlack(Node node){
if(node!=null){
node.color = BLACK;
}
}
/**
* 获取当前节点的父节点
*
* @param node
* @return
*/
private Node parentOf(Node node){
if(node!=null){
return node.parentNode;
}
return null;
}
/**
* 判断当前节点是否为红色
*
* @param node
* @return
*/
private boolean isRed(Node node){
if(node!=null){
if(node.getColor().equals(RED)){
return true;
}
}
return false;
}
class Node<K extends Comparable<K>,V>{
public Node leftNode;
public Node rightNode;
public Node parentNode;
public K key;
public V value;
public String color;
public Node(Node leftNode, Node rightNode, Node parentNode, K key, V value, String color) {
super();
this.leftNode = leftNode;
this.rightNode = rightNode;
this.parentNode = parentNode;
this.key = key;
this.value = value;
this.color = color;
}
public Node() {
super();
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public Node getParentNode() {
return parentNode;
}
public void setParentNode(Node parentNode) {
this.parentNode = parentNode;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public String getColor() {
return color;
}
public void setColor(String color) {
this.color = color;
}
}
}
测试main方法
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
RedBlackTree<String, Object> rbtree = new RedBlackTree<String, Object>();
/*while (true) {
System.out.println("请输入值：");
String key = scanner.next();
System.out.println();
rbtree.put(key, null);
System.out.println("前序打印：");
rbtree.pointTreeValbefor();
System.out.println();
System.out.println("中序打印：");
rbtree.pointTreeVal();
System.out.println();
}*/
rbtree.put("account", "admin");
rbtree.put("name", "张三");
rbtree.put("age","18");
rbtree.put("pwd", "111111");
String account = rbtree.get("account");
String pwd = rbtree.get("pwd");
int size = rbtree.size();
System.out.println("树大小："+size);
System.out.println("账号："+account);
System.out.println("密码："+pwd);
// 这个应该要抛出异常
String school = rbtree.get("school");
System.out.println("学校："+school);
}
学会了红黑树之后，我觉得我的技术应该和发际线同时上涨了
奥利给！
上一篇： OpenCV-Python 图像处理（三）：图像的基本操作
下一篇： 【结论？】这是一颗树吗？