红黑树csdn



历史

红黑树是一种自平衡二叉查找树，最早由一位名叫Rudolf Bayer的德国计算机科学家于1972年发明。然而，最初的树形结构不是现在的红黑树，而是一种称为B树的结构，它是一种多叉树，可用于在磁盘上存储大量数据。

在1980年代早期，计算机科学家Leonard Adleman和Daniel Sleator推广了红黑树，并证明了它的自平衡性和高效性。从那时起，红黑树成为了最流行的自平衡二叉查找树之一，并被广泛应用于许多领域，如编译器、操作系统、数据库等。

红黑树的名字来源于红色节点和黑色节点的交替出现，它们的颜色是用来维护树的平衡性的关键。它们的颜色具有特殊的意义，黑色节点代表普通节点，而红色节点代表一个新添加的节点，它们必须满足一些特定的规则才能维持树的平衡性。

红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少

红黑树特性

1. 所有节点都有两种颜色：红🔴、黑⚫️
2. 所有 null 视为黑色⚫️
3. 红色🔴节点不能相邻
4. 根节点是黑色⚫️
5. 从根到任意一个叶子节点，路径中的黑色⚫️节点数一样

插入情况

插入节点均视为红色🔴

case 1：插入节点为根节点，将根节点变黑⚫️

case 2：插入节点的父亲若为黑色⚫️，树的红黑性质不变，无需调整

插入节点的父亲为红色🔴，触发红红相邻

case 3：叔叔为红色🔴

• 父亲变为黑色⚫️，为了保证黑色平衡，连带的叔叔也变为黑色⚫️
• 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色🔴
• 祖父如果变成红色，可能会接着触发红红相邻，因此对将祖父进行递归调整

case 4：叔叔为黑色⚫️

1. 父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡
   • 让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
   • 祖父右旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
2. 父亲为左孩子，插入节点是右孩子，此时即 LR 不平衡
   • 父亲左旋，变成 LL 情况，按 1. 来后续处理
3. 父亲为右孩子，插入节点也是右孩子，此时即 RR 不平衡
   • 让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
   • 祖父左旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
4. 父亲为右孩子，插入节点是左孩子，此时即 RL 不平衡
   • 父亲右旋，变成 RR 情况，按 3. 来后续处理

删除情况

case0：如果删除节点有两个孩子

• 交换删除节点和后继节点的 key，value，递归删除后继节点，直到该节点没有孩子或只剩一个孩子

如果删除节点没有孩子或只剩一个孩子

case 1：删的是根节点

• 删完了，直接将 root = null
• 用剩余节点替换了根节点的 key，value，根节点孩子 = null，颜色保持黑色⚫️不变

删黑色会失衡，删红色不会失衡，但删黑色有一种简单情况

case 2：删的是黑⚫️，剩下的是红🔴，剩下这个红节点变黑⚫️

删除节点和剩下节点都是黑⚫️，触发双黑，双黑意思是，少了一个黑

case 3：被调整节点的兄弟为红🔴，此时两个侄子定为黑 ⚫️

• 删除节点是左孩子，父亲左旋
• 删除节点是右孩子，父亲右旋
• 父亲和兄弟要变色，保证旋转后颜色平衡
• 旋转的目的是让黑侄子变为删除节点的黑兄弟，对删除节点再次递归，进入 case 4 或 case 5

case 4：被调整节点的兄弟为黑⚫️，两个侄子都为黑 ⚫️

• 将兄弟变红🔴，目的是将删除节点和兄弟那边的黑色高度同时减少 1
• 如果父亲是红🔴，则需将父亲变为黑，避免红红，此时路径黑节点数目不变
• 如果父亲是黑⚫️，说明这条路径还是少黑，再次让父节点触发双黑

case 5：被调整节点的兄弟为黑⚫️，至少一个红🔴侄子

• 如果兄弟是左孩子，左侄子是红🔴，LL 不平衡
  • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️，平衡起见，左侄子也是黑⚫️
  • 原来兄弟要成为父亲，需要保留父亲颜色
• 如果兄弟是左孩子，右侄子是红🔴，LR 不平衡
  • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️
  • 右侄子会取代原来父亲，因此它保留父亲颜色
  • 兄弟已经是黑了⚫️，无需改变
• 如果兄弟是右孩子，右侄子是红🔴，RR 不平衡
  • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️，平衡起见，右侄子也是黑⚫️
  • 原来兄弟要成为父亲，需要保留父亲颜色
• 如果兄弟是右孩子，左侄子是红🔴，RL 不平衡
  • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️
  • 左侄子会取代原来父亲，因此它保留父亲颜色
  • 兄弟已经是黑了⚫️，无需改变

