红黑树(Java) 超、凢脫俗 2023-07-04 12:41 77阅读 0赞 # 红黑树 # 红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 **红黑树与2-3树在很大程度上是等价的！** ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70] ### 性质 ### 1.每个节点或者是红色的，或者是黑色的（红黑树定义） 2.根节点是黑色的（红黑树的节点也可以看作是2-3树中的2节点与3节点，2节点是黑色的，3节点的根节点也是黑色的） 3.每一个叶子节点（最后的空节点）是黑色的（一棵空的红黑树既是叶子节点也是根节点，性质2-根节点是黑色的，那么空节点也是黑色的） 4.如果一个节点是红色的，那么他的孩子节点都是黑色的（红色的节点对应2-3树中3节点中左边的节点，与它连接的节点要么是3节点，要么是2节点，均是根节点，也就是黑色的） 5.从任意一个节点到叶子节点，经过的黑色节点是一样的（2-3树是一棵绝对平衡的树，左右子树的高度相同，2-3树从任意一个节点到叶子节点经过的节点数是相等的，对应到红黑树，经过的每个节点都是黑色的节点） 6.红黑树中黑色节点的右孩子一定是黑色的（如果右孩子为空，那么它是黑色的；如果右孩子不为空，所连接的节点要么是3节点，要么是2节点，均是根节点，也就是黑色的） ### RedBlackTree.java(红黑树) ### //红黑树 public class RedBlackTree<K extends Comparable<K>, V> { private static final boolean RED = true; private static final boolean BLACK = false; private class Node { public K key; public V value; public Node left, right; public boolean color; public Node(K key, V value) { this.key = key; this.value = value; left = null; right = null; color = RED;// 默认新建节点为红色 即红色代表是需要融合的节点 } } private Node root; private int size; public RedBlackTree() { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } // 左旋转 // node x // / \ 左旋转 / \ // T1 x ---------> node T3 // / \ / \ // T2 T3 T1 T2 private Node leftRotate(Node node) { Node x = node.right;// 定义 // 开始旋转 node.right = x.left; x.left = node; // 颜色 x.color = node.color; node.color = RED;// node节点与x形成3节点 return x; } // 右旋转 // node x // / \ 右旋转 / \ // x T2 -------> y node // / \ / \ // y T1 T1 T2 private Node rightRotate(Node node) { Node x = node.left;// 定义 // 旋转 node.left = x.right; x.right = node; // 维持颜色 x.color = node.color; node.color = RED;// 暂时存储为4节点 red表示融合 return x;// 返回新的根节点 } // 颜色翻转 即在3节点的右边添加元素 private void flipColors(Node node) { // 在3节点添加元素会变成3个2节点 node.color = RED;// 根节点可能需要融合所以为红色 node.left.color = BLACK; node.right.color = BLACK; } //判断红黑树根节点是否为红色 private boolean isRed(Node node) { if (node == null)// 红黑树性质 空节点默认黑色 return BLACK; return node.color; } // 向树中添加新的元素(key, value) public void add(K key, V value) { root = add(root, key, value); root.color = BLACK;// 添加后保持根节点是黑色的 } // 向以node为根的红黑树中插入元素(key, value)，递归算法 // 返回插入新节点后红黑树的根 private Node add(Node node, K key, V value) { if (node == null) { size++; return new Node(key, value);// 红色的节点 } if (key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if (key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else // key.compareTo(node.key) == 0 node.value = value; // 左旋转 if (isRed(node.right) && !isRed(node.left))// 右孩子是红色，左孩子不是红色 node = leftRotate(node); // 右旋转 if (isRed(node.left) && isRed(node.left.left))// 左孩子是红色，左孩子的左孩子也是红色 node = rightRotate(node); // 颜色翻转 if (isRed(node.left) && isRed(node.right))// 左孩子和右孩子都是红色 flipColors(node); return node; } // 返回以node为根节点的二分搜索树中，key所在的节点 private Node getNode(Node node, K key) { if (node == null) return null; if (key.equals(node.key)) return node; else if (key.compareTo(node.key) < 0) return getNode(node.left, key); else // if(key.compareTo(node.key) > 0) return getNode(node.right, key); } public boolean contains(K key) { return getNode(root, key) != null; } public V get(K key) { Node node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue) { Node node = getNode(root, key); if (node == null) throw new IllegalArgumentException(key + " doesn't exist!"); node.value = newValue; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimum(Node node) { if (node.left == null) return node; return minimum(node.left); } // 删除掉以node为根的二分搜索树中的最小节点 // 返回删除节点后新的二分搜索树的根 private Node removeMin(Node node) { if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } node.left = removeMin(node.left); return node; } // 从二分搜索树中删除键为key的节点 public V remove(K key) { Node node = getNode(root, key); if (node != null) { root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key) { if (node == null) return null; if (key.compareTo(node.key) < 0) { node.left = remove(node.left, key); return node; } else if (key.compareTo(node.key) > 0) { node.right = remove(node.right, key); return node; } else { // key.compareTo(node.key) == 0 // 待删除节点左子树为空的情况 if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } // 待删除节点右子树为空的情况 if (node.right == null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // 待删除节点左右子树均不为空的情况 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } } } ## 总结 ## #### 红黑树是保持“黑平衡”的二叉树，严格意义上，不是平衡二叉树 #### #### 当所连接的节点均为黑色节点与红色节点（2-3树中的3节点）红黑树的最大高度为2logn，时间复杂度为O(logn) #### #### 红黑树优势在于添加、删除操作，相对于AVL树更有优势，所以红黑树统计性能更优（综合增删改查所有的操作） #### [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200211002917841.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
相关 红黑树 [https://baijiahao.baidu.com/s?id=1641940303518144126&wfr=spider&for=pc][https_baijiahao 水深无声/ 2023年07月12日 03:41/ 0 赞/ 49 阅读
相关 红黑树(Java) 红黑树 红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Ba 超、凢脫俗/ 2023年07月04日 12:41/ 0 赞/ 78 阅读
相关 树：红黑树 1，红黑树引入 红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1，超过后需要进行左旋或者右旋操作再次对树进行平衡，虽然这样能够解决二叉树退化为链表的缺 ╰半橙微兮°/ 2023年02月28日 01:25/ 0 赞/ 175 阅读
相关 红黑树 红黑树的定义 每个节点要么是红色，要么是黑色。 根节点必须是黑色， 每个叶子节点是黑色（叶子节点包含NULL）。 红色节点不能连续（红色节点的孩子和父亲 Dear 丶/ 2022年12月13日 04:18/ 0 赞/ 38 阅读
相关 红黑树 红黑树（Red Black Tree） 是一种自平衡二叉查找树，红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能，它虽然 谁践踏了优雅/ 2022年06月15日 12:57/ 0 赞/ 520 阅读
相关 红黑树 > 3.3 Balanced Search Trees > [http://algs4.cs.princeton.edu/33balanced/][http_algs4.c ╰+攻爆jí腚メ/ 2022年06月09日 12:48/ 0 赞/ 371 阅读
相关 红黑树 红黑树 概念 红黑树，又被称为对称二叉B树。 [红黑树模型][Link 1] 其本质是一种二叉查找树，单它在二叉查找树的基础上额外添加了一个标记（颜色），同时具 拼搏现实的明天。/ 2022年04月10日 02:39/ 0 赞/ 462 阅读
相关 红黑树 先Mark，后续补充： [https://juejin.im/entry/58371f13a22b9d006882902d][https_juejin.im_entry_58 柔情只为你懂/ 2022年01月30日 14:57/ 0 赞/ 364 阅读
相关 红黑树 二叉查找树（BST） 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下 川长思鸟来/ 2021年10月24日 01:48/ 0 赞/ 420 阅读
相关 红黑树 1. 从 2-3 树说起 一棵标准的 BST （二叉查找树 / 二叉搜索树）是长这个样子的： BST 其中，这棵二叉查找树中的每个结点也叫 2-结点 ，2-结点 就表示树... 系统管理员/ 2020年11月29日 04:30/ 0 赞/ 866 阅读
水深无声
超、凢脫俗
╰+攻爆jí腚メ
柔情只为你懂
系统管理员
还没有评论，来说两句吧...