大连网站排名优化价格,浙江杭州下沙做网站,网站建设工作室介绍范文,商城平台开发公司文章目录 红黑树红黑树介绍红黑树的五个基本性质红黑树的平衡原理红黑树的操作红黑树的操作 代码实现节点实现插入和查询操作 红黑树
红黑树介绍 红黑树#xff08;Red-Black Tree#xff09;是一种自平衡的二叉查找树#xff08;Binary Search Tree, BST#xff09;… 文章目录 红黑树红黑树介绍红黑树的五个基本性质红黑树的平衡原理红黑树的操作红黑树的操作 代码实现节点实现插入和查询操作 红黑树
红黑树介绍 红黑树Red-Black Tree是一种自平衡的二叉查找树Binary Search Tree, BST它在普通二叉查找树的基础上增加了一些额外的约束条件以确保树的平衡性从而保证在最坏情况下插入、删除和查找操作的时间复杂度为 O(logn)。
红黑树的五个基本性质
红黑树是一种特殊的二叉查找树它满足以下五个基本性质 1.节点是红色或黑色每个节点都有一个颜色属性红色或黑色。 2.根节点必须是黑色 3.叶子节点即空节点或 null是黑色。 4.如果一个节点是红色则它的两个子节点都是黑色。换句话说红色节点不能连续出现。 5.从任意节点到其每个叶子节点的所有路径上黑色节点的数量相同。这一性质确保了树的平衡性。
红黑树的平衡原理
红黑树通过上述性质来保证树的平衡。虽然红黑树不是完全平衡的二叉树但它能够保证最长路径和最短路径的长度不会相差太大。具体来说红黑树的最长路径不会超过最短路径的两倍从而保证了树的近似平衡。
红黑树的操作
红黑树的主要操作包括插入、删除和查找。这些操作在普通二叉查找树的基础上增加了颜色调整和旋转操作以确保树的平衡。
红黑树的操作
红黑树的主要操作包括插入、删除和查找。这些操作在普通二叉查找树的基础上增加了颜色调整和旋转操作以确保树的平衡。 插入操作 插入新节点将新节点插入到树中新节点默认为红色。 修复树的性质插入后可能违反红黑树的性质需要通过以下操作修复 颜色翻转改变节点的颜色。 旋转操作包括左旋和右旋调整树的结构。 删除操作 删除节点删除目标节点。 修复树的性质删除后可能违反红黑树的性质需要通过以下操作修复 颜色调整改变节点的颜色。 旋转操作调整树的结构。 查找操作 查找操作与普通二叉查找树相同从根节点开始根据键值的大小关系逐层向下查找直到找到目标节点或到达叶子节点。
代码实现
节点实现
class NodeK extends ComparableK, V {K key;V value;NodeK, V left, right, parent;boolean color; // true 表示红色false 表示黑色public Node(K key, V value) {this.key key;this.value value;this.color true; // 新节点默认为红色}
}插入和查询操作
public class RedBlackTreeK extends ComparableK, V {private NodeK, V root;// 插入操作public void insert(K key, V value) {root insert(root, key, value);root.color false; // 根节点必须是黑色}private NodeK, V insert(NodeK, V node, K key, V value) {if (node null) {return new Node(key, value);}if (key.compareTo(node.key) 0) {node.left insert(node.left, key, value);node.left.parent node;} else if (key.compareTo(node.key) 0) {node.right insert(node.right, key, value);node.right.parent node;} else {node.value value; // 如果键已存在更新值}// 修复红黑树性质return fixAfterInsertion(node);}// 修复插入后的红黑树性质private NodeK, V fixAfterInsertion(NodeK, V node) {while (node ! null node ! root node.parent.color) {if (node.parent node.parent.parent.left) {NodeK, V uncle node.parent.parent.right;if (uncle ! null uncle.color) {// 情况1叔叔节点是红色node.parent.color false;uncle.color false;node.parent.parent.color true;node node.parent.parent;} else {if (node node.parent.right) {// 情况2右倾先左旋node node.parent;rotateLeft(node);}// 情况3左倾右旋node.parent.color false;node.parent.parent.color true;rotateRight(node.parent.parent);}} else {NodeK, V uncle node.parent.parent.left;if (uncle ! null uncle.color) {// 情况1叔叔节点是红色node.parent.color false;uncle.color false;node.parent.parent.color true;node node.parent.parent;} else {if (node node.parent.left) {// 情况2左倾先右旋node node.parent;rotateRight(node);}// 情况3右倾左旋node.parent.color false;node.parent.parent.color true;rotateLeft(node.parent.parent);}}}return node;}// 左旋操作private void rotateLeft(NodeK, V x) {NodeK, V y x.right;x.right y.left;if (y.left ! null) {y.left.parent x;}y.parent x.parent;if (x.parent null) {root y;} else if (x x.parent.left) {x.parent.left y;} else {x.parent.right y;}y.left x;x.parent y;}// 右旋操作private void rotateRight(NodeK, V x) {NodeK, V y x.left;x.left y.right;if (y.right ! null) {y.right.parent x;}y.parent x.parent;if (x.parent null) {root y;} else if (x x.parent.right) {x.parent.right y;} else {x.parent.left y;}y.right x;x.parent y;}// 查找操作public V get(K key) {NodeK, V node root;while (node ! null) {int cmp key.compareTo(node.key);if (cmp 0) {node node.left;} else if (cmp 0) {node node.right;} else {return node.value;}}return null;}
}代码说明 节点定义 每个节点包含键、值、左右子节点和父节点指针以及一个颜色属性红色或黑色。 插入操作 插入新节点时新节点默认为红色。 插入后调用 fixAfterInsertion 方法修复红黑树的性质。 修复逻辑 根据红黑树的性质修复插入操作可能破坏的平衡。 主要处理以下几种情况 叔叔节点是红色将父节点和叔叔节点改为黑色祖父节点改为红色继续向上检查。 叔叔节点是黑色根据节点的位置进行旋转操作调整树的结构。 旋转操作 左旋将右子节点提升为新的根节点调整子树的连接关系。 右旋将左子节点提升为新的根节点调整子树的连接关系。 查找操作 从根节点开始根据键值的大小关系逐层向下查找直到找到目标节点或到达叶子节点。
