一个做礼品的网站,做一个直播app软件要多少钱,工程公司名称大全集最新免费,建跨境电商网站多少钱红黑树插入时的自平衡
红黑树实质上是一棵自平衡的二叉查找树#xff0c;引入带颜色的节点也是为了方便在进行插入或删除操作时#xff0c;如果破坏了二叉查找树的平衡性能通过一系列变换保持平衡。
红黑树的性质
每个节点要么是红色#xff0c;要么是黑色根节点必须是黑…红黑树插入时的自平衡
红黑树实质上是一棵自平衡的二叉查找树引入带颜色的节点也是为了方便在进行插入或删除操作时如果破坏了二叉查找树的平衡性能通过一系列变换保持平衡。
红黑树的性质
每个节点要么是红色要么是黑色根节点必须是黑色两个红色节点不能相连从根节点出发到达任意叶子节点经过的黑色节点个数相同
红黑树的数据结构
红黑树实质上是一颗二叉查找树左子树的值小于根节点的值右子树的值大于根节点的值。 public class RedBlackTree {private static int BLACK 1;private static final int RED 0;private static Node root;private static class Node {private int color RED;private int data;private Node left;private Node right;private Node parent;Node(int data) {this.data data;}}
}红黑树的插入
插入的节点默认是红色的要不然全是黑色节点它也满足红黑树的定义不过就没意义了
由于红黑树是一颗二叉查找树所以它的插入可以使用递归先不考虑破坏红黑树的结构 /*** 通过递归往红黑树中插入一个新节点* param root 要插入的树的根节点* param data 新节点的值*/private void insert(Node root, int data) {if(root.data data) {if(root.left null) {Node node new Node(data);root.left node;node.parent root;} else {insert(root.left, data);}}else {if(root.right null) {Node node new Node(data);root.right node;node.parent root;} else {insert(root.right, data);}}}调整结构
新插入节点后可能破坏红黑树的定义虽然红黑树的定义有四条前两条都是确定了的不会因为新添加节点而被破坏只需要关注第三条就可以了满足前三条第四条就会自然满足 /*** 判断插入新节点后红黑树结构是否需要变化* 根据红黑树的定义两个红色节点不能连接* param root 插入的新节点* return 返回true表示插入新节点后破坏了红黑树的结构* 需要通过旋转变色来纠正否则不需要修改。*/private boolean checkStruct(Node root) {return root.color RED root.parent.color RED;}所以只要新插入的节点的父节点是红色就需要调整结构。调整结构的办法有三种
1. 变色
就是把红色变为黑色黑色变为红色
2. 左旋 以节点C为轴左旋的步骤
将C的父节点A沉下来C升上去作为新的父节点将原来C的左子树挂到A的右子树上其他不变 /*** 左旋* - 旋转前的右子节点变成旋转后的父节点* - 旋转前的父节点轴变为旋转后父节点的左子节点* - 旋转前轴的右子节点的右子节点旋转后变为轴的右子节点* - 旋转前右子节点的左子树变成旋转后左子节点的右子树* - 其他不变* param node 以该节点为轴旋转*/private static void leftSpin(Node node) {Node nextFather node.right;nextFather.parent node.parent;node.right node.right.left;nextFather.left node;connectParent(node, nextFather);}3. 右旋
右旋和左旋正好相反 以B为轴右旋的步骤
将B的父节点A沉下来B升上去作为新的父节点将原来B的右子树接到新的A的左子树的位置 /*** 将变换后的树和它上面的节点连接* param node 变换前的轴* param nextFather 变换后的子树*/private static void connectParent(Node node, Node nextFather) {// 如果变换的是根节点就把root赋值成变换后的节点if(node.parent ! null) {if(node.parent.data node.data) {node.parent.left nextFather;} else {node.parent.right nextFather;}} else {RedBlackTree.root nextFather;}node.parent nextFather;} /*** 右旋* - 旋转前的左子节点变成旋转后的父节点* - 旋转前左子节点的右子树变成旋转后右子节点的左子树* param node 旋转轴。*/private static void rightSpin(Node node) {Node nextFather node.left;nextFather.parent node.parent;node.left node.left.right;nextFather.right node;connectParent(node, nextFather);}根据新插入节点位置的不同情况节点调整有五种不同的方案
1. 父节点和叔叔节点均为红色
如果新插入节点的父节点和叔叔节点都是红色只需要将父节点和叔叔节点变为黑色祖父节点变为红色即可。 如果祖父节点是根节点祖父节点保持黑色。
ONLY_CHANGE_COLOR {/*** 适用于* - 父节点和叔叔节点都为红色的情况* 具体方法* - 把父节点和叔叔节点的颜色变为黑色* - 爷爷节点的颜色变为红色* - 如果爷爷节点为根节点爷爷节点颜色恢复黑色* param node 当前新修改的节点*/Overridepublic void way(Node node) {node.parent.parent.left.color BLACK;node.parent.parent.right.color BLACK;if(node.parent.parent.parent ! null){node.parent.parent.color RED;}}},2. 叔叔节点不存在或为黑色父节点位于祖父节点的左子树 2.1 当前节点位于左子树
调整办法
将父节点设置为黑色经祖父节点设置为红色对祖父节点进行右旋 RIGHT_SPIN_CHANGE_COLOR {/*** 适用于* - 无叔叔节点或叔叔节点为黑色* - 父节点位于祖父节点的左子树* - 新节点位于父节点左子树的情况* 具体方法* - 将当前节点的父节点设置为黑色* - 将当前节点的祖父节点设置为红色* - 对祖父节点进行右旋* param node 当前节点*/Overridepublic void way(Node node) {node.parent.color BLACK;node.parent.parent.color RED;Solution.rightSpin(node.parent.parent);}},2.2 当前节点位于右子树
如果当前节点位于右子树需要先对它的父节点进行左旋得到2.1的情况再按2.1进行变换 LEFT_SPIN_WITH_RIGHT_SPIN {/*** 适用于* - 无叔叔节点或叔叔节点为黑色* - 父节点位于祖父节点的左子树* - 新节点位于父节点右子树的情况* 具体方法* - 对当前节点的父节点进行左旋* - 执行 RIGHT_SPIN_CHANGE_COLOR* param node 当前节点*/Overridepublic void way(Node node) {Solution.leftSpin(node.parent);RIGHT_SPIN_CHANGE_COLOR.way(node.left);}},3.叔叔节点不存在或为黑色父节点在祖父节点的右子树
与上面的情况正好相反 3.1 当前节点位于父节点的右子树上
调整步骤
将父节点变为黑色将祖父节点变为红色对祖父节点左旋 LEFT_SPIN_CHANGE_COLOR {/*** 适用于* - 无叔叔节点或叔叔节点为黑色* - 父节点位于祖父节点的右子树* - 新节点位于父节点右子树的情况* 具体方法* - 将当前节点的父节点设置为黑色* - 将当前节点的祖父节点设置为红色* - 对祖父节点进行左旋* param node 当前节点*/Overridepublic void way(Node node) {node.parent.color BLACK;node.parent.parent.color RED;Solution.leftSpin(node.parent.parent);}},3.2 当前节点位于左子树
调整步骤
对当前节点的父节点进行右旋执行3.1的步骤 RIGHT_SPIN_LEFT_SPIN {/*** 适用于* - 无叔叔节点或叔叔节点为黑色* - 父节点位于祖父节点的右子树* - 新节点位于父节点左子树的情况* 具体方法* - 对当前节点的父节点进行右旋* - 执行 LEFT_SPIN_CHANGE_COLOR* param node 当前节点*/Overridepublic void way(Node node) {Solution.rightSpin(node.parent);LEFT_SPIN_CHANGE_COLOR.way(node.right);}},完整代码
package Note.cistern;public class RedBlackTree {private static int BLACK 1;private static final int RED 0;private static Node root;private static class Node {private int color RED;private int data;private Node left;private Node right;private Node parent;Node(int data) {this.data data;}Overridepublic String toString() {return Node{ data data , color color , left left , right right };}}interface SolutionInterface {void way(Node node);}enum Solution implements SolutionInterface{ONLY_CHANGE_COLOR {/*** 适用于* - 父节点和叔叔节点都为红色的情况* 具体方法* - 把父节点和叔叔节点的颜色变为黑色* - 爷爷节点的颜色变为红色* - 如果爷爷节点为根节点爷爷节点颜色恢复黑色* param node 当前新修改的节点*/Overridepublic void way(Node node) {node.parent.parent.left.color BLACK;node.parent.parent.right.color BLACK;if(node.parent.parent.parent ! null){node.parent.parent.color RED;}}},RIGHT_SPIN_LEFT_SPIN {/*** 适用于* - 无叔叔节点或叔叔节点为黑色* - 父节点位于祖父节点的右子树* - 新节点位于父节点左子树的情况* 具体方法* - 对当前节点的父节点进行右旋* - 执行 LEFT_SPIN_CHANGE_COLOR* param node 当前节点*/Overridepublic void way(Node node) {Solution.rightSpin(node.parent);LEFT_SPIN_CHANGE_COLOR.way(node.right);}},LEFT_SPIN_CHANGE_COLOR {/*** 适用于* - 无叔叔节点或叔叔节点为黑色* - 父节点位于祖父节点的右子树* - 新节点位于父节点右子树的情况* 具体方法* - 将当前节点的父节点设置为黑色* - 将当前节点的祖父节点设置为红色* - 对祖父节点进行左旋* param node 当前节点*/Overridepublic void way(Node node) {node.parent.color BLACK;node.parent.parent.color RED;Solution.leftSpin(node.parent.parent);}},LEFT_SPIN_WITH_RIGHT_SPIN {/*** 适用于* - 无叔叔节点或叔叔节点为黑色* - 父节点位于祖父节点的左子树* - 新节点位于父节点右子树的情况* 具体方法* - 对当前节点的父节点进行左旋* - 执行 RIGHT_SPIN_CHANGE_COLOR* param node 当前节点*/Overridepublic void way(Node node) {Solution.leftSpin(node.parent);RIGHT_SPIN_CHANGE_COLOR.way(node.left);}},RIGHT_SPIN_CHANGE_COLOR {/*** 适用于* - 无叔叔节点或叔叔节点为黑色* - 父节点位于祖父节点的左子树* - 新节点位于父节点左子树的情况* 具体方法* - 将当前节点的父节点设置为黑色* - 将当前节点的祖父节点设置为红色* - 对祖父节点进行右旋* param node 当前节点*/Overridepublic void way(Node node) {node.parent.color BLACK;node.parent.parent.color RED;Solution.rightSpin(node.parent.parent);}},PASS {/*** 异常情况* param node 当前节点*/Overridepublic void way(Node node) {}};/*** 左旋* - 旋转前的右子节点变成旋转后的父节点* - 旋转前的父节点轴变为旋转后父节点的左子节点* - 旋转前轴的右子节点的右子节点旋转后变为轴的右子节点* - 旋转前右子节点的左子树变成旋转后左子节点的右子树* - 其他不变* param node 以该节点为轴旋转*/private static void leftSpin(Node node) {Node nextFather node.right;nextFather.parent node.parent;node.right node.right.left;nextFather.left node;connectParent(node, nextFather);}/*** 将变换后的树和它上面的节点连接* param node 变换前的轴* param nextFather 变换后的子树*/private static void connectParent(Node node, Node nextFather) {// 如果变换的是根节点就把root赋值成变换后的节点if(node.parent ! null) {if(node.parent.data node.data) {node.parent.left nextFather;} else {node.parent.right nextFather;}} else {RedBlackTree.root nextFather;}node.parent nextFather;}/*** 右旋* - 旋转前的左子节点变成旋转后的父节点* - 旋转前左子节点的右子树变成旋转后右子节点的左子树* param node 旋转轴。*/private static void rightSpin(Node node) {Node nextFather node.left;nextFather.parent node.parent;node.left node.left.right;nextFather.right node;connectParent(node, nextFather);}}public RedBlackTree(int rootData){root new Node(rootData);root.color BLACK;}/*** 通过一个整形数组快速构建红黑树* param data 要创建树的元素*/public RedBlackTree(int [] data) {assert data.length 1: data的长度至少为1;root new Node(data[0]);root.color BLACK;for (int i 1; i data.length; i) {this.append(data[i]);}}/*** 判断插入新节点后红黑树结构是否需要变化* 根据红黑树的定义两个红色节点不能连接* param root 插入的新节点* return 返回true表示插入新节点后破坏了红黑树的结构* 需要通过旋转变色来纠正否则不需要修改。*/private boolean checkStruct(Node root) {return root.color RED root.parent.color RED;}/*** 确定该以哪种方式变换当前树使之满足红黑树的条件* param node 当前新加入的使红黑树结构错误的节点* return 返回解决办法*/private Solution determineSolution(Node node) {int fatherColor node.parent.color;int uncleColor;// 如果父亲是爷爷的右子树if(node.parent.data node.parent.parent.data){uncleColor node.parent.parent.left null? BLACK: node.parent.parent.left.color;if(fatherColor RED uncleColor BLACK){if(node.data node.parent.data){return Solution.RIGHT_SPIN_LEFT_SPIN;} else {return Solution.LEFT_SPIN_CHANGE_COLOR;}}} else {uncleColor node.parent.parent.right null? BLACK: node.parent.parent.right.color;if(fatherColor RED uncleColor BLACK){// 插入的节点是父节点的左子节点if(node.data node.parent.data){return Solution.RIGHT_SPIN_CHANGE_COLOR;} else {return Solution.LEFT_SPIN_WITH_RIGHT_SPIN;}}}// 如果父节点和叔叔节点都是红色if(fatherColor RED uncleColor RED){return Solution.ONLY_CHANGE_COLOR;}return Solution.PASS;}private void changeTree(Node node) {Solution solution determineSolution(node);solution.way(node);if(node.parent ! null node.parent.parent ! null checkStruct(node.parent.parent)) {changeTree(node.parent.parent);}}/*** 通过递归往红黑树中插入一个新节点* param root 要插入的树的根节点* param data 新节点的值*/private void insert(Node root, int data) {if(root.data data) {if(root.left null) {Node node new Node(data);root.left node;node.parent root;if(checkStruct(node)) {changeTree(node);}} else {insert(root.left, data);}}else {if(root.right null) {Node node new Node(data);root.right node;node.parent root;if(checkStruct(node)) {changeTree(node);}} else {insert(root.right, data);}}}public Node append(int data) {insert(root, data);return root;}public Node append(int[] data) {for (int datum : data) {append(datum);}return root;}public Node getRoot(){return root;}public static void main(String[] args) {int[] data {16, 8, 11, 13, 15, 17, 22, 25, 27};RedBlackTree redBlackTree new RedBlackTree(data);System.out.println(redBlackTree.getRoot());}}