完整代码

 package com.itheima.datastructure.redblacktree;  ​  import static com.itheima.datastructure.redblacktree.RedBlackTree.Color.BLACK;  import static com.itheima.datastructure.redblacktree.RedBlackTree.Color.RED;  ​  /   * <h3>红黑树</h3>   */  public class RedBlackTree {  ​      enum Color {          RED, BLACK;     }  ​      Node root;  ​      static class Node {          int key;          Object value;          Node left;          Node right;          Node parent;        // 父节点          Color color = RED;  // 颜色  ​          public Node(int key, Object value) {              this.key = key;              this.value = value;         }  ​          public Node(int key) {              this.key = key;         }  ​          public Node(int key, Color color) {              this.key = key;              this.color = color;         }  ​          public Node(int key, Color color, Node left, Node right) {              this.key = key;              this.color = color;              this.left = left;              this.right = right;              if (left != null) {                  left.parent = this;             }              if (right != null) {                  right.parent = this;             }         }  ​          // 是否是左孩子          boolean isLeftChild() {              return parent != null && parent.left == this;         }  ​          // 叔叔          Node uncle() {              if (parent == null || parent.parent == null) {                  return null;             }              if (parent.isLeftChild()) {                  return parent.parent.right;             } else {                  return parent.parent.left;             }         }  ​          // 兄弟          Node sibling() {              if (parent == null) {                  return null;             }              if (this.isLeftChild()) {                  return parent.right;             } else {                  return parent.left;             }         }     }  ​      // 判断红      boolean isRed(Node node) {          return node != null && node.color == RED;     }  ​      // 判断黑      boolean isBlack(Node node) {  //       return !isRed(node);          return node == null || node.color == BLACK;     }  ​      // 右旋 1. parent 的处理 2. 旋转后新根的父子关系      private void rightRotate(Node pink) {          Node parent = pink.parent;          Node yellow = pink.left;          Node green = yellow.right;          if (green != null) {              green.parent = pink;         }          yellow.right = pink;          yellow.parent = parent;          pink.left = green;          pink.parent = yellow;          if (parent == null) {              root = yellow;         } else if (parent.left == pink) {              parent.left = yellow;         } else {              parent.right = yellow;         }     }  ​      // 左旋      private void leftRotate(Node pink) {          Node parent = pink.parent;          Node yellow = pink.right;          Node green = yellow.left;          if (green != null) {              green.parent = pink;         }          yellow.left = pink;          yellow.parent = parent;          pink.right = green;          pink.parent = yellow;          if (parent == null) {              root = yellow;         } else if (parent.left == pink) {              parent.left = yellow;         } else {              parent.right = yellow;         }     }  ​      /       * 新增或更新       * <br>       * 正常增、遇到红红不平衡进行调整       *       * @param key   键       * @param value 值       */      public void put(int key, Object value) {          Node p = root;          Node parent = null;          while (p != null) {              parent = p;              if (key < p.key) {                  p = p.left;             } else if (p.key < key) {                  p = p.right;             } else {                  p.value = value; // 更新                  return;             }         }          Node inserted = new Node(key, value);          if (parent == null) {              root = inserted;         } else if (key < parent.key) {              parent.left = inserted;              inserted.parent = parent;         } else {              parent.right = inserted;              inserted.parent = parent;         }          fixRedRed(inserted);     }  ​      void fixRedRed(Node x) {          // case 1 插入节点是根节点，变黑即可          if (x == root) {              x.color = BLACK;              return;         }          // case 2 插入节点父亲是黑色，无需调整          if (isBlack(x.parent)) {              return;         }          /* case 3 当红红相邻，叔叔为红时              需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理          */          Node parent = x.parent;          Node uncle = x.uncle();          Node grandparent = parent.parent;          if (isRed(uncle)) {              parent.color = BLACK;              uncle.color = BLACK;              grandparent.color = RED;              fixRedRed(grandparent);              return;         }  ​          // case 4 当红红相邻，叔叔为黑时          if (parent.isLeftChild() && x.isLeftChild()) { // LL              parent.color = BLACK;              grandparent.color = RED;              rightRotate(grandparent);         } else if (parent.isLeftChild()) { // LR              leftRotate(parent);              x.color = BLACK;              grandparent.color = RED;              rightRotate(grandparent);         } else if (!x.isLeftChild()) { // RR              parent.color = BLACK;              grandparent.color = RED;              leftRotate(grandparent);         } else { // RL              rightRotate(parent);              x.color = BLACK;              grandparent.color = RED;              leftRotate(grandparent);         }     }  ​      /       * 删除       * <br>       * 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整       *       * @param key 键       */      public void remove(int key) {          Node deleted = find(key);          if (deleted == null) {              return;         }          doRemove(deleted);     }  ​      public boolean contains(int key) {          return find(key) != null;     }  ​      // 查找删除节点      private Node find(int key) {          Node p = root;          while (p != null) {              if (key < p.key) {                  p = p.left;             } else if (p.key < key) {                  p = p.right;             } else {                  return p;             }         }          return null;     }  ​      // 查找剩余节点      private Node findReplaced(Node deleted) {          if (deleted.left == null && deleted.right == null) {              return null;         }          if (deleted.left == null) {              return deleted.right;         }          if (deleted.right == null) {              return deleted.left;         }          Node s = deleted.right;          while (s.left != null) {              s = s.left;         }          return s;     }  ​      // 处理双黑 (case3、case4、case5)      private void fixDoubleBlack(Node x) {          if (x == root) {              return;         }          Node parent = x.parent;          Node sibling = x.sibling();          // case 3 兄弟节点是红色          if (isRed(sibling)) {              if (x.isLeftChild()) {                  leftRotate(parent);             } else {                  rightRotate(parent);             }              parent.color = RED;              sibling.color = BLACK;              fixDoubleBlack(x);              return;         }          if (sibling != null) {              // case 4 兄弟是黑色, 两个侄子也是黑色              if (isBlack(sibling.left) && isBlack(sibling.right)) {                  sibling.color = RED;                  if (isRed(parent)) {                      parent.color = BLACK;                 } else {                      fixDoubleBlack(parent);                 }             }              // case 5 兄弟是黑色, 侄子有红色              else {                  // LL                  if (sibling.isLeftChild() && isRed(sibling.left)) {                      rightRotate(parent);                      sibling.left.color = BLACK;                      sibling.color = parent.color;                 }                  // LR                  else if (sibling.isLeftChild() && isRed(sibling.right)) {                      sibling.right.color = parent.color;                      leftRotate(sibling);                      rightRotate(parent);                 }                  // RL                  else if (!sibling.isLeftChild() && isRed(sibling.left)) {                      sibling.left.color = parent.color;                      rightRotate(sibling);                      leftRotate(parent);                 }                  // RR                  else {                      leftRotate(parent);                      sibling.right.color = BLACK;                      sibling.color = parent.color;                 }                  parent.color = BLACK;             }         } else {              // @TODO 实际也不会出现，触发双黑后，兄弟节点不会为 null              fixDoubleBlack(parent);         }     }  ​      private void doRemove(Node deleted) {          Node replaced = findReplaced(deleted);          Node parent = deleted.parent;          // 没有孩子          if (replaced == null) {              // case 1 删除的是根节点              if (deleted == root) {                  root = null;             } else {                  if (isBlack(deleted)) {                      // 双黑调整                      fixDoubleBlack(deleted);                 } else {                      // 红色叶子, 无需任何处理                 }                  if (deleted.isLeftChild()) {                      parent.left = null;                 } else {                      parent.right = null;                 }                  deleted.parent = null;             }              return;         }          // 有一个孩子          if (deleted.left == null || deleted.right == null) {              // case 1 删除的是根节点              if (deleted == root) {                  root.key = replaced.key;                  root.value = replaced.value;                  root.left = root.right = null;             } else {                  if (deleted.isLeftChild()) {                      parent.left = replaced;                 } else {                      parent.right = replaced;                 }                  replaced.parent = parent;                  deleted.left = deleted.right = deleted.parent = null;                  if (isBlack(deleted) && isBlack(replaced)) {                      // @TODO 实际不会有这种情况 因为只有一个孩子时 被删除节点是黑色 那么剩余节点只能是红色不会触发双黑                      fixDoubleBlack(replaced);                 } else {                      // case 2 删除是黑，剩下是红                      replaced.color = BLACK;                 }             }              return;         }          // case 0 有两个孩子 => 有一个孩子 或 没有孩子          int t = deleted.key;          deleted.key = replaced.key;          replaced.key = t;  ​          Object v = deleted.value;          deleted.value = replaced.value;          replaced.value = v;          doRemove(replaced);     }  }

• 以上代码中的 TODO 未作改正

普通二叉搜索树插入、删除、查询的时间复杂度与树的高度相关，因此在最坏情况下，时间复杂度为O(n)，而且容易退化成链表，查找效率低。

AVL树是一种高度平衡的二叉搜索树，其左右子树的高度差不超过1。因此，它能够在logn的平均时间内完成插入、删除、查询操作，但是在维护平衡的过程中，需要频繁地进行旋转操作，导致插入删除效率较低。

红黑树是一种近似平衡的二叉搜索树，它在保持高度平衡的同时，又能够保持较高的插入删除效率。红黑树通过节点着色和旋转操作来维护平衡。红黑树在维护平衡的过程中，能够进行较少的节点旋转操作，因此插入删除效率较高，并且查询效率也较高。

综上所述，红黑树具有较高的综合性能，是一种广泛应用的数据结构。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/3012.html