红黑树是 2-3-4 树的实现,所以在讲红黑树之前想讲下 2-3-4 树有助于理解红黑树。 因为红黑树是一棵自平衡二叉搜索树,通过结点颜色改变和局部旋转来维持平衡,所以除了一些会改变树结构的操作之外,其他的操作都和普通的二叉搜索树相同。因此这里就只讲插入删除操作。 因为我要用红黑树实现一个符号表,所以结点需要存储键值对,而且实现的红黑树是基于 2-3-4 树。
通过观察以上两图基本能看出两者的关系了
实现部分的代码用 Java
每个结点的类型是 Node,里面有 5 个字段。
- private class Node {
- Key key;
- Value value;
- Node left;
- Node right;
- boolean color;
- public
- Node
- (Key key, Value value, Node left, Node right, boolean color)
- {
- this.key = key;
- this.value = value;
- this.left = left;
- this.right = right;
- this.color = color;
- }
- }
当我们想要在树中插入一个新结点时,先在树中搜索与插入结点键相同的结点。
结点,因为插入位置在右边,则需要对 0001** 做一个左旋操作:
- 0003
** 结点:
- 0004
首先要删除一个结点的话,这个结点有两种可能的颜色:
- import java.util.*;
- public
- class
- RBTree
- <
- Key
- extends
- Comparable
- <
- Key
- >,
- Value
- >
- {
- private class Node {
- Key key;
- Value value;
- Node left;
- Node right;
- boolean color;
- public
- Node
- (Key key, Value value, Node left, Node right, boolean color)
- {
- this.key = key;
- this.value = value;
- this.left = left;
- this.right = right;
- this.color = color;
- }
- }
- private static final boolean RED = true;
- private static final boolean BLACK = false;
- private int size;
- private Node root;
- public
- boolean
- isEmpty
- ()
- {
- return root == null;
- }
- private
- boolean
- isRed
- (Node node)
- {
- return node != null && node.color;
- }
- //颜色转换
- private
- void
- flipColors
- (Node h)
- {
- h.color = !h.color;
- h.left.color = !h.left.color;
- h.right.color = !h.right.color;
- }
- //左旋
- private Node rotationLeft(Node node) {
- Node x = node.right;
- node.right = x.left;
- x.left = node;
- x.color = node.color;
- node.color = RED;
- return x;
- }
- //右旋
- private Node rotationRight(Node node) {
- Node x = node.left;
- node.left = x.right;
- x.right = node;
- x.color = node.color;
- node.color = RED;
- return x;
- }
- //平衡操作
- private Node balance(Node node) {
- if (isRed(node.left) && isRed(node.right) && !isRed(node)) {
- if ((isRed(node.left.left) || isRed(node.left.right) || isRed(node.right.left) || isRed(node.right.right)))
- flipColors(node);
- }
- else {
- if (isRed(node.left)){
- if (isRed(node.left.right))
- node.left = rotationLeft(node.left);
- if (isRed(node.left) && isRed(node.left.left))
- node = rotationRight(node);
- }else if (isRed(node.right)){
- if (isRed(node.right) && isRed(node.right.left))
- node.right = rotationRight(node.right);
- if (isRed(node.right) && isRed(node.right.right))
- node = rotationLeft(node);
- }
- if (isRed(node.left) && isRed(node.right) && !isRed(node)) {
- if ((isRed(node.left.left) || isRed(node.left.right) || isRed(node.right.left) || isRed(node.right.right)))
- flipColors(node);
- }
- }
- return node;
- }
- private Node max(Node node) {
- if(node == null) {
- return null;
- } else {
- while(node.right != null) {
- node = node.right;
- }
- return node;
- }
- }
- private Node min(Node node) {
- if(node == null) {
- return null;
- } else {
- while(node.left != null) {
- node = node.left;
- }
- return node;
- }
- }
- public Value max() {
- return root == null ? null : max(root).value;
- }
- public Value min() {
- return root == null ? null : min(root).value;
- }
- //插入
- public
- void
- put
- (Key key, Value value)
- {
- root = put(key, value, root);
- root.color = BLACK;
- }
- private Node put(Key key, Value value, Node node) {
- if(node == null) {
- ++size;
- return new Node(key, value, null, null, RED);
- } else {
- int cmp = key.compareTo(node.key);
- if(cmp < 0) {
- node.left = put(key, value, node.left);
- } else if (cmp > 0){
- node.right = put(key, value, node.right);
- }else{
- node.value = value;
- }
- return balance(node);
- }
- }
- public
- void
- deleteMin
- ()
- {
- if (!isEmpty()){
- root.color = RED;
- root = deleteMin(root);
- --size;
- if (!isEmpty())
- root.color = BLACK;
- }
- }
- private Node deleteMin(Node node){
- if (node.left == null){
- return node.right;
- }
- if (!isRed(node.left)) {
- if(!isRed(node.left) && !isRed(node.right))
- flipColors(node);
- else
- node = rotationLeft(node);
- }
- node.left = deleteMin(node.left);
- return balance(node);
- }
- public
- void
- deleteMax
- ()
- {
- if (!isEmpty()){
- root.color = RED;
- root = deleteMax(root);
- --size;
- if (!isEmpty())
- root.color = BLACK;
- }
- }
- private Node deleteMax(Node node){
- if (node.right == null){
- return node.left;
- }
- if (!isRed(node.right)) {
- if(!isRed(node.left) && !isRed(node.right))
- flipColors(node);
- else
- node = rotationRight(node);
- }
- node.right = deleteMax(node.right);
- return balance(node);
- }
- //删除
- public
- void
- delete
- (Key key)
- {
- if (!isEmpty()){
- root.color = RED;
- root = delete(key, root);
- if (!isEmpty())
- root.color = BLACK;
- }
- }
- private Node delete(Key key, Node node){
- if (node == null)
- return null;
- int cmp = key.compareTo(node.key);
- if (cmp < 0){
- if (node.left != null && !isRed(node.left)) {
- if(!isRed(node.right))
- flipColors(node);
- else
- node = rotationLeft(node);
- }
- node.left = delete(key, node.left);
- }else if (cmp > 0){
- if (node.right != null && !isRed(node.right)) {
- if(!isRed(node.left))
- flipColors(node);
- else
- node = rotationRight(node);
- }
- node.right = delete(key, node.right);
- }else {
- --size;
- if (node.left == null)
- return node.right;
- if (node.right == null)
- return node.left;
- Node x = min(node.right);
- node.key = x.key;
- node.value = x.value;
- node.right = deleteMin(node.right);
- }
- return balance(node);
- }
- //判断树是否为一棵红黑树
- public
- boolean
- isRBTree
- ()
- {
- return isRBTree(root);
- }
- public
- boolean
- isRBTree
- (Node node)
- {
- if(node == null) {
- return true;
- } else if(node.color == RED) {
- return false;
- } else {
- Node x = node;
- int count = 0;
- for(; x != null; x = x.left) {
- if(x.color == BLACK) {
- ++count;
- }
- }
- return isRBTree(node, count, 0);
- }
- }
- private
- boolean
- isRBTree
- (Node node, int count, int k)
- {
- if(node == null) {
- return count == k;
- } else if((isRed(node.left) && isRed(node.left.left))
- ||(isRed(node.left) && isRed(node.left.right))
- ||(isRed(node.right) && isRed(node.right.right))
- ||(isRed(node.right) && isRed(node.right.left))) {
- return false;
- } else {
- if(node.color == BLACK) {
- ++k;
- }
- return node.left == null && node.right == null ? k == count:isRBTree(node.left, count, k) && isRBTree(node.right, count, k);
- }
- }
- //树的中序遍历
- public
- void
- inTraverse
- ()
- {
- inTraverse(root);
- }
- private
- void
- inTraverse
- (Node node)
- {
- if (node == null)
- return;
- inTraverse(node.left);
- System.out.print(node.key + " ");
- inTraverse(node.right);
- }
- //测试
- public
- static
- void
- main
- (String[] args)
- {
- int n = 3000, a;
- Random random = new Random();
- RBTree<Integer, String> rbt = new RBTree();
- for (int i = 1; i <= n; ++i) {
- a = random.nextInt(50000);
- rbt.put(a, "naoko");
- }
- for (int i = 0; i < 1500; ++i) {
- rbt.delete(i);
- }
- if (!rbt.isRBTree()) {
- System.out.println("不是红黑树");
- return;
- }
- rbt.inTraverse();
- System.out.print("是红黑树");
- }
- }
红黑树和 AVL 树类似,都是在进行插入和删除操作时通过特定操作保持树的平衡,从而获得较高的查找性能。不同的是红黑树并不是向 AVL 树那样追求完美平衡,而是黑色平衡,即从根结点到任意一个空结点的简单路径上黑色结点数都相同。因为一棵红黑树的高度最高不超过 **2lg(N+1),因此其查找时间复杂度也是 O(lgN) 级别的。而对于插入和删除操作产生不平衡情况都会在 3 次旋转之内快速解决,所以复杂度基本为 O(lgN)** 级别,也因为这一点红黑树的效率比 AVL 树快。
红黑树的插入和删除操作都有自顶向下和自顶向上两种方法,其中自顶向下较为容易,我的删除操作实现属于自顶向下的方法。在 JDK 中的 TreeMap 中插入和删除就用了自底向上的方法。
来源: https://juejin.im/post/5a30a3ac51882535c47140bb