手写红黑树【数据结构】
手写红黑树【数据结构】
- 前言
- 版权
- 推荐
- 手写红黑树
- 一、理论知识
- 红黑树的特征
- 增加
- 删除
- 二、手写代码
- 初始-树结点
- 初始-红黑树
- 初始-遍历
- 初始-判断红黑树是否有效
- 查找
- 增加-1.父为黑,直接插入
- 增加-2. 父叔为红,颜色调换
- 增加-3. 父红叔黑,颜色调换,再移动
- 增加-4. 父子不同向,先掰直,再执行第3种情况
- 测试增加
- 删除-0 初始化数据
- 删除-1.单个红节点 直接删除
- 删除-3.带有一个子节点
- 删除-4.带有两个子节点
- 删除-2.单个黑结点
- 2.1.1兄黑,对侄红
- 2.1.2兄黑,顺侄红
- 2.1.3 兄黑,双侄黑
- 删除-2.单个黑结点 2.2兄红
- 测试删除
- 附录源码
- 最后
前言
2024-3-30 10:52:57
昨天晚上B站看到的视频
00:00~01:00
以下内容源自《【数据结构】》
仅供学习交流使用
版权
禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://jsss-1.blog.csdn.net
禁止其他平台发布时删除以上此话
推荐
我红黑树那么牛,你们凭什么不用我?
手写红黑树
一、理论知识
红黑树的特征
红黑树是一种二叉平衡树,只不过这个平衡不是那么严苛,只需黑平衡就行
- 结点分为两种颜色
- 根节点是黑色
- 叶子结点是黑色的,叶子结点是不存储数据的空结点
- 两个红结点不能相连,即红父亲的孩子都是黑色的
- 对于任意一个结点,其到叶子结点的路径上的黑色结点数量是一致的
增加
视频
插入结点的颜色是红色的
因为是黑平衡,所以插入红结点有概率不会破坏这个规则
- 父为黑,直接插入
- 父叔为红,颜色调换
- 父红叔黑,颜色调换,再移动
- 父子不同向,先掰直,再执行第3种情况
删除
视频
https://www.processon.com/view/link/6550422f54fca5688e143664
二、手写代码
为了实现简单,加入parent的指针,和isLeaf的标记
可以使用HashMap用来记录每一个叶子结点的父亲结点,即键是叶子,值是父亲;
也可以直接在Node结点中加入双亲指针。
根节点的父亲结点是null
特别注意的是,parent的维护
如果是叶子结点,它的isLeaf的值为true。
初始-树结点
//结点
class TreeNode {//true是黑色,false是红色boolean color;//数据Integer data;TreeNode left;TreeNode right;private static final boolean RED = false;private static final boolean BLACK = true;//是否是叶子结点boolean isLeaf;//方便实现TreeNode parent;public TreeNode() {}public TreeNode(int data) {this.data = data;}public TreeNode(boolean color, Integer data) {this.color = color;this.data = data;}public TreeNode(boolean color, Integer data, TreeNode parent) {this.color = color;this.data = data;this.parent = parent;}public TreeNode(boolean color, Integer data, TreeNode parent, boolean isLeaf) {this.color = color;this.data = data;this.parent = parent;this.isLeaf = isLeaf;}// public TreeNode(Integer data,TreeNode left, TreeNode right) {
// this.data = data;
// this.left = left;
// this.right = right;
// }public boolean isBlack() {return color == BLACK;}@Overridepublic String toString() {return "TreeNode{" +"color=" + color +", data=" + data +'}';}}
初始-红黑树
package test;import java.util.LinkedList;
import java.util.Queue;public class RedBlackTree {private static final boolean RED = false;private static final boolean BLACK = true;//根结点TreeNode root;public void initRoot(int data) {root = new TreeNode(BLACK, data, null, false);TreeNode nil = new TreeNode(BLACK, null, root, true);root.left = nil;root.right = nil;}/*** 增加* 1. 父为黑,直接插入* 2. 父叔为红,颜色调换* 3. 父红叔黑,颜色调换,再移动* 4. 父子不同向,先掰直,再执行第3种情况** @param data 数据*/public void add(int data) {}/*** 删除* 1.单个红节点 直接删除* 2.单个黑节点* 2.1兄黑* 2.1.1 对侄红 (指方向相反的侄节点)* 父兄交替旋转、然后按父红兄弟黑换色 (最后一步的换色,父红两兄弟黑,是按交替旋转之后的关系处理。)* 2.1.2 顺侄红(指方向相同的侄节点)* 兄侄交替旋转,并调换颜色,就会变成对侄红,然后按2.1.1处理* 2.1.3 双侄黑* 兄变红父变黑,如果父本身就是黑,就以父亲角度按情况2处理** 2.2 兄红* 父兄交替旋转,并调换颜色,新的兄节点将变黑,在按2.1处理* 3.带有一个子节点(当一个节点只有一个子节点时(空叶子除外),该节点必定是黑节点,其子节点必定是红色)* 用红子节点值替换,然后直接删除红子节点* 4.带有两个子节点!* 找到左子树中最靠右的子节点,用该节点值替换,并删除该节点按情况1,2,3处理(左子树中最大的值,也是离其最近的值)** @param data 数据*/public void delete(int data) {}public static void main(String[] args) {RedBlackTree tree = new RedBlackTree();tree.inorder(tree.root);
// tree.levelOrder(tree.root);}}
初始-遍历
//中序遍历public void inorder(TreeNode root) {if (root == null) {return;}if (!root.left.isLeaf) {inorder(root.left);}System.out.println(root);if (!root.right.isLeaf) {inorder(root.right);}}//层序遍历public void levelOrder(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode cur = queue.poll();System.out.print(cur + "\t");if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}System.out.println();}}
初始-判断红黑树是否有效
//判断是否是有效的红黑树public static boolean isValidRedBlackTree(TreeNode root) {if (root == null) {return true;}// 检查根节点是否是黑色if (root.color != BLACK) {return false;}// 计算黑高度,并检查红黑平衡blackHeight = -1;if (!checkBlackBalance(root, 0)) {return false;}// 递归检查每个节点return isValidRedBlackSubtree(root);}private static boolean checkBlackBalance(TreeNode node, int currentBlackHeight) {if (node.isLeaf) {if (blackHeight == -1) {blackHeight = currentBlackHeight;return true;} else {return currentBlackHeight == blackHeight;}}if (node.color == BLACK) {currentBlackHeight++;}return checkBlackBalance(node.left, currentBlackHeight) && checkBlackBalance(node.right, currentBlackHeight);}private static boolean isValidRedBlackSubtree(TreeNode node) {if (node == null) {return true;}// 检查红黑树性质if (node.color == RED) {if ((node.left != null && node.left.color != BLACK) || (node.right != null && node.right.color != BLACK)) {return false;}}// 递归检查左右子树return isValidRedBlackSubtree(node.left) && isValidRedBlackSubtree(node.right);}
查找
/*** 查找** @param data 数据* @return 查找结点,如果差不到就会返回叶子结点*/public TreeNode find(int data) {TreeNode find = root;while (!find.isLeaf) {if (data < find.data) {find = find.left;} else if(data==find.data){return find;} else if (data > find.data) {find = find.right;}}return find;}
增加-1.父为黑,直接插入
/*** 增加* 1. 父为黑,直接插入* 2. 父叔为红,颜色调换* 3. 父红叔黑,颜色调换,再移动* 4. 父子不同向,先掰直,再执行第3种情况** @param data 数据*/public void add(int data) {if (root == null) {initRoot(data);return;}TreeNode find = find(data);if (!find.isLeaf) {System.out.println("不能插入相同数据的结点");return;}TreeNode parent = find.parent;TreeNode newNode = new TreeNode(RED, data, parent);TreeNode nil = new TreeNode(BLACK, null, newNode, true);newNode.left = nil;newNode.right = nil;if (data < parent.data) {parent.left = newNode;} else {parent.right = newNode;}//1.父为黑,直接插入if (parent.isBlack()) {//不需要额外的操作} else {//跳转2...}
增加-2. 父叔为红,颜色调换
TreeNode grandpa = parent.parent;TreeNode uncle = grandpa.left != parent ? grandpa.left : grandpa.right;//2. 父叔为红,颜色调换if (!uncle.isBlack()) {parent.color = BLACK;uncle.color = BLACK;grandpa.color = RED;//如果爷爷是根节点if (grandpa == root) {grandpa.color = BLACK;return;}//爷爷变成红色后,它的父叔可能为红TreeNode cur=grandpa;parent=cur.parent;grandpa=parent.parent;if (parent==null||grandpa==null){return;}uncle=grandpa.left != parent ? grandpa.left : grandpa.right;while (!cur.isBlack()&&!parent.isBlack()&&!uncle.isBlack()){parent.color = BLACK;uncle.color = BLACK;grandpa.color = RED;//如果爷爷是根节点if (grandpa == root) {grandpa.color = BLACK;break;}cur=grandpa;parent=cur.parent;grandpa=parent.parent;uncle=grandpa.left != parent ? grandpa.left : grandpa.right;}} else {//跳转3...}
增加-3. 父红叔黑,颜色调换,再移动
//跳转3...boolean right1 = data > parent.data;boolean right2 = parent.data > grandpa.data;boolean direct1 = right1 && right2;boolean left1 = data < parent.data;boolean left2 = parent.data < grandpa.data;boolean direct2 = left1 && left2;//3. 父红叔黑,颜色调换,再移动if (direct1 || direct2) {op(data, parent, grandpa);} else {//跳转4...}public void op(int data, TreeNode parent, TreeNode grandpa) {boolean right1 = data > parent.data;boolean right2 = parent.data > grandpa.data;boolean direct1 = right1 && right2;boolean left1 = data < parent.data;boolean left2 = parent.data < grandpa.data;boolean direct2 = left1 && left2;boolean tmp = grandpa.color;grandpa.color = parent.color;parent.color = tmp;TreeNode grandpaPa = grandpa.parent;if (parent.data < grandpaPa.data) {grandpaPa.left = parent;} else {grandpaPa.right = parent;}parent.parent = grandpaPa;if (direct1) {parent.left = grandpa;grandpa.parent = parent;} else if (direct2) {parent.right = grandpa;grandpa.parent = parent;}grandpa.left = new TreeNode(BLACK, null, grandpa, true);grandpa.right = new TreeNode(BLACK, null, grandpa, true);}
增加-4. 父子不同向,先掰直,再执行第3种情况
//跳转4...//4. 父子不同向,先掰直,再执行第3种情况if (left1) {grandpa.right = newNode;newNode.right = parent;}if (right1) {grandpa.left = newNode;newNode.left = parent;}newNode.parent = grandpa;parent.parent = newNode;TreeNode newNil = new TreeNode(BLACK, null, parent, true);parent.left = newNil;parent.right = newNil;op(parent.data, newNode, grandpa);
测试增加
public static void main(String[] args) {RedBlackTree tree = new RedBlackTree();testAdd(tree);}private static void testAdd(RedBlackTree tree) {tree.add(157);//0tree.add(12);//1tree.add(200);//1tree.add(250);//2tree.add(260);//3tree.add(220);//2tree.add(210);//4tree.add(11);//1tree.add(10);//3tree.add(7);//2tree.add(9);//4tree.inorder(tree.root);
// tree.levelOrder(tree.root);System.out.println(isValidRedBlackTree(tree.root));}
11、10、7、9的插入图如下
2024-3-30 15:35:56
删除-0 初始化数据
public static void main(String[] args) {RedBlackTree tree = new RedBlackTree();
// testAdd(tree);initData(tree);}private static void initData(RedBlackTree tree) {int[] nums={430,261,636,95,344,559,822,37,131,330,369,499,594,705,981,262,345,485,664,818};for (int i = 0; i < nums.length; i++) {tree.add(nums[i]);}// tree.inorder(tree.root);tree.levelOrder(tree.root);System.out.println(isValidRedBlackTree(tree.root));}
删除-1.单个红节点 直接删除
/*** 删除* 1.单个红节点 直接删除* 2.单个黑节点* 2.1兄黑* 2.1.1 对侄红 (指方向相反的侄节点)* 父兄交替旋转、然后按父红兄弟黑换色 (最后一步的换色,父红两兄弟黑,是按交替旋转之后的关系处理。)* 2.1.2 顺侄红(指方向相同的侄节点)* 兄侄交替旋转,并调换颜色,就会变成对侄红,然后按2.1.1处理* 2.1.3 双侄黑* 兄变红父变黑,如果父本身就是黑,就以父亲角度按情况2处理** 2.2 兄红* 父兄交替旋转,并调换颜色,新的兄节点将变黑,在按2.1处理* 3.带有一个子节点(当一个节点只有一个子节点时(空叶子除外),该节点必定是黑节点,其子节点必定是红色)* 用红子节点值替换,然后直接删除红子节点* 4.带有两个子节点* 找到左子树中最靠右的子节点,用该节点值替换,并删除该节点按情况1,2,3处理(左子树中最大的值,也是离其最近的值)** @param data 数据*/public void delete(int data) {TreeNode find = find(data);if (find.isLeaf){System.out.println("没有找到");return;}//1.单个红节点if (!find.isBlack()){if (find.left.isLeaf&&find.right.isLeaf){TreeNode parent = find.parent;TreeNode nil=new TreeNode(BLACK,null,parent,true);if (data<parent.data){parent.left=nil;}else {parent.right=nil;}}else {//4.带有两个子节点}}else {//3.带有一个子节点,用红子节点值替换,然后直接删除红子节点}}
删除-3.带有一个子节点
//3.带有一个子节点,用红子节点值替换,然后直接删除红子节点if (find.left.isLeaf&&!find.right.isBlack()){find.data=find.right.data;find.right= new TreeNode(BLACK,null,find,true);}else if (find.right.isLeaf&&!find.left.isBlack()){find.data=find.left.data;find.left= new TreeNode(BLACK,null,find,true);}
删除-4.带有两个子节点
else if (!find.left.isLeaf&&!find.right.isLeaf){//4.带有两个子节点TreeNode replace = findReplace(find);delete(replace.data);find.data= replace.data;}else {//2.单个黑结点/*** 查找替代的结点* 中序遍历线索树的直接前驱结点* @param node 删除的结点* @return 查找替代*/public TreeNode findReplace(TreeNode node) {TreeNode left = node.left;while (!left.isLeaf) {left=left.right;}return left.parent;}
删除-2.单个黑结点
2.1.1兄黑,对侄红
TreeNode parent=find.parent;TreeNode brother=parent.left!=find?parent.left:parent.right;boolean left=find.data<parent.data;//对侄TreeNode duiNephew=left?brother.right:brother.left;//顺侄TreeNode shunNephew=left?brother.left:brother.right;if (brother.isBlack()){//2.1兄黑//2.1.1 对侄红TreeNode duiNephew=left?brother.right:brother.left;if (!duiNephew.isBlack()){//父兄交替旋转TreeNode grandpa=parent.parent;if (brother.data<grandpa.data){grandpa.left=brother;}else {grandpa.right=brother;}brother.parent=grandpa;if (left){brother.left=parent;}else {brother.right=parent;}parent.parent=brother;TreeNode nil=new TreeNode(BLACK,null,parent,true);parent.left=nil;parent.right=nil;//并调换颜色brother.color=RED;duiNephew.color=BLACK;parent.color=BLACK;}else if (!shunNephew.isBlack()){//2.1.2 顺侄红}else if (brother.left.isBlack()&&brother.right.isBlack()){//2.1.3 双侄黑}else{//兄红}
2.1.2兄黑,顺侄红
//兄侄交替旋转,并调换颜色,就会变成对侄红,if (brother.data< parent.data){parent.left=shunNephew;shunNephew.left=brother;}else {parent.right=shunNephew;shunNephew.right=brother;}shunNephew.parent=parent;brother.parent=shunNephew;TreeNode nil=new TreeNode(BLACK,null,brother,true);brother.left=nil;brother.right=nil;brother.color=RED;shunNephew.color=BLACK;delete(data);
2.1.3 兄黑,双侄黑
//兄变红父变黑,如果父本身就是黑,就以父亲角度按情况2处理brother.color=RED;parent.color=BLACK;TreeNode nil=new TreeNode(BLACK,null,parent,true);if (find.data< parent.data){parent.left=nil;}else {parent.right=nil;}
删除-2.单个黑结点 2.2兄红
//父兄交替旋转,并调换颜色,新的兄节点将变黑,在按2.1处理TreeNode grandpa=parent.parent;if (brother.data<grandpa.data){grandpa.left=brother;}else {grandpa.right=brother;}brother.parent=grandpa;TreeNode tmp;if (data<parent.data){tmp=brother.left;brother.left=parent;}else {tmp=brother.right;brother.right=parent;}parent.parent=brother;if (data<parent.data){parent.left=find;parent.right=tmp;}else {parent.left=tmp;parent.right=find;}brother.color=BLACK;parent.color=RED;delete(data);
测试删除
public static void main(String[] args) {RedBlackTree tree = new RedBlackTree();
// testAdd(tree);initData(tree);testDelete(tree);tree.levelOrder(tree.root);System.out.println(isValidRedBlackTree(tree.root));}private static void testDelete(RedBlackTree tree) {tree.delete(262);//1tree.delete(818);//1tree.delete(705);//3tree.delete(369);//3tree.add(346);tree.delete(430);//4tree.delete(594);//2.1.1tree.add(570);tree.delete(485);//2.1.1tree.add(565);tree.delete(499);//2.1.2tree.add(335);tree.delete(345);//2.1.2tree.delete(559);//2.1.3tree.delete(570);tree.delete(565);//2.2tree.delete(37);tree.delete(131);tree.delete(95);//2.2}
附录源码
package test;import java.util.LinkedList;
import java.util.Queue;public class RedBlackTree {private static final boolean RED = false;private static final boolean BLACK = true;//根结点TreeNode root;public void initRoot(int data) {root = new TreeNode(BLACK, data, null, false);TreeNode nil = new TreeNode(BLACK, null, root, true);root.left = nil;root.right = nil;}/*** 增加* 1. 父为黑,直接插入* 2. 父叔为红,颜色调换* 3. 父红叔黑,颜色调换,再移动* 4. 父子不同向,先掰直,再执行第3种情况** @param data 数据*/public void add(int data) {if (root == null) {initRoot(data);return;}TreeNode find = find(data);if (!find.isLeaf) {System.out.println("不能插入相同数据的结点");return;}TreeNode parent = find.parent;TreeNode newNode = new TreeNode(RED, data, parent);TreeNode nil = new TreeNode(BLACK, null, newNode, true);newNode.left = nil;newNode.right = nil;if (data < parent.data) {parent.left = newNode;} else {parent.right = newNode;}//1.父为黑,直接插入if (parent.isBlack()) {//不需要额外的操作} else {TreeNode grandpa = parent.parent;TreeNode uncle = grandpa.left != parent ? grandpa.left : grandpa.right;//2. 父叔为红,颜色调换if (!uncle.isBlack()) {parent.color = BLACK;uncle.color = BLACK;grandpa.color = RED;//如果爷爷是根节点if (grandpa == root) {grandpa.color = BLACK;return;}//爷爷变成红色后,它的父叔可能为红TreeNode cur=grandpa;parent=cur.parent;grandpa=parent.parent;if (parent==null||grandpa==null){return;}uncle=grandpa.left != parent ? grandpa.left : grandpa.right;while (!cur.isBlack()&&!parent.isBlack()&&!uncle.isBlack()){parent.color = BLACK;uncle.color = BLACK;grandpa.color = RED;//如果爷爷是根节点if (grandpa == root) {grandpa.color = BLACK;break;}cur=grandpa;parent=cur.parent;grandpa=parent.parent;uncle=grandpa.left != parent ? grandpa.left : grandpa.right;}} else {boolean right1 = data > parent.data;boolean right2 = parent.data > grandpa.data;boolean direct1 = right1 && right2;boolean left1 = data < parent.data;boolean left2 = parent.data < grandpa.data;boolean direct2 = left1 && left2;//3. 父红叔黑,颜色调换,再移动if (direct1 || direct2) {op(data, parent, grandpa);} else {//4. 父子不同向,先掰直,再执行第3种情况if (left1) {grandpa.right = newNode;newNode.right = parent;}if (right1) {grandpa.left = newNode;newNode.left = parent;}newNode.parent = grandpa;parent.parent = newNode;TreeNode newNil = new TreeNode(BLACK, null, parent, true);parent.left = newNil;parent.right = newNil;op(parent.data, newNode, grandpa);}}}}public void op(int data, TreeNode parent, TreeNode grandpa) {boolean right1 = data > parent.data;boolean right2 = parent.data > grandpa.data;boolean direct1 = right1 && right2;boolean left1 = data < parent.data;boolean left2 = parent.data < grandpa.data;boolean direct2 = left1 && left2;boolean tmp = grandpa.color;grandpa.color = parent.color;parent.color = tmp;TreeNode grandpaPa = grandpa.parent;if (parent.data < grandpaPa.data) {grandpaPa.left = parent;} else {grandpaPa.right = parent;}parent.parent = grandpaPa;if (direct1) {parent.left = grandpa;grandpa.parent = parent;} else if (direct2) {parent.right = grandpa;grandpa.parent = parent;}grandpa.left = new TreeNode(BLACK, null, grandpa, true);grandpa.right = new TreeNode(BLACK, null, grandpa, true);}/*** 删除* 1.单个红节点 直接删除* 2.单个黑节点* 2.1兄黑* 2.1.1 对侄红 (指方向相反的侄节点)* 父兄交替旋转、然后按父红兄弟黑换色 (最后一步的换色,父红两兄弟黑,是按交替旋转之后的关系处理。)* 2.1.2 顺侄红(指方向相同的侄节点)* 兄侄交替旋转,并调换颜色,就会变成对侄红,然后按2.1.1处理* 2.1.3 双侄黑* 兄变红父变黑,如果父本身就是黑,就以父亲角度按情况2处理** 2.2 兄红* 父兄交替旋转,并调换颜色,新的兄节点将变黑,在按2.1处理* 3.带有一个子节点(当一个节点只有一个子节点时(空叶子除外),该节点必定是黑节点,其子节点必定是红色)* 用红子节点值替换,然后直接删除红子节点* 4.带有两个子节点* 找到左子树中最靠右的子节点,用该节点值替换,并删除该节点按情况1,2,3处理(左子树中最大的值,也是离其最近的值)** @param data 数据*/public void delete(int data) {TreeNode find = find(data);if (find.isLeaf){System.out.println("没有找到");return;}//1.单个红节点if (!find.isBlack()){if (find.left.isLeaf&&find.right.isLeaf){TreeNode parent = find.parent;TreeNode nil=new TreeNode(BLACK,null,parent,true);if (data<parent.data){parent.left=nil;}else {parent.right=nil;}}else {//4.带有两个子节点TreeNode replace = findReplace(find);delete(replace.data);find.data= replace.data;}}else {//3.带有一个子节点,用红子节点值替换,然后直接删除红子节点if (find.left.isLeaf&&!find.right.isBlack()){find.data=find.right.data;find.right= new TreeNode(BLACK,null,find,true);}else if (find.right.isLeaf&&!find.left.isBlack()){find.data=find.left.data;find.left= new TreeNode(BLACK,null,find,true);} else if (!find.left.isLeaf&&!find.right.isLeaf){//4.带有两个子节点TreeNode replace = findReplace(find);delete(replace.data);find.data= replace.data;}else {//2.单个黑结点TreeNode parent=find.parent;TreeNode brother=parent.left!=find?parent.left:parent.right;boolean left=find.data<parent.data;//对侄TreeNode duiNephew=left?brother.right:brother.left;//顺侄TreeNode shunNephew=left?brother.left:brother.right;if (brother.isBlack()){//2.1兄黑//2.1.1 对侄红if (!duiNephew.isBlack()){//父兄交替旋转TreeNode grandpa=parent.parent;if (brother.data<grandpa.data){grandpa.left=brother;}else {grandpa.right=brother;}brother.parent=grandpa;if (left){brother.left=parent;}else {brother.right=parent;}parent.parent=brother;TreeNode nil=new TreeNode(BLACK,null,parent,true);parent.left=nil;parent.right=nil;//并调换颜色brother.color=RED;duiNephew.color=BLACK;parent.color=BLACK;} else if (!shunNephew.isBlack()){//2.1.2 顺侄红//兄侄交替旋转,并调换颜色,就会变成对侄红,if (brother.data< parent.data){parent.left=shunNephew;shunNephew.left=brother;}else {parent.right=shunNephew;shunNephew.right=brother;}shunNephew.parent=parent;brother.parent=shunNephew;TreeNode nil=new TreeNode(BLACK,null,brother,true);brother.left=nil;brother.right=nil;brother.color=RED;shunNephew.color=BLACK;delete(data);} else if (brother.left.isBlack()&&brother.right.isBlack()){//2.1.3 双侄黑//兄变红父变黑,如果父本身就是黑,就以父亲角度按情况2处理brother.color=RED;parent.color=BLACK;TreeNode nil=new TreeNode(BLACK,null,parent,true);if (find.data< parent.data){parent.left=nil;}else {parent.right=nil;}}}else {//2.2兄红//父兄交替旋转,并调换颜色,新的兄节点将变黑,在按2.1处理TreeNode grandpa=parent.parent;if (brother.data<grandpa.data){grandpa.left=brother;}else {grandpa.right=brother;}brother.parent=grandpa;TreeNode tmp;if (data<parent.data){tmp=brother.left;brother.left=parent;}else {tmp=brother.right;brother.right=parent;}parent.parent=brother;if (data<parent.data){parent.left=find;parent.right=tmp;}else {parent.left=tmp;parent.right=find;}brother.color=BLACK;parent.color=RED;delete(data);}}}}/*** 查找** @param data 数据* @return 查找结点,如果差不到就会返回叶子结点*/public TreeNode find(int data) {TreeNode find = root;while (!find.isLeaf) {if (data < find.data) {find = find.left;} else if(find.data.equals(data)){return find;} else if (data > find.data) {find = find.right;}}return find;}/*** 查找替代的结点* 中序遍历线索树的直接前驱结点* @param node 删除的结点* @return 查找替代*/public TreeNode findReplace(TreeNode node) {TreeNode left = node.left;while (!left.isLeaf) {left=left.right;}return left.parent;}//中序遍历public void inorder(TreeNode root) {if (root == null) {return;}if (!root.left.isLeaf) {inorder(root.left);}System.out.println(root);if (!root.right.isLeaf) {inorder(root.right);}}//层序遍历public void levelOrder(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode cur = queue.poll();System.out.print(cur + "\t");if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}System.out.println();}}private static int blackHeight = -1;//判断是否是有效的红黑树public static boolean isValidRedBlackTree(TreeNode root) {if (root == null) {return true;}// 检查根节点是否是黑色if (root.color != BLACK) {return false;}// 计算黑高度,并检查红黑平衡blackHeight = -1;if (!checkBlackBalance(root, 0)) {return false;}// 递归检查每个节点return isValidRedBlackSubtree(root);}private static boolean checkBlackBalance(TreeNode node, int currentBlackHeight) {if (node.isLeaf) {if (blackHeight == -1) {blackHeight = currentBlackHeight;return true;} else {return currentBlackHeight == blackHeight;}}if (node.color == BLACK) {currentBlackHeight++;}return checkBlackBalance(node.left, currentBlackHeight) && checkBlackBalance(node.right, currentBlackHeight);}private static boolean isValidRedBlackSubtree(TreeNode node) {if (node == null) {return true;}// 检查红黑树性质if (node.color == RED) {if ((node.left != null && node.left.color != BLACK) || (node.right != null && node.right.color != BLACK)) {return false;}}// 递归检查左右子树return isValidRedBlackSubtree(node.left) && isValidRedBlackSubtree(node.right);}public static void main(String[] args) {RedBlackTree tree = new RedBlackTree();
// testAdd(tree);initData(tree);testDelete(tree);tree.levelOrder(tree.root);System.out.println(isValidRedBlackTree(tree.root));}private static void testDelete(RedBlackTree tree) {tree.delete(262);//1tree.delete(818);//1tree.delete(705);//3tree.delete(369);//3tree.add(346);tree.delete(430);//4tree.delete(594);//2.1.1tree.add(570);tree.delete(485);//2.1.1tree.add(565);tree.delete(499);//2.1.2tree.add(335);tree.delete(345);//2.1.2tree.delete(559);//2.1.3tree.delete(570);tree.delete(565);//2.2tree.delete(37);tree.delete(131);tree.delete(95);//2.2}private static void initData(RedBlackTree tree) {int[] nums={430,261,636,95,344,559,822,37,131,330,369,499,594,705,981,262,345,485,664,818};for (int i = 0; i < nums.length; i++) {tree.add(nums[i]);}// tree.inorder(tree.root);
// tree.levelOrder(tree.root);
// System.out.println(isValidRedBlackTree(tree.root));}private static void testAdd(RedBlackTree tree) {tree.add(157);//0tree.add(12);//1tree.add(200);//1tree.add(250);//2tree.add(260);//3tree.add(220);//2tree.add(210);//4tree.add(11);//1tree.add(10);//3tree.add(7);//2tree.add(9);//4tree.inorder(tree.root);
// tree.levelOrder(tree.root);System.out.println(isValidRedBlackTree(tree.root));}}//结点
class TreeNode {//true是黑色,false是红色boolean color;//数据Integer data;TreeNode left;TreeNode right;private static final boolean RED = false;private static final boolean BLACK = true;//是否是叶子结点boolean isLeaf;//方便实现TreeNode parent;public TreeNode() {}public TreeNode(int data) {this.data = data;}public TreeNode(boolean color, Integer data) {this.color = color;this.data = data;}public TreeNode(boolean color, Integer data, TreeNode parent) {this.color = color;this.data = data;this.parent = parent;}public TreeNode(boolean color, Integer data, TreeNode parent, boolean isLeaf) {this.color = color;this.data = data;this.parent = parent;this.isLeaf = isLeaf;}// public TreeNode(Integer data,TreeNode left, TreeNode right) {
// this.data = data;
// this.left = left;
// this.right = right;
// }public boolean isBlack() {return color == BLACK;}@Overridepublic String toString() {return "TreeNode{" +"color=" + color +", data=" + data +'}';}}
最后
2024-3-30 23:05:13
写了一天
迎着日光月光星光,直面风霜雨霜雪霜。
相关文章:

手写红黑树【数据结构】
手写红黑树【数据结构】 前言版权推荐手写红黑树一、理论知识红黑树的特征增加删除 二、手写代码初始-树结点初始-红黑树初始-遍历初始-判断红黑树是否有效查找增加-1.父为黑,直接插入增加-2. 父叔为红,颜色调换增加-3. 父红叔黑,颜色调换&am…...

[蓝桥杯练习]通电
kruskal做法(加边) #include <bits/stdc.h> using namespace std; int x[10005],y[10005],z[10005];//存储i点的x与y坐标 int bcj[10005];//并查集 struct Edge{//边 int v1,v2; double w; }edge[2000005]; int cmp(Edge a, Edge b){return a.w < b.w;} int find(i…...
安全算法 - 摘要算法
摘要算法是一种将任意长度的数据转换为固定长度字节串的算法。它具有以下特点和应用。 首先,摘要算法能够生成一个唯一且固定长度的摘要值,用于验证数据的完整性和一致性。无论输入数据有多长,生成的摘要值始终是固定长度的,且即…...

操作系统:动静态库
目录 1.动静态库 1.1.如何制作一个库 1.2.静态库的使用和管理 1.3.安装和使用库 1.4.动态库 1.4.1.动态库的实现 1.4.2.动态库与静态库的区别 1.4.3.共享动态库给系统的方法 2.动态链接 2.1.操作系统层面的动态链接 1.动静态库 静态库(.a)&…...

车载电子电器架构 —— 局部网络管理汇总
车载电子电器架构 —— 局部网络管理汇总 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明…...

网络安全 | 什么是DDoS攻击?
关注WX:CodingTechWork DDoS-介绍 DoS:Denial of Service,拒绝服务。DDoS是通过大规模的网络流量使得正常流量不能访问受害者目标,是一种压垮性的网络攻击,而不是一种入侵手段。NTP网络时间协议,设备需要…...
[Godot] 3D拾取
CollisionObject3D文档 Camera3D文档 CollisionObject3D有个信号_input_event,可以用于处理3D拾取。 Camera3D也有project_position用于将屏幕空间坐标投影到3D空间。 extends Node3D#是否处于选中状态 var selected : bool false #摄像机的前向量 var front : V…...

知识融合:知识图谱构建的关键技术
目录 一、引言二、知识图谱基础2.1 知识表示三元组属性图 2.2 知识抽取实体抽取关系抽取属性抽取 三、知识融合的核心问题3.1 实体识别与链接实体识别实体链接 3.2 重复实体合并方法示例 3.3 关系融合挑战方法示例 四、知识融合技术深度解析4.1 基于规则的方法规则设计原则规则…...

外贸建站:WordPress搭建外贸独立站零基础自建站完整教程(2024)
对于做外贸来说,拥有自己的外贸独立网站真的非常重要。在外贸领域,如今各平台竞争激烈,规则多,成本高,价格战、政策变化快,还存在封店风险等等因素。在这种情况下,拥有外贸独立站就能很好规避上…...

【教程】Kotlin语言学习笔记(五)——Lambda表达式与条件控制
写在前面: 如果文章对你有帮助,记得点赞关注加收藏一波,利于以后需要的时候复习,多谢支持! 【Kotlin语言学习】系列文章 第一章 《认识Kotlin》 第二章 《数据类型》 第三章 《数据容器》 第四章 《方法》 第五章 《L…...

C++的并发世界(三)——线程对象生命周期
0.案例代码 先看下面一个例子: #include <iostream> #include <thread>void ThreadMain() {std::cout << "begin sub thread:" << std::this_thread::get_id()<<std::endl;for (int i 0; i < 10; i){std::cout <&…...

SAD法(附python实现)和Siamese神经网络计算图像的视差图
1 视差图 视差图:以左视图视差图为例,在像素位置p的视差值等于该像素在右图上的匹配点的列坐标减去其在左图上的列坐标 视差图和深度图: z f b d z \frac{fb}{d} zdfb 其中 d d d 是视差, f f f 是焦距, b b…...

基于DWT(离散小波变换)的图像加密水印算法,Matlab实现
博主简介: 专注、专一于Matlab图像处理学习、交流,matlab图像代码代做/项目合作可以联系(QQ:3249726188) 个人主页:Matlab_ImagePro-CSDN博客 原则:代码均由本人编写完成,非中介,提供…...

【威胁情报综述阅读3】Cyber Threat Intelligence Mining for Proactive Cybersecurity Defense
【威胁情报综述阅读1】Cyber Threat Intelligence Mining for Proactive Cybersecurity Defense: A Survey and New Perspectives 写在最前面一、介绍二、网络威胁情报挖掘方法和分类A. 研究方法1) 第 1 步 - 网络场景分析:2) 第 2 步 - 数据…...

在编程中使用中文到底该不该??
看到知乎上有个热门问题,为什么很多人反对中文在编程中的使用? 这个问题有几百万的浏览热度,其中排名第一的回答非常简洁,我深以为然: 在国内做开发,用中文写注释、写文档,是非常好的习惯&…...
PyQt6从入门到放弃
PyQt6从入门到放弃 安装PyQt6 pip install PyQt6# 查看QT和PyQT的版本 from PyQt6.QtCore import QT_VERSION_STR from PyQt6.QtCore import PYQT_VERSION_STR print(QT_VERSION_STR) print(PYQT_VERSION_STR)PyQt6模块 PyQt6类由一系列模块组成包括QtCore、QtGui、QtWidgets…...
PhpWord导入试卷
规定word导入格式 1、[单选题][2024][一般]题目1 A.选项1 B.选项2 C.选项3 D.选项4 答案:D 试题图片(上传多媒体图片): 分数:2 答案解析: 2、[多选题][2024][困难]题目2 A.选项1 B.选项2 C.选项3 D.选项4 E…...
C# 运算符重载 之前的小总结
C# 中支持运算符重载,所谓运算符重载就是我们可以使用自定义类型来重新定义 C# 中大多数运算符的功能。运算符重载需要通过 operator 关键字后跟运算符的形式来定义的,我们可以将被重新定义的运算符看作是具有特殊名称的函数,与其他函数一样&…...

XenCenter 2024 创建一个虚拟机
前言 实现,创建一个虚拟机,内存,cpu,磁盘,名称,网卡,配置 Xen Center 2024 download 创建虚拟机 选择系统类型 定义虚拟机名称 选择ISO镜像库 选择主服务器 分配虚拟机内存,cpu资源…...
tomcat 知多少
Tomcat的缺省端口: 默认端口为8080,可以通过在tomcat安装包conf目录下,service.xml中的Connector元素的port属性来修改端口。 tomcat 常见 Connector 运行模式(优化): 这三种模式的不同之处如下: BIO : 一…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...

C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...

数据分析六部曲?
引言 上一章我们说到了数据分析六部曲,何谓六部曲呢? 其实啊,数据分析没那么难,只要掌握了下面这六个步骤,也就是数据分析六部曲,就算你是个啥都不懂的小白,也能慢慢上手做数据分析啦。 第一…...