自己做网站投放有流量么,eclipse网站开发例子,ps制作博客网站界面,seo关键词推广多少钱文章目录 前言什么是红黑树红黑树的性质红黑树结点的定义红黑树的插入情况一情况二情况三插入代码总结 验证是否为红黑树红黑树的删除 前言
前面我们学习了 AVL 树——高度平衡的二叉搜索树#xff0c;AVL 树保证了结点的左右子树的高度差的绝对值不超过 1#xff0c;也就是… 文章目录 前言什么是红黑树红黑树的性质红黑树结点的定义红黑树的插入情况一情况二情况三插入代码总结 验证是否为红黑树红黑树的删除 前言
前面我们学习了 AVL 树——高度平衡的二叉搜索树AVL 树保证了结点的左右子树的高度差的绝对值不超过 1也就是结点的左右子树的高度是绝对平衡的虽然这种结构的查询速度非常的快但是因为它要保证左右子树的绝对平衡所以对 AVL 树进行增加或者删除操作的时候就需要进行多次旋转而对树进行旋转也是需要时间的所以 AVL 树只适合存储一些静态的不经常变化的数据。那么要想保证查询速度也要对数据进行增加和删除操作的话就需要使用另一个数据结构——红黑树。
什么是红黑树
红黑树是一种二叉搜索树但在每个节点上增加了一个存储位表示节点的颜色可以是 Red 或者 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是接近平衡的。 红黑树的性质
为了保证红黑树的查找速率以及增加和删除的速度红黑树具有以下性质
从根节点到叶子节点的路径中最长路径最多是最短路径的二倍每个节点不是红色就是黑色根节点是黑色的如果一个节点是红色的则如果它的两个孩子节点是黑色的一条路径上不存在两个连续的红色节点对于每个节点从该结点到其所有后代节点的简单路径上均包含相同数目的黑色节点黑色节点的数量包括 NULL 节点每个叶子节点都是黑色的此处的叶子结点指的是空结点
这里对一些性质进行演示
为什么从根节点到叶子节点的路径中最长路径最多是最短路径的二倍
这个性质是通过性质4、5得来的
红黑树结点的定义
首先通过一个枚举类来表示颜色
public enum COLOR {RED, BLACK;
}红黑树节点的定义
class RBTreeNode {public RBTreeNode left;public RBTreeNode right;public RBTreeNode parent;public rbtree.COLOR color rbtree.COLOR.RED; //结点的颜色public int val;public RBTreeNode(int val) {this.val val;this.color COLOR.RED;}
}在这里我们将节点的颜色默认设置为了红色这是为什么呢 因为红黑树的性质从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。将节点默认设置为红色插入时不会违反红黑树的性质因为红色的节点不会影响路径上黑色节点的数量。而如果默认颜色设置为黑色每次插入新节点都可能违反红黑树的性质需要频繁调整树的结构导致效率降低。因此将红黑树的结点默认颜色设置为红色是为了保持树的平衡提高插入操作的效率。 红黑树的插入
因为红黑树也是属于特殊的二叉搜索树所以在插入数据的时候还是按照二叉搜索树插入的做法一样当数据插入之后我们需要做的就是检测新节点插入之后红黑树的性质是否被破坏。
这里的破坏性质通常是指因为新插入的节点的颜色默认是红色如果新插入的节点的双亲节点的颜色是黑色的话就没有破坏红黑树的性质不需要做出修改而如果插入的节点的双亲结点也是红色的话就不符合红黑树的性质——红色结点的左右孩子节点的颜色都是黑色在一条路径中不存在两个连续的红色节点此时就需要对红黑树的结构进行修改。
这里我们将插入节点后需要调整红黑树结构的情况给列举出来
这里我们约定cur 节点为当前节点p为父节点g为祖父节点u为叔叔节点
情况一
当 cur 为红色p 为红色g 为黑色u 存在且为红色 这里 cur 是新插入的节点插入之后 p 为红色cur 为红色一条路径上存在两个连续的红色节点此时就需要对红黑树的结构进行调整。这种情况还是比较容易解决的这种情况我们需要将 p 和 u 都改为黑色并且为了保证路径上黑色节点的数量不变还需要将 g 节点的颜色改为 RED这样就没有破坏红黑树的性质。 修改 p、u 和 g 的颜色之后还没有结束因为红黑树的性质中还有一条性质就是根节点的颜色必须为黑色所以我们在进行上面的操作了之后不管根节点为啥颜色都需要进行 root.color COLOR.BLACK 的操作。
通过代码体现就是这样
while (parent ! null parent.color COLOR.RED) {RBTreeNode grandfather parent.parent; //grandfather不可能为null因为如果parent为红色那么就一定存在父亲节点因为红黑树的根节点是黑色RBTreeNode uncle null;if (grandfather.left parent) {uncle grandfather.right;}else {uncle grandfather.left;}if (uncle ! null uncle.color COLOR.RED) {//情况一parent.color COLOR.BLACK;uncle.color COLOR.BLACK;grandfather.color COLOR.RED;//当grandfather的节点颜色变为了红色之后可能又会破坏其他树的结构所以需要继续向上调整cur grandfather;parent cur.parent;}
}
root.color COLOR.BLACK; //将根节点的颜色修改为黑色情况二
当 cur 为红色p 为红色g 为黑色u 不存在或者 u 存在且为黑色
这种情况往往不是刚插入时候造成的而是因为在调整的过程中出现的 所以这种情况只可能在向上调整的过程中才会出现 对于这种情况的解决方式就是对 g 的左右子树进行右旋操作之后将 p 的颜色改为黑色g 的颜色改为红色 这是 u 不存在的情况 同样的这里是右旋将上面的情况进行镜像处理就需要进行左旋操作了 所以当 cur 为红色p 为红色g 为黑色。u不存在或者 u 存在且颜色为黑色的做法就可以总结为
当 p 为 g 的左孩子cur 为 p 的左孩子的时候
1将 g 节点的左右子树进行右旋操作2将 g 节点的颜色修改为红色p 节点的颜色修改为黑色
当 p 为 g 的右孩子cur 为 p 的右孩子的时候
1将 g 节点的左右子树进行左旋操作2 将 g 节点的颜色修改为红色p 节点的颜色修改为黑色
通过代码体现就是这样
while (parent ! null parent.color COLOR.RED) {RBTreeNode grandfather parent.parent; //grandfather不可能为null因为如果parent为红色那么就一定存在父亲节点因为红黑树的根节点是黑色RBTreeNode uncle null;if (grandfather.left parent) {uncle grandfather.right;if (uncle ! null uncle.color COLOR.RED) {//情况一parent.color COLOR.BLACK;uncle.color COLOR.BLACK;grandfather.color COLOR.RED;//当grandfather的节点颜色变为了红色之后可能又会破坏其他树的结构所以需要继续向上调整cur grandfather;parent cur.parent;}else {//else 就表示uncle为空或者uncle不为空且uncle颜色为黑色的情况if (cur parent.left) {rotateRight(grandfather);grandfather.color COLOR.RED;parent.color COLOR.BLACK;}}}else {uncle grandfather.left;if (uncle ! null uncle.color COLOR.RED) {//情况一parent.color COLOR.BLACK;uncle.color COLOR.BLACK;grandfather.color COLOR.RED;//当grandfather的节点颜色变为了红色之后可能又会破坏其他树的结构所以需要继续向上调整cur grandfather;parent cur.parent;}else {//else 就表示uncle为空或者uncle不为空且uncle颜色为黑色的情况if (cur parent.right) {rotateLeft(grandfather);grandfather.color COLOR.RED;parent.color COLOR.BLACK;}}}
}
root.color COLOR.BLACK;
return true;右旋操作
public void rotateRight(RBTreeNode parent) {RBTreeNode subL parent.left;RBTreeNode subLR subL.right;parent.left subLR;if (subLR ! null) {subLR.parent parent;}RBTreeNode pParent parent.parent;if (root parent) {root subL;subL.parent null;}else {if (pParent.left parent) {pParent.left subLR;}else {pParent.right subLR;}subLR.parent pParent;}subL.right parent;parent.parent subL;
}左旋操作
public void rotateLeft(RBTreeNode parent) {RBTreeNode subR parent.right;RBTreeNode subRL subR.left;RBTreeNode pParent parent.parent;parent.right subRL;if (subRL ! null) {subRL.parent parent;}if (root parent) {root subR;root.parent pParent;}else {if (pParent.left parent) {pParent.left subR;else {pParent.right subR;}subR.parent pParent;}subR.left parent;parent.parent subR;
}情况三
第三种情况还是 cur 为红色p 为红色g 为黑色u 不存在或者 u 存在且为黑色但是呢这种情况不是和第二种情况一样p 位于 g 的左侧cur 位于 p 的左侧、p 位于 g 的右侧cur 位于 p 的右侧这种相同方向的情况而是 p 位于 g 的左侧cur 位于 p 的右侧、p 位于 g 的右侧cur 位于 g 的左侧 同样这种情况也是在调整的过程中才会出现的 当出现这种情况的时候通过右旋 g 节点的左右子树然后修改 p 和 g 的颜色是无法解决的 当出现这种情况的时候需要先对 p 节点的左右子树进行左旋操作 对 p 的左右子树进行左旋操作之后就变成了第二类情况接下来对 g 的左右子树进行右旋操作之后将 g 节点的颜色修改为红色、p 节点的颜色修改为黑色就可以达到目的了。
这是当 p 为 g 的左子树cur 为 p 的右子树的情况对于 p 为 g 的右子树cur 为 p 的左子树的解决方法是类似的 通过代码展示就是这样的
当 p 为 g 的左子树cur 为 p 的右子树
rotateLeft(parent);
RBTreeNode tmp parent;
parent cur;
cur tmp;
rotateRight(grandfather);
grandfather.color COLOR.RED;
parent.color COLOR.BLACK;当 p 为 g 的右子树cur 为 p 的左子树
rotateRight(parent);
RBTreeNode tmp parent;
parent cur;
cur tmp;
rotateLeft(grandfather);
grandfather.color COLOR.RED;
parent.color COLOR.BLACK;插入代码总结
public class RBTree {class RBTreeNode {public RBTreeNode left;public RBTreeNode right;public RBTreeNode parent;public rbtree.COLOR color; //结点的颜色public int val;public RBTreeNode(int val) {this.val val;this.color COLOR.RED;}}private RBTreeNode root;public boolean insert(int data) {RBTreeNode node new RBTreeNode(data);if (root null) {root node;node.color COLOR.BLACK;return true;}RBTreeNode cur root, parent null; //parent节点记录cur节点的双亲节点while (cur ! null) {if (cur.val data) {parent cur;cur cur.right;}else if (cur.val data) {parent cur;cur cur.left;}else {return false; //二叉搜索树中不存在重复的元素}}if (data parent.val) {parent.right node;}else {parent.left node;}node.parent parent;cur node;while (parent ! null parent.color COLOR.RED) {RBTreeNode grandfather parent.parent; //grandfather不可能为null因为如果parent为红色那么就一定存在父亲节点因为红黑树的根节点是黑色RBTreeNode uncle null;if (grandfather.left parent) {uncle grandfather.right;if (uncle ! null uncle.color COLOR.RED) {//情况一parent.color COLOR.BLACK;uncle.color COLOR.BLACK;grandfather.color COLOR.RED;//当grandfather的节点颜色变为了红色之后可能又会破坏其他树的结构所以需要继续向上调整cur grandfather;parent cur.parent;}else {//else 就表示uncle为空或者uncle不为空且uncle颜色为黑色的情况if (cur parent.right) {rotateLeft(parent);RBTreeNode tmp parent;parent cur;cur tmp;}rotateRight(grandfather);grandfather.color COLOR.RED;parent.color COLOR.BLACK;}}else {uncle grandfather.left;if (uncle ! null uncle.color COLOR.RED) {//情况一parent.color COLOR.BLACK;uncle.color COLOR.BLACK;grandfather.color COLOR.RED;//当grandfather的节点颜色变为了红色之后可能又会破坏其他树的结构所以需要继续向上调整cur grandfather;parent cur.parent;}else {//else 就表示uncle为空或者uncle不为空且uncle颜色为黑色的情况if (cur parent.left) {rotateRight(parent);RBTreeNode tmp parent;parent cur;cur tmp;}rotateLeft(grandfather);grandfather.color COLOR.RED;parent.color COLOR.BLACK;}}}root.color COLOR.BLACK;return true;}public void rotateRight(RBTreeNode parent) {RBTreeNode subL parent.left;RBTreeNode subLR subL.right;parent.left subLR;if (subLR ! null) {subLR.parent parent;}RBTreeNode pParent parent.parent;if (root parent) {root subL;subL.parent null;}else {if (pParent.left parent) {pParent.left subLR;}else {pParent.right subLR;}subLR.parent pParent;}subL.right parent;parent.parent subL;}public void rotateLeft(RBTreeNode parent) {RBTreeNode subR parent.right;RBTreeNode subRL subR.left;RBTreeNode pParent parent.parent;parent.right subRL;if (subRL ! null) {subRL.parent parent;}if (root parent) {root subR;root.parent pParent;}else {if (pParent.left parent) {pParent.left subR;}else {pParent.right subR;}subR.parent pParent;}subR.left parent;parent.parent subR;}
}
验证是否为红黑树
验证是否为红黑树首先需要验证是否为二叉搜索树然后验证每个路径上的黑色节点的数量是否相等还需要验证在一条路径中是否存在两个连续的红色节点
检验是否为二叉搜索树
private int prev Integer.MIN_VALUE;public boolean isBinarySearchTree(RBTreeNode root) {if (root null) return true;boolean l isBinarySearchTree(root.left);if (!l) return false;if (prev root.val) {prev root.val;return isBinarySearchTree(root.right);}else return false;
}校验所有路径中的黑色节点的数量是否相等
//先计算出红黑树中其中一条路径中黑色节点的数量
public int blackNum(RBTreeNode root) {if (root null) return 0;int count 0;RBTreeNode cur root;if (root.left ! null) {while (cur ! null) {if (cur.color COLOR.BLACK) count;cur cur.left;}}else if (root.right ! null){while (cur ! null) {if (cur.color COLOR.BLACK) count;cur cur.right;}}else {count root.color COLOR.BLACK ? 1 : 0;}return count;
}//根据传入的路径中黑色节点的数量判断是否所有路径上的黑色节点的数量相同
public boolean checkBlackNum(RBTreeNode root, int pathBlackNum, int blackNum) {if (root null) return true;if (root.color COLOR.BLACK) pathBlackNum;if (root.left null root.right null) {if (pathBlackNum blackNum) return true;else return false;}return checkBlackNum(root.left, pathBlackNum, blackNum) checkBlackNum(root.right, pathBlackNum, blackNum);
}判断一条路径上是否存在两个连续的红色节点
public boolean checkRedColor(RBTreeNode root) {if (root null) return true;if (root.color COLOR.RED) {if (root.left ! null root.left.color COLOR.RED) return false;if (root.right ! null root.right.color COLOR.RED) return false;}return checkRedColor(root.left) checkRedColor(root.right);
}整理接口
public boolean checkRBTree(RBTreeNode root) {int blackNum blackNum(root);return isBinarySearchTree(root) checkBlackNum(root,0,blackNum) checkRedColor(root);
}红黑树的删除
红黑树的删除操作主要涉及以下几个步骤
定位节点找到要删除的节点。如果要删除的节点有两个子节点则需要找到该节点的后继节点通常是右子树中的最小节点来替代要删除的节点。执行删除执行标准的二叉搜索树BST的删除操作。这涉及到将后继节点的值复制到当前节点并删除后继节点。如果后继节点有子节点这些子节点将被转移到被删除节点的位置。修复红黑树性质删除节点后可能会破坏红黑树的性质。因此需要通过一系列的旋转和颜色更改操作来修复这些性质。这些操作包括左旋、右旋以及重新着色节点以确保满足红黑树的五大特征。处理特殊情况在删除操作中可能会遇到一些特殊情况例如要删除的节点是黑色且拥有两个红色子节点或者要删除的节点是根节点等。这些情况需要特殊的处理方式来确保红黑树的性质得到维护。
这里我就不为大家详细介绍了大家下去可以自己了解了解。
