手写红黑树【数据结构】
手写红黑树【数据结构】
- 前言
- 版权
- 推荐
- 手写红黑树
- 一、理论知识
- 红黑树的特征
- 增加
- 删除
- 二、手写代码
- 初始-树结点
- 初始-红黑树
- 初始-遍历
- 初始-判断红黑树是否有效
- 查找
- 增加-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 : 一…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...

C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
【实施指南】Android客户端HTTPS双向认证实施指南
🔐 一、所需准备材料 证书文件(6类核心文件) 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...
13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析
LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...

李沐--动手学深度学习--GRU
1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...