做网站不给源代码,吉林省招标网官方网站,下载软件的注意事项,网站开发者工具下载手写红黑树【数据结构】 前言版权推荐手写红黑树一、理论知识红黑树的特征增加删除 二、手写代码初始-树结点初始-红黑树初始-遍历初始-判断红黑树是否有效查找增加-1.父为黑#xff0c;直接插入增加-2. 父叔为红#xff0c;颜色调换增加-3. 父红叔黑#xff0c;颜色调换直接插入增加-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.带有两个子节点!* 找到左子树中最靠右的子节点用该节点值替换并删除该节点按情况123处理左子树中最大的值也是离其最近的值)** 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;}QueueTreeNode 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(datafind.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 curgrandpa;parentcur.parent;grandpaparent.parent;if (parentnull||grandpanull){return;}unclegrandpa.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;}curgrandpa;parentcur.parent;grandpaparent.parent;unclegrandpa.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.带有两个子节点* 找到左子树中最靠右的子节点用该节点值替换并删除该节点按情况123处理左子树中最大的值也是离其最近的值)** 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.isLeaffind.right.isLeaf){TreeNode parent find.parent;TreeNode nilnew TreeNode(BLACK,null,parent,true);if (dataparent.data){parent.leftnil;}else {parent.rightnil;}}else {//4.带有两个子节点}}else {//3.带有一个子节点,用红子节点值替换然后直接删除红子节点}}
删除-3.带有一个子节点 //3.带有一个子节点,用红子节点值替换然后直接删除红子节点if (find.left.isLeaf!find.right.isBlack()){find.datafind.right.data;find.right new TreeNode(BLACK,null,find,true);}else if (find.right.isLeaf!find.left.isBlack()){find.datafind.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) {leftleft.right;}return left.parent;}删除-2.单个黑结点
2.1.1兄黑对侄红 TreeNode parentfind.parent;TreeNode brotherparent.left!find?parent.left:parent.right;boolean leftfind.dataparent.data;//对侄TreeNode duiNephewleft?brother.right:brother.left;//顺侄TreeNode shunNephewleft?brother.left:brother.right;if (brother.isBlack()){//2.1兄黑//2.1.1 对侄红TreeNode duiNephewleft?brother.right:brother.left;if (!duiNephew.isBlack()){//父兄交替旋转TreeNode grandpaparent.parent;if (brother.datagrandpa.data){grandpa.leftbrother;}else {grandpa.rightbrother;}brother.parentgrandpa;if (left){brother.leftparent;}else {brother.rightparent;}parent.parentbrother;TreeNode nilnew TreeNode(BLACK,null,parent,true);parent.leftnil;parent.rightnil;//并调换颜色brother.colorRED;duiNephew.colorBLACK;parent.colorBLACK;}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.leftshunNephew;shunNephew.leftbrother;}else {parent.rightshunNephew;shunNephew.rightbrother;}shunNephew.parentparent;brother.parentshunNephew;TreeNode nilnew TreeNode(BLACK,null,brother,true);brother.leftnil;brother.rightnil;brother.colorRED;shunNephew.colorBLACK;delete(data);
2.1.3 兄黑双侄黑 //兄变红父变黑如果父本身就是黑就以父亲角度按情况2处理brother.colorRED;parent.colorBLACK;TreeNode nilnew TreeNode(BLACK,null,parent,true);if (find.data parent.data){parent.leftnil;}else {parent.rightnil;}删除-2.单个黑结点 2.2兄红 //父兄交替旋转并调换颜色新的兄节点将变黑在按2.1处理TreeNode grandpaparent.parent;if (brother.datagrandpa.data){grandpa.leftbrother;}else {grandpa.rightbrother;}brother.parentgrandpa;TreeNode tmp;if (dataparent.data){tmpbrother.left;brother.leftparent;}else {tmpbrother.right;brother.rightparent;}parent.parentbrother;if (dataparent.data){parent.leftfind;parent.righttmp;}else {parent.lefttmp;parent.rightfind;}brother.colorBLACK;parent.colorRED;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 curgrandpa;parentcur.parent;grandpaparent.parent;if (parentnull||grandpanull){return;}unclegrandpa.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;}curgrandpa;parentcur.parent;grandpaparent.parent;unclegrandpa.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.带有两个子节点* 找到左子树中最靠右的子节点用该节点值替换并删除该节点按情况123处理左子树中最大的值也是离其最近的值)** 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.isLeaffind.right.isLeaf){TreeNode parent find.parent;TreeNode nilnew TreeNode(BLACK,null,parent,true);if (dataparent.data){parent.leftnil;}else {parent.rightnil;}}else {//4.带有两个子节点TreeNode replace findReplace(find);delete(replace.data);find.data replace.data;}}else {//3.带有一个子节点,用红子节点值替换然后直接删除红子节点if (find.left.isLeaf!find.right.isBlack()){find.datafind.right.data;find.right new TreeNode(BLACK,null,find,true);}else if (find.right.isLeaf!find.left.isBlack()){find.datafind.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 parentfind.parent;TreeNode brotherparent.left!find?parent.left:parent.right;boolean leftfind.dataparent.data;//对侄TreeNode duiNephewleft?brother.right:brother.left;//顺侄TreeNode shunNephewleft?brother.left:brother.right;if (brother.isBlack()){//2.1兄黑//2.1.1 对侄红if (!duiNephew.isBlack()){//父兄交替旋转TreeNode grandpaparent.parent;if (brother.datagrandpa.data){grandpa.leftbrother;}else {grandpa.rightbrother;}brother.parentgrandpa;if (left){brother.leftparent;}else {brother.rightparent;}parent.parentbrother;TreeNode nilnew TreeNode(BLACK,null,parent,true);parent.leftnil;parent.rightnil;//并调换颜色brother.colorRED;duiNephew.colorBLACK;parent.colorBLACK;} else if (!shunNephew.isBlack()){//2.1.2 顺侄红//兄侄交替旋转并调换颜色就会变成对侄红if (brother.data parent.data){parent.leftshunNephew;shunNephew.leftbrother;}else {parent.rightshunNephew;shunNephew.rightbrother;}shunNephew.parentparent;brother.parentshunNephew;TreeNode nilnew TreeNode(BLACK,null,brother,true);brother.leftnil;brother.rightnil;brother.colorRED;shunNephew.colorBLACK;delete(data);} else if (brother.left.isBlack()brother.right.isBlack()){//2.1.3 双侄黑//兄变红父变黑如果父本身就是黑就以父亲角度按情况2处理brother.colorRED;parent.colorBLACK;TreeNode nilnew TreeNode(BLACK,null,parent,true);if (find.data parent.data){parent.leftnil;}else {parent.rightnil;}}}else {//2.2兄红//父兄交替旋转并调换颜色新的兄节点将变黑在按2.1处理TreeNode grandpaparent.parent;if (brother.datagrandpa.data){grandpa.leftbrother;}else {grandpa.rightbrother;}brother.parentgrandpa;TreeNode tmp;if (dataparent.data){tmpbrother.left;brother.leftparent;}else {tmpbrother.right;brother.rightparent;}parent.parentbrother;if (dataparent.data){parent.leftfind;parent.righttmp;}else {parent.lefttmp;parent.rightfind;}brother.colorBLACK;parent.colorRED;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) {leftleft.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;}QueueTreeNode 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
写了一天
迎着日光月光星光直面风霜雨霜雪霜。
