海口网站建设优化,上海企业营销型网站建设,最简单的网站,东平县住房和城乡建设局网站文章目录 基本定义五大性质红黑树和2-3-4树的关系红黑树和2-3-4树各结点对应关系添加结点到红黑树注意事项添加的所有情况 添加导致不平衡叔父节点不是红色节点#xff08;祖父节点为红色#xff09;添加不平衡LL/RR添加不平衡LR/RL 叔父节点是红色节点#xff08;祖父节点为… 文章目录 基本定义五大性质红黑树和2-3-4树的关系红黑树和2-3-4树各结点对应关系添加结点到红黑树注意事项添加的所有情况 添加导致不平衡叔父节点不是红色节点祖父节点为红色添加不平衡LL/RR添加不平衡LR/RL 叔父节点是红色节点祖父节点为黑色 删除删除红色节点删除黑色节点删除黑色叶子节点——情况一删除黑色叶子节点——情况二删除黑色叶子节点——情况三删除黑色叶子节点——情况四 红黑树与AVL平衡二叉树树比较红黑树与B树B树比较完整的Java测试代码RedBlackTreeBinaryTreeInfoBinaryTreesInorderPrinterLevelOrderPrinterPrinterStrings 总结 基本定义
红黑树是一颗二叉搜索树它在每个结点上增加了一个存储位来表示结点的颜色可以是红色或者黑色。 通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而是近似平衡的。
五大性质
1、结点必须是红色或者黑色。 2、根节点是黑色。 3、叶子结点外部结点、空结点不是传统上认为的那种叶子结点如图中的那些NIL结点都是黑色 4、红色结点的子结点都是黑色 于是有推论 4.1、红色结点的父结点都是黑色 4.2、从根结点到叶子结点的所有路径上不能有两个连续的红色结点 5、从任一结点到叶子结点外部结点、空结点不是传统上认为的那种叶子结点如图中的那些NIL结点的所有路径都包含相同数目的黑色结点 如图所示
红黑树和2-3-4树的关系 红黑树和4阶B树2-3-4树具有等价性 黑色节点与它的红色子节点融合在一起形成一个B树节点 红黑树的黑色节点个数与4阶B树的节点总个数相等
红黑树和2-3-4树各结点对应关系
红黑红、黑红、红黑、黑
添加结点到红黑树
注意事项
一般新添加的节点默认为红色这样对红黑树的性质影响最小性质1、2、3、5都满足性质4不一定 如果新添加的节点是根节点染成黑色即可
添加的所有情况
添加结点到红黑树总共有12中情况
有4种情况满足红黑树的性质父节点为黑色节点因此不需要做任何处理。如下图所示的4种紫红色节点添加情况
有8种情况不满足红黑树的性质父节点为红色节点但其实可以归纳为3种情况。如下图所示的8种紫红色节点添加情况。
添加导致不平衡
添加结点导致红黑树出现不平衡的情况。
叔父节点不是红色节点祖父节点为红色
添加不平衡LL/RR
判断条件叔父节点不是红色节点 父节点是祖父节点的左孩子自己是父节点的左孩子LL) 父节点是祖父节点的右孩子自己是父节点的右孩子RR) 如何恢复平衡 1、父节点染成黑色祖父节点染成红色 2、对祖父节点进行旋转操作LL是右旋RR是左旋 添加不平衡LR/RL
判断条件叔父节点不是红色节点 父节点是祖父节点的左孩子自己是父节点的右孩子LR) 父节点是祖父节点的右孩子自己是父节点的左孩子RL) 如何恢复平衡 1、把自己染成黑色祖父节点染成红色 2、进行两次旋转第一次旋转是转换成LL/RR情况第二次旋转恢复平衡 2.1、LR先按照父节点左旋变成LL再按照祖父节点右旋 2.2、RL先按照父节点右旋变成RR再按照祖父节点左旋
叔父节点是红色节点祖父节点为黑色
判断条件叔父节点为红色 如何恢复平衡 1、父节点、叔父节点都染成黑色 2、祖父节点染成红色并把祖父节点当成新添加的节点继续处理 2.1、如果祖父节点染成红色没有引起双红现象则处理结束 2.2、如果祖父节点染成红色也导致双红现象则继续按照是LL/RRLR/RL还是叔父节点为红色的三种情况处理最差情况是处理直到根节点把根节点染成了红色这个时候只需要把根节点染成黑色即可。
删除
B树中最后真正被删除的元素都在叶子节点中。详细见B树B-tree、B-树理论详解 删除节点就是上面图的4种情况。
删除红色节点
直接删除无需任何调整
删除黑色节点
有3种情况 1、拥有两个红色子节点的黑色节点不可能直接被删除因为会找它的红色子节点替代删除因此这种情况无需考虑 2、拥有1个红色子节点的黑色节点 (删除黑色节点后把替代的红色子节点染成黑色即可) 3、黑色叶子节点 (情况比较复杂)
删除黑色叶子节点——情况一
如果兄弟节点是红色节点, 1、把兄弟节点染成黑色父节点染成红色对父节点进行旋转2、此时兄弟节点变成黑色可以继续按照情况234进行处理 如图所示40结点的兄弟结点是20父结点是30。
删除黑色叶子节点——情况二
黑色兄弟节点没有一个红色子节点 1、如果父节点是红色把兄弟节点染成红色父节点染成黑色完成平衡维护。 2、如果父节点是黑色把兄弟节点染成红色把父节点当成待删除的节点向上递归或循环处理依然有情况1234。
删除黑色叶子节点——情况三
兄弟节点是左节点黑色兄弟节点的左孩子是黑色节点为LR场景需要先转变为LL方便后面的平衡旋转。 1、把兄弟节点的右孩子设为黑色兄弟节点设为红色对兄弟节点进行左旋确保兄弟节点有一个红色左孩子此时变成情况4。
删除黑色叶子节点——情况四
兄弟节点是左节点兄弟节点的左孩子是红色节点LL场景 1、把兄弟节点的颜色设置为父节点的颜色父节点和兄弟节点的左孩子都设置为黑色 对父节点进行右旋恢复平衡。
红黑树与AVL平衡二叉树树比较
AVL树的平衡标准比较严格每个左右子树的高度差不超过1。 红黑树的平衡标准比较宽松没有一条路径会大于其他路径的两倍。 相对于AVL树来说红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作总体性能要优于 AVL树。 红黑树的平均统计性能优于AVL树实际应用中更多选择使用红黑树。
红黑树与B树B树比较
红黑树的分叉少适合在内存中使用如果在硬盘中使用的话当数据量大的时候红黑树的层高比较高会带来比较多的磁盘IO影响查询性能比如说100万的数据量用红黑树的话大概是20层的层高会有20次磁盘IO。 B树和B树的分叉比较多B树分叉一般能到两三百B树分叉多的能到上千所以B树和B树适合磁盘存储100万的数据量一般3层树高即可搞定只有3次磁盘IO实际中数据库一般把根节点存放在内存中所以其实只有两次IO。
完整的Java测试代码
RedBlackTree
package redblacktree;public class RedBlackTree implements BinaryTreeInfo {//红黑直接用布尔变量定义private static final boolean RED false;private static final boolean BLACK true;//初始化一个唯一的叶结点private final RBNode nil new RBNode();//根结点初始化为nilprivate RBNode root nil;public RBNode getRoot() {return root;}public void setRoot(RBNode root) {this.root root;}public RedBlackTree() {this.root nil;}public RedBlackTree(RBNode root) {this.root root;}//前序遍历二叉树public void preorderTreeWalk(RBNode x) {if(x ! nil) {System.out.print(x.key );preorderTreeWalk(x.left);preorderTreeWalk(x.right);}}//中序遍历二叉树public void inorderTreeWalk(RBNode x) {if(x ! nil) {inorderTreeWalk(x.left);System.out.print(x.key );inorderTreeWalk(x.right);}}//后序遍历二叉树public void postorderTreeWalk(RBNode x) {if(x ! nil) {postorderTreeWalk(x.left);postorderTreeWalk(x.right);System.out.print(x.key );}}//在二叉搜索树中查询某个值递归版本public RBNode treeSearch(RBNode x, Integer k) {if(x nil || k x.key) {return x;}if(k x.key) {return treeSearch(x.left, k);} else {return treeSearch(x.right, k);}}//在二叉搜索树中查询某个值循环版本public RBNode iterativeTreeSearch(RBNode x, Integer k) {while(x ! nil k ! x.key) {if(k x.key) {x x.left;} else {x x.right;}}return x;}//在二叉搜索树中查找包含最小值的节点public RBNode treeMinimum(RBNode x) {while (x.left ! nil) {x x.left;}return x;}//在二叉搜索树中查找包含最大值的节点public RBNode treeMaximum(RBNode x) {while (x.right ! nil) {x x.right;}return x;}//查找节点x的后继节点public RBNode treeSuccessor(RBNode x) {if(x.right ! nil) { //x的右子树不为空找右子树的最小值return treeMinimum(x.right);}RBNode y x.parent;while(y ! nil x y.right) {x y;y y.parent;}return y;}//查找节点x的前驱节点public RBNode treePredeceessor(RBNode x) {if(x.left ! nil) {return treeMaximum(x.left);}RBNode y x.parent;while(y ! nil x y.left) {x y;y y.parent;}return y;}/*** 围绕x左旋* xp xp* / /* x xr* / \ / \* xl xr x rr* / \ / \* rl rr xl rl** param t,x*/void leftRotate(RedBlackTree t, RBNode x) {RBNode y x.right; //让y等于x的右子节点x.right y.left; //将y的左子树转成x的右子树if(y.left ! t.nil) { //假如y的左孩子不为空将y的左孩子的父亲设置为xy.left.parent x;}y.parent x.parent; //将y的父亲设置为x的父亲if(x.parent t.nil) {t.root y; //考虑x原来为根节点的情况} else if (x.parent.left x) {x.parent.left y;} else {x.parent.right y;}y.left x;x.parent y;}/*** 围绕x右旋* xp xp* \ \* x xl* / \ / \* xl xr ll x* / \ / \* ll lr lr xr** param t,x*/void rightRotate(RedBlackTree t, RBNode x) {RBNode y x.left; //让y等于x的左子节点x.left y.right; //将y的右子树转成x的左子树if(y.right ! t.nil) { //假如y的右孩子不为空将y的右孩子的父亲设置为xy.right.parent x;}y.parent x.parent; //将y的父亲设置为x的父亲if(x.parent t.nil) {t.root y; //考虑x原来为根节点的情况} else if (x.parent.left x) {x.parent.left y;} else {x.parent.right y;}y.right x;x.parent y;}//红黑树的插入操作public void RBInsert(RedBlackTree t, RBNode z) {RBNode y t.nil;RBNode x t.root;while(x ! t.nil) {y x;if(z.key x.key) {x x.left;} else {x x.right;}}z.parent y;if(y t.nil) { //说明现在是棵空树t.root z;} else if (z.key y.key) {y.left z;} else {y.right z;}z.left t.nil;z.right t.nil;z.color RED;rbInsertFixup(t, z);}//插入节点后维护红黑树性质的过程public void rbInsertFixup(RedBlackTree t, RBNode z) {while (z.parent.color RED) {if(z.parent z.parent.parent.left) { //z的父节点是z的祖父节点的左孩子RBNode y z.parent.parent.right; //让y成为z的叔叔节点if (y.color RED) {/** z的父亲和叔叔节点都是红色* 根据红黑树性质z的祖父一定是黑色* 所以这时候可以把z的祖父设为红色* z的父亲和叔叔都设为黑色但这可能* 导致z的祖父产生双红节点的问题这* 时候把z设置成z的祖父继续向上递归*/z.parent.color BLACK;y.color BLACK;z.parent.parent.color RED;z z.parent.parent;} else {if (z z.parent.right) {/** z的父亲是左节点z是右节点,* 满足LR不平衡需要对z的父亲进行左旋,* 转变成LL不平衡*/z z.parent;leftRotate(t, z);}/** z的父亲是左节点z也是左节点* 满足LL不平衡把z的父亲设为黑色* z的祖父设为红色对z进行右旋* 即可满足平衡*/z.parent.color BLACK;z.parent.parent.color RED;rightRotate(t, z.parent.parent);}} else {RBNode y z.parent.parent.left; //让y成为z的叔叔节点if (y.color RED) {/** z的父亲和叔叔节点都是红色* 根据红黑树性质z的祖父一定是黑色* 所以这时候可以把z的祖父设为红色* z的父亲和叔叔都设为黑色但这可能* 导致z的祖父产生双红节点的问题这* 时候把z设置成z的祖父继续向上递归*/z.parent.color BLACK;y.color BLACK;z.parent.parent.color RED;z z.parent.parent;} else {if (z z.parent.left) {/** z的父亲是右节点z是左节点,* 满足RL不平衡需要对z的父亲进行右旋,* 转变成RR不平衡*/z z.parent;rightRotate(t, z);}/** z的父亲是右节点z也是右节点* 满足RR不平衡把z的父亲设为黑色* z的祖父设为红色对z进行左旋* 即可满足平衡*/z.parent.color BLACK;z.parent.parent.color RED;leftRotate(t, z.parent.parent);}}}t.root.color BLACK;}public void rbTransplant(RedBlackTree t, RBNode u, RBNode v) {if(u.parent t.nil) {t.root v;} else if(u u.parent.left) {u.parent.left v;} else {u.parent.right v;}v.parent u.parent;}//删除节点操作public void rbDelete(RedBlackTree t, RBNode z) {RBNode x;RBNode y z;boolean yOriginalColor y.color;if (z.left t.nil) {x z.right;//z的左孩子为空用z的右孩子替换z此时z的右孩子可以为空也可以不为空rbTransplant(t, z, z.right);} else if (z.right t.nil) {x z.left;//z仅有一个孩子且其为左孩子用z的左孩子替换zrbTransplant(t, z , z.left);} else {//z有两个孩子找z的后继节点y treeMinimum(z.right);yOriginalColor y.color;x y.right;if(y.parent z) {x.parent y;} else {//用以y的右孩子为根的树代替以y为根的树rbTransplant(t, y, y.right);y.right z.right;y.right.parent y;}//用以y为根的树代替以z为根的树rbTransplant(t, z, y);y.left z.left;y.left.parent y;}//如果删除的为黑节点需要修复平衡if (yOriginalColor BLACK) {
// rbDeleteFixup(t, x);fixAfterDelete(t, x);}}//删除修复算法导论版代码用红黑树解释public void rbDeleteFixup(RedBlackTree t, RBNode x) {while(x ! t.root x.color BLACK) {//x是左孩子if(x x.parent.left) {//w为兄弟节点RBNode w x.parent.right;//w为红色要旋转成黑色方便后续操作if(w.color RED) {w.color BLACK;x.parent.color RED;leftRotate(t, x.parent);//此时w为黑色w x.parent.right;}/** w是黑色w的两个孩子都是黑色* 没办法通过旋转恢复平衡只能把w拉下水设为红色* x变成x的父节点向上递归*/if(w.left.color BLACK w.right.color BLACK) {w.color RED;x x.parent;} else {/** w是黑色w的右孩子是黑色* w的左孩子是红色为RL场景* 此时把w的左孩子设为黑色* w设为红色对w进行右旋* 确保w的右孩子为红色此时为RR场景*/if(w.right.color BLACK) {w.left.color BLACK;w.color RED;rightRotate(t, w);w x.parent.right;}/** 此时一定是w为黑色w的右孩子为红色* w设置为x父节点的颜色* x父节点设为黑色* w的右孩子设置为黑色* 这样w路径上多出来一个黑节点* 对x的父节点进行左旋* 相当于把原来w路径上多出来的黑节点补充到x的路径上* 这样就填补了原来删除的黑节点恢复平衡*/w.color x.parent.color;x.parent.color BLACK;w.right.color BLACK;leftRotate(t, x.parent);/** 这里已经恢复平衡* 所以直接把x设置为根节点结束循环*/x t.root;}} else {//x是右孩子w是兄弟节点RBNode w x.parent.left;//w为红色要旋转成黑色方便后续操作if(w.color RED) {w.color BLACK;x.parent.color RED;rightRotate(t, x.parent);//此时w为黑色w x.parent.right;}/** w是黑色w的两个孩子都是黑色* 没办法通过旋转恢复平衡只能把w拉下水设为红色* x变成x的父节点向上递归*/if(w.right.color BLACK w.left.color BLACK) {w.color RED;x x.parent;} else {/** w是黑色w的左孩子是黑色* w的右孩子是红色为LR场景* 此时把w的右孩子设为黑色* w设为红色对w进行左旋* 确保w的左孩子一定为红色此时为LL场景*/if(w.left.color BLACK) {w.right.color BLACK;w.color RED;leftRotate(t, w);w x.parent.left;}/** 此时一定是w为黑色w的左孩子为红色* w设置为x父节点的颜色* x父节点设为黑色* w的左孩子设置为黑色* 这样w路径上多出来一个黑节点* 对x的父节点进行右旋* 相当于把原来w路径上多出来的黑节点补充到x的路径上* 这样就填补了原来删除的黑节点恢复平衡*/w.color x.parent.color;x.parent.color BLACK;w.left.color BLACK;rightRotate(t, x.parent);/** 这里已经恢复平衡* 所以直接把x设置为根节点结束循环*/x t.root;}}}/** 循环结束要么x是根节点* 要么x是红色节点* 直接把x设置成黑色即可恢复平衡*/x.color BLACK;}/*** 根据2-3-4树解释的红黑树删除* 删除后的调整处理* 1.情况1自己能搞定对应的叶子节点是3节点或者4节点* 2.情况2自己搞不定需要兄弟节点借但是兄弟节点不能直接借找父亲节点借父亲下来然后兄弟节点找一个人代替父亲当家* 3.情况3跟兄弟节点借兄弟也没有* param t,x*/public void fixAfterDelete(RedBlackTree t, RBNode x){while(x ! t.root x.color BLACK){//x是左孩子的情况if(x x.parent.left) {//兄弟节点RBNode w x.parent.right;//判断此时兄弟节点是否是真正的兄弟节点只有黑色节点才是if(w.color RED){w.color BLACK;x.parent.color RED;leftRotate(t, x.parent);//找到真正的兄弟节点w x.parent.right;}//情况三找兄弟借兄弟没得借if(w.left.color BLACK w.right.color BLACK) {//把兄弟拉下水设为红色向上递归w.color RED;x x.parent;}//情况二找兄弟借兄弟有的借else{//确保w的右孩子是红色if(w.right.color BLACK) {w.left.color BLACK;w.color RED;rightRotate(t, w);w x.parent.right;}/** 此时一定是w为黑色w的右孩子为红色* w设置为x父节点的颜色* x父节点设为黑色* w的右孩子设置为黑色* 这样w路径上多出来一个黑节点* 对x的父节点进行左旋* 相当于把原来w路径上多出来的黑节点补充到x的路径上* 这样就填补了原来删除的黑节点恢复平衡*/w.color x.parent.color;x.parent.color BLACK;w.right.color BLACK;leftRotate(t, x.parent);x t.root;}}//x是右孩子的情况else{//兄弟节点RBNode w x.parent.left;//判断此时兄弟节点是否是真正的兄弟节点只有黑色节点才是if(w.color RED) {w.color BLACK;x.parent.color RED;rightRotate(t, x.parent);//此时w为黑色才是真正的兄弟节点w x.parent.right;}//情况三找兄弟借兄弟没得借if(w.left.color BLACK w.right.color BLACK) {//把兄弟拉下水设为红色向上递归w.color RED;x x.parent;}//情况二找兄弟借兄弟有的借else{//确保w的左孩子是红色if(w.left.color BLACK) {w.right.color BLACK;w.color RED;leftRotate(t, w);w x.parent.right;}/** 此时一定是w为黑色w的左孩子为红色* w设置为x父节点的颜色* x父节点设为黑色* w的左孩子设置为黑色* 这样w路径上多出来一个黑节点* 对x的父节点进行右旋* 相当于把原来w路径上多出来的黑节点补充到x的路径上* 这样就填补了原来删除的黑节点恢复平衡*/w.color x.parent.color;x.parent.color BLACK;w.left.color BLACK;rightRotate(t, x.parent);x t.root;}}}//情况一、替代节点是红色则直接染红补偿删除的黑色节点这样红黑树依然保持平衡x.color BLACK;}//红黑树节点类定义static class RBNode {private Integer key; //节点值private RBNode parent; //父节点private RBNode left; //左孩子private RBNode right; //右孩子private boolean color BLACK;public RBNode() {}public RBNode(Integer key) {this.key key;}public RBNode(Integer key, RBNode parent) {this.parent parent;this.color BLACK;this.key key;}public RBNode(RBNode parent, RBNode left, RBNode right, Integer key, boolean color) {this.parent parent;this.left left;this.right right;this.key key;this.color color;}public Integer getKey() {return key;}public void setKey(Integer key) {this.key key;}public RBNode getParent() {return parent;}public void setParent(RBNode parent) {this.parent parent;}public RBNode getLeft() {return left;}public void setLeft(RBNode left) {this.left left;}public RBNode getRight() {return right;}public void setRight(RBNode right) {this.right right;}}Overridepublic Object root() {return root;}Overridepublic Object left(Object RBNode) {return ((RBNode)RBNode).left;}Overridepublic Object right(Object RBNode) {return ((RBNode)RBNode).right;}Overridepublic Object string(Object RBNode) {RBNode myRBNode (RBNode)RBNode;String color myRBNode.color RED ? RED : BLACK;return myRBNode.key ( color );}public static void main(String[] args) {RedBlackTree bst new RedBlackTree();bst.RBInsert(bst, new RBNode(12));bst.RBInsert(bst, new RBNode(5));bst.RBInsert(bst, new RBNode(2));bst.RBInsert(bst, new RBNode(9));bst.RBInsert(bst, new RBNode(18));bst.RBInsert(bst, new RBNode(15));bst.RBInsert(bst, new RBNode(19));bst.RBInsert(bst, new RBNode(17));bst.inorderTreeWalk(bst.root);System.out.println();BinaryTrees.print(bst);bst.rbDelete(bst, bst.treeSearch(bst.root, 12));System.out.println();BinaryTrees.print(bst);}
}
BinaryTreeInfo
package redblacktree;public interface BinaryTreeInfo {/*** who is the root node*/Object root();/*** how to get the left child of the node*/Object left(Object node);/*** how to get the right child of the node*/Object right(Object node);/*** how to print the node*/Object string(Object node);
}
BinaryTrees
package redblacktree;public final class BinaryTrees {private BinaryTrees() {}public static void print(BinaryTreeInfo tree) {print(tree, null);}public static void println(BinaryTreeInfo tree) {println(tree, null);}public static void print(BinaryTreeInfo tree, PrintStyle style) {if (tree null || tree.root() null) return;printer(tree, style).print();}public static void println(BinaryTreeInfo tree, PrintStyle style) {if (tree null || tree.root() null) return;printer(tree, style).println();}public static String printString(BinaryTreeInfo tree) {return printString(tree, null);}public static String printString(BinaryTreeInfo tree, PrintStyle style) {if (tree null || tree.root() null) return null;return printer(tree, style).printString();}private static Printer printer(BinaryTreeInfo tree, PrintStyle style) {if (style PrintStyle.INORDER) return new InorderPrinter(tree);return new LevelOrderPrinter(tree);}public enum PrintStyle {LEVEL_ORDER, INORDER}
}InorderPrinter
package redblacktree;/**┌──800┌──760│ └──600┌──540│ └──476│ └──445┌──410│ └──394
381│ ┌──190│ │ └──146│ ┌──40│ │ └──35└──12└──9*/
public class InorderPrinter extends Printer {private static String rightAppend;private static String leftAppend;private static String blankAppend;private static String lineAppend;static {int length 2;rightAppend ┌ Strings.repeat(─, length);leftAppend └ Strings.repeat(─, length);blankAppend Strings.blank(length 1);lineAppend │ Strings.blank(length);}public InorderPrinter(BinaryTreeInfo tree) {super(tree);}Overridepublic String printString() {StringBuilder string new StringBuilder(printString(tree.root(), , , ));string.deleteCharAt(string.length() - 1);return string.toString();}/*** 生成node节点的字符串* param nodePrefix node那一行的前缀字符串* param leftPrefix node整棵左子树的前缀字符串* param rightPrefix node整棵右子树的前缀字符串* return*/private String printString(Object node,String nodePrefix,String leftPrefix,String rightPrefix) {Object left tree.left(node);Object right tree.right(node);String string tree.string(node).toString();int length string.length();if (length % 2 0) {length--;}length 1;String nodeString ;if (right ! null) {rightPrefix Strings.blank(length);nodeString printString(right, rightPrefix rightAppend, rightPrefix lineAppend, rightPrefix blankAppend);}nodeString nodePrefix string \n;if (left ! null) {leftPrefix Strings.blank(length);nodeString printString(left, leftPrefix leftAppend, leftPrefix blankAppend, leftPrefix lineAppend);}return nodeString;}
}
LevelOrderPrinter
package redblacktree;import java.util.*;/**┌───381────┐│ │
┌─12─┐ ┌─410─┐
│ │ │ │
9 ┌─40─┐ 394 ┌─540─┐│ │ │ │35 ┌─190 ┌─476 ┌─760─┐│ │ │ │146 445 600 800*/
public class LevelOrderPrinter extends Printer {/*** 节点之间允许的最小间距最小只能填1*/private static final int MIN_SPACE 1;private Node root;private int minX;private int maxWidth;private ListListNode nodes;public LevelOrderPrinter(BinaryTreeInfo tree) {super(tree);root new Node(tree.root(), tree);maxWidth root.width;}Overridepublic String printString() {// nodes用来存放所有的节点nodes new ArrayList();fillNodes();cleanNodes();compressNodes();addLineNodes();int rowCount nodes.size();// 构建字符串StringBuilder string new StringBuilder();for (int i 0; i rowCount; i) {if (i ! 0) {string.append(\n);}ListNode rowNodes nodes.get(i);StringBuilder rowSb new StringBuilder();for (Node node : rowNodes) {int leftSpace node.x - rowSb.length() - minX;rowSb.append(Strings.blank(leftSpace));rowSb.append(node.string);}string.append(rowSb);}return string.toString();}/*** 添加一个元素节点*/private Node addNode(ListNode nodes, Object btNode) {Node node null;if (btNode ! null) {node new Node(btNode, tree);maxWidth Math.max(maxWidth, node.width);nodes.add(node);} else {nodes.add(null);}return node;}/*** 以满二叉树的形式填充节点*/private void fillNodes() {// 第一行ListNode firstRowNodes new ArrayList();firstRowNodes.add(root);nodes.add(firstRowNodes);// 其他行while (true) {ListNode preRowNodes nodes.get(nodes.size() - 1);ListNode rowNodes new ArrayList();boolean notNull false;for (Node node : preRowNodes) {if (node null) {rowNodes.add(null);rowNodes.add(null);} else {Node left addNode(rowNodes, tree.left(node.btNode));if (left ! null) {node.left left;left.parent node;notNull true;}Node right addNode(rowNodes, tree.right(node.btNode));if (right ! null) {node.right right;right.parent node;notNull true;}}}// 全是null就退出if (!notNull) break;nodes.add(rowNodes);}}/*** 删除全部null、更新节点的坐标*/private void cleanNodes() {int rowCount nodes.size();if (rowCount 2) return;// 最后一行的节点数量int lastRowNodeCount nodes.get(rowCount - 1).size();// 每个节点之间的间距int nodeSpace maxWidth 2;// 最后一行的长度int lastRowLength lastRowNodeCount * maxWidth nodeSpace * (lastRowNodeCount - 1);// 空集合CollectionObject nullSet Collections.singleton(null);for (int i 0; i rowCount; i) {ListNode rowNodes nodes.get(i);int rowNodeCount rowNodes.size();// 节点左右两边的间距int allSpace lastRowLength - (rowNodeCount - 1) * nodeSpace;int cornerSpace allSpace / rowNodeCount - maxWidth;cornerSpace 1;int rowLength 0;for (int j 0; j rowNodeCount; j) {if (j ! 0) {// 每个节点之间的间距rowLength nodeSpace;}rowLength cornerSpace;Node node rowNodes.get(j);if (node ! null) {// 居中由于奇偶数的问题可能有1个符号的误差int deltaX (maxWidth - node.width) 1;node.x rowLength deltaX;node.y i;}rowLength maxWidth;rowLength cornerSpace;}// 删除所有的nullrowNodes.removeAll(nullSet);}}/*** 压缩空格*/private void compressNodes() {int rowCount nodes.size();if (rowCount 2) return;for (int i rowCount - 2; i 0; i--) {ListNode rowNodes nodes.get(i);for (Node node : rowNodes) {Node left node.left;Node right node.right;if (left null right null) continue;if (left ! null right ! null) {// 让左右节点对称node.balance(left, right);// left和right之间可以挪动的最小间距int leftEmpty node.leftBoundEmptyLength();int rightEmpty node.rightBoundEmptyLength();int empty Math.min(leftEmpty, rightEmpty);empty Math.min(empty, (right.x - left.rightX()) 1);// left、right的子节点之间可以挪动的最小间距int space left.minLevelSpaceToRight(right) - MIN_SPACE;space Math.min(space 1, empty);// left、right往中间挪动if (space 0) {left.translateX(space);right.translateX(-space);}// 继续挪动space left.minLevelSpaceToRight(right) - MIN_SPACE;if (space 1) continue;// 可以继续挪动的间距leftEmpty node.leftBoundEmptyLength();rightEmpty node.rightBoundEmptyLength();if (leftEmpty 1 rightEmpty 1) continue;if (leftEmpty rightEmpty) {left.translateX(Math.min(leftEmpty, space));} else {right.translateX(-Math.min(rightEmpty, space));}} else if (left ! null) {left.translateX(node.leftBoundEmptyLength());} else { // right ! nullright.translateX(-node.rightBoundEmptyLength());}}}}private void addXLineNode(ListNode curRow, Node parent, int x) {Node line new Node(─);line.x x;line.y parent.y;curRow.add(line);}private Node addLineNode(ListNode curRow, ListNode nextRow, Node parent, Node child) {if (child null) return null;Node top null;int topX child.topLineX();if (child parent.left) {top new Node(┌);curRow.add(top);for (int x topX 1; x parent.x; x) {addXLineNode(curRow, parent, x);}} else {for (int x parent.rightX(); x topX; x) {addXLineNode(curRow, parent, x);}top new Node(┐);curRow.add(top);}// 坐标top.x topX;top.y parent.y;child.y parent.y 2;minX Math.min(minX, child.x);// 竖线Node bottom new Node(│);bottom.x topX;bottom.y parent.y 1;nextRow.add(bottom);return top;}private void addLineNodes() {ListListNode newNodes new ArrayList();int rowCount nodes.size();if (rowCount 2) return;minX root.x;for (int i 0; i rowCount; i) {ListNode rowNodes nodes.get(i);if (i rowCount - 1) {newNodes.add(rowNodes);continue;}ListNode newRowNodes new ArrayList();newNodes.add(newRowNodes);ListNode lineNodes new ArrayList();newNodes.add(lineNodes);for (Node node : rowNodes) {addLineNode(newRowNodes, lineNodes, node, node.left);newRowNodes.add(node);addLineNode(newRowNodes, lineNodes, node, node.right);}}nodes.clear();nodes.addAll(newNodes);}private static class Node {/*** 顶部符号距离父节点的最小距离最小能填0*/private static final int TOP_LINE_SPACE 1;Object btNode;Node left;Node right;Node parent;/*** 首字符的位置*/int x;int y;int treeHeight;String string;int width;private void init(String string) {string (string null) ? null : string;string string.isEmpty() ? : string;width string.length();this.string string;}public Node(String string) {init(string);}public Node(Object btNode, BinaryTreeInfo opetaion) {init(opetaion.string(btNode).toString());this.btNode btNode;}/*** 顶部方向字符的X极其重要* * return*/private int topLineX() {// 宽度的一半int delta width;if (delta % 2 0) {delta--;}delta 1;if (parent ! null this parent.left) {return rightX() - 1 - delta;} else {return x delta;}}/*** 右边界的位置rightX 或者 右子节点topLineX的下一个位置极其重要*/private int rightBound() {if (right null) return rightX();return right.topLineX() 1;}/*** 左边界的位置x 或者 左子节点topLineX极其重要*/private int leftBound() {if (left null) return x;return left.topLineX();}/*** x ~ 左边界之间的长度包括左边界字符* * return*/private int leftBoundLength() {return x - leftBound();}/*** rightX ~ 右边界之间的长度包括右边界字符* * return*/private int rightBoundLength() {return rightBound() - rightX();}/*** 左边界可以清空的长度* * return*/private int leftBoundEmptyLength() {return leftBoundLength() - 1 - TOP_LINE_SPACE;}/*** 右边界可以清空的长度* * return*/private int rightBoundEmptyLength() {return rightBoundLength() - 1 - TOP_LINE_SPACE;}/*** 让left和right基于this对称*/private void balance(Node left, Node right) {if (left null || right null) return;// 【left的尾字符】与【this的首字符】之间的间距int deltaLeft x - left.rightX();// 【this的尾字符】与【this的首字符】之间的间距int deltaRight right.x - rightX();int delta Math.max(deltaLeft, deltaRight);int newRightX rightX() delta;right.translateX(newRightX - right.x);int newLeftX x - delta - left.width;left.translateX(newLeftX - left.x);}private int treeHeight(Node node) {if (node null) return 0;if (node.treeHeight ! 0) return node.treeHeight;node.treeHeight 1 Math.max(treeHeight(node.left), treeHeight(node.right));return node.treeHeight;}/*** 和右节点之间的最小层级距离*/private int minLevelSpaceToRight(Node right) {int thisHeight treeHeight(this);int rightHeight treeHeight(right);int minSpace Integer.MAX_VALUE;for (int i 0; i thisHeight i rightHeight; i) {int space right.levelInfo(i).leftX - this.levelInfo(i).rightX;minSpace Math.min(minSpace, space);}return minSpace;}private LevelInfo levelInfo(int level) {if (level 0) return null;int levelY y level;if (level treeHeight(this)) return null;ListNode list new ArrayList();QueueNode queue new LinkedList();queue.offer(this);// 层序遍历找出第level行的所有节点while (!queue.isEmpty()) {Node node queue.poll();if (levelY node.y) {list.add(node);} else if (node.y levelY) break;if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}Node left list.get(0);Node right list.get(list.size() - 1);return new LevelInfo(left, right);}/*** 尾字符的下一个位置*/public int rightX() {return x width;}public void translateX(int deltaX) {if (deltaX 0) return;x deltaX;// 如果是LineNodeif (btNode null) return;if (left ! null) {left.translateX(deltaX);}if (right ! null) {right.translateX(deltaX);}}}private static class LevelInfo {int leftX;int rightX;public LevelInfo(Node left, Node right) {this.leftX left.leftBound();this.rightX right.rightBound();}}
}
Printer
package redblacktree;public abstract class Printer {/*** 二叉树的基本信息*/protected BinaryTreeInfo tree;public Printer(BinaryTreeInfo tree) {this.tree tree;}/*** 生成打印的字符串*/public abstract String printString();/*** 打印后换行*/public void println() {print();System.out.println();}/*** 打印*/public void print() {System.out.print(printString());}
}
Strings
package redblacktree;public class Strings {public static String repeat(String string, int count) {if (string null) return null;StringBuilder builder new StringBuilder();while (count-- 0) {builder.append(string);}return builder.toString();}public static String blank(int length) {if (length 0) return null;if (length 0) return ;return String.format(% length s, );}
}
总结
这个实现过程比较复杂更多的是在提现一个打印结果的实现没有必要自己去手敲可以全部拿下来去运行看具体核心实现红黑树对应的那些功能。对于红黑树更细节的去使用我也还在探索中之后会更加细节的去记录。
ps:计划每日更新一篇博客今日2023-05-04日更第十八天。 昨日更新 B树B-tree、B-树理论详解
