Java TreeMap 特殊方法

javaobject oriented programmingprogramming更新于 2024/3/15 15:08:17

TreeMap 是 Java 环境中的方法类集合框架。它存储使用 MapAbstract 类实现 Map 接口或 Map 导航的键。排序过程之后,该映射的键将以一致的方式按自然顺序存储。TreeMap 的实现可能不是有组织的,因为特定映射可以由多个线程寻址。使用自平衡红黑二叉树实现的 TreeMap 函数。此方法对于执行某些元素的添加、删除和检索非常有效,时间复杂度为 O(log n)。

现在我们对 TreeMap 有了一些基本了解。让我们深入了解它的更多功能以更好地理解。

Java 环境中的 TreeMap 是什么?

  • TreeMap 是一种数据结构,它将数据保存为值对。

  • 这里的键是唯一标识符。此方法允许保存多个操作(添加、替换和删除)的数据。

  • TreeMap 与其他 Map 一样,是一个排序的 Map,与"="符号兼容。

  • TreeMap 始终保持升序和非同步方式。

  • 快速失败 - 它是一个类集合视图方法。iterator() 类从集合中返回迭代器。它们本质上是快速失败的。

  • Comparator 接口通过两种方法帮助对元素进行排序 -

    • 键 - 将映射中的每个值关联为唯一标识符。

    • 值 - 通过映射键关联元素。

    • 在此方法中,不允许使用空键,否则会引发空指针异常。

    • 红黑树

      • 根节点为黑色。

      • 着色方法使插入和移除率保持平衡。

      • 两个红色节点不能是彼此的直接邻居。

算法

  • 步骤 1 - 创建一个新的 TreeMap。

  • 步骤 2 − 在 TreeMap 中输入一些输入。

  • 步骤 3 − 计算哈希键。

  • 步骤 4 − 终止代码。

创建 TreeMap- 语法

TreeMap<Key, Value> numbers = new TreeMap<>();

红黑树显示了 TreeMap() 方法的后端工作。父元素将始终大于左侧元素。并且右侧元素始终大于或等于父元素。

要遵循的方法

  • 方法 1 - Java 中的红黑树表示

Java 中的红黑树表示

将数据插入映射中。以下是一些将一些数据输入到映射中的方法。

  • put() - 插入值

  • putAll() - 插入条目

  • putIfAbsent() - 将值映射插入到映射中

示例 1

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
    
        TreeMap<String, Integer> evenNumbers = new TreeMap<>();
        evenNumbers.put("Seven", 7);
        evenNumbers.put("Sixteen", 16);
        evenNumbers.putIfAbsent("Ten", 10);
        System.out.println("我们可以得到偶数的 TreeMap:" + evenNumbers);
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("Three", 3);
        numbers.putAll(evenNumbers);
        System.out.println("我们从列表中得到的数字的 TreeMap:" + numbers);
    }
}

输出

这里我们可以得到偶数的TreeMap:{Seven=7, Sixteen=16, Ten=10}
这里我们从列表中得到的数字的TreeMap:{Seven=7, Sixteen=16, Ten=10, Three=3}

示例2

Java环境提供了红黑树,用户可以通过它在map中维护数据的平衡比例。

class Node {
   int data;
   Node parent;
   Node left;
   Node right;
   int color;
}

public class RedBlackTree {
   private Node root;
   private Node TNULL;
   private void preOrderHelper1(Node node) {
      if (node != TNULL) {
         System.out.print(node.data + " ");
         preOrderHelper1(node.left);
         preOrderHelper1(node.right);
      }
   }
   private void inOrderHelper7(Node node) {
      if (node != TNULL) {
         inOrderHelper7(node.left);
         System.out.print(node.data + " ");
         inOrderHelper7(node.right);
      }
   }
   private void postOrderHelper(Node node) {
      if (node != TNULL) {
         postOrderHelper(node.left);
         postOrderHelper(node.right);
         System.out.print(node.data + " ");
      }
   }
   private Node searchTreeHelper(Node node, int key) {
      if (node == TNULL || key == node.data) {
         return node;
      }

      if (key < node.data) {
         return searchTreeHelper(node.left, key);
      }
      return searchTreeHelper(node.right, key);
   }
   private void fixDelete(Node x) {
      Node s;
      while (x != root && x.color == 0) {
         if (x == x.parent.left) {
            s = x.parent.right;
            if (s.color == 1) {
               s.color = 0;
               x.parent.color = 1;
               leftRotate(x.parent);
               s = x.parent.right;
            }

            if (s.left.color == 0 && s.right.color == 0) {
               s.color = 1;
               x = x.parent;
            } else {
               if (s.right.color == 0) {
                  s.left.color = 0;
                  s.color = 1;
                  rightRotate(s);
                  s = x.parent.right;
               }

               s.color = x.parent.color;
               x.parent.color = 0;
               s.right.color = 0;
               leftRotate(x.parent);
               x = root;
            }
         } else {
            s = x.parent.left;
            if (s.color == 1) {
               s.color = 0;
               x.parent.color = 1;
               rightRotate(x.parent);
               s = x.parent.left;
            }

            if (s.right.color == 0 && s.right.color == 0) {
               s.color = 1;
               x = x.parent;
            } else {
               if (s.left.color == 0) {
                  s.right.color = 0;
                  s.color = 1;
                  leftRotate(s);
                  s = x.parent.left;
               }

               s.color = x.parent.color;
               x.parent.color = 0;
               s.left.color = 0;
               rightRotate(x.parent);
               x = root;
            }
         }
      }
      x.color = 0;
   }

   private void rbTransplant(Node u, Node v) {
      if (u.parent == null) {
         root = v;
      } else if (u == u.parent.left) {
         u.parent.left = v;
      } else {
         u.parent.right = v;
      }
      v.parent = u.parent;
   }

   private void deleteNodeHelper(Node node, int key) {
      Node z = TNULL;
      Node x, y;
      while (node != TNULL) {
         if (node.data == key) {
            z = node;
         }

         if (node.data <= key) {
            node = node.right;
         } else {
            node = node.left;
         }
      }

      if (z == TNULL) {
         System.out.println("Couldn't find key in the tree, please find it again");
         return;
      }

      y = z;
      int yOriginalColor = y.color;
      if (z.left == TNULL) {
         x = z.right;
         rbTransplant(z, z.right);
      } else if (z.right == TNULL) {
         x = z.left;
         rbTransplant(z, z.left);
      } else {
         y = minimum(z.right);
         yOriginalColor = y.color;
         x = y.right;
         if (y.parent == z) {
            x.parent = y;
         } else {
            rbTransplant(y, y.right);
            y.right = z.right;
            y.right.parent = y;
         }

         rbTransplant(z, y);
         y.left = z.left;
         y.left.parent = y;
         y.color = z.color;
      }
      if (yOriginalColor == 0) {
         fixDelete(x);
      }
   }
   private void fixInsert(Node k) {
      Node u;
      while (k.parent.color == 1) {
         if (k.parent == k.parent.parent.right) {
            u = k.parent.parent.left;
            if (u.color == 1) {
               u.color = 0;
               k.parent.color = 0;
               k.parent.parent.color = 1;
               k = k.parent.parent;
            } else {
               if (k == k.parent.left) {
                  k = k.parent;
                  rightRotate(k);
               }
               k.parent.color = 0;
               k.parent.parent.color = 1;
               leftRotate(k.parent.parent);
            }
         } else {
            u = k.parent.parent.right;

            if (u.color == 1) {
               u.color = 0;
               k.parent.color = 0;
               k.parent.parent.color = 1;
               k = k.parent.parent;
            } else {
               if (k == k.parent.right) {
               k = k.parent;
               leftRotate(k);
               }
               k.parent.color = 0;
               k.parent.parent.color = 1;
               rightRotate(k.parent.parent);
            }
         }
         if (k == root) {
            break;
         }
      }
      root.color = 0;
   }

   private void printHelper(Node root, String indent, boolean last) {
      if (root != TNULL) {
         System.out.print(indent);
         if (last) {
            System.out.print("R----");
            indent += " ";
         } else {
            System.out.print("L----");
            indent += "|";
         }

         String sColor = root.color == 1 ? "RED" : "BLACK";
         System.out.println(root.data + "(" + sColor + ")");
         printHelper(root.left, indent, false);
         printHelper(root.right, indent, true);
      }
   }

   public RedBlackTree() {
      TNULL = new Node();
      TNULL.color = 0;
      TNULL.left = null;
      TNULL.right = null;
      root = TNULL;
   }

   public void preorder() {
      preOrderHelper1(this.root);
   }

   public void inorder() {
      inOrderHelper7(this.root);
   }

   public void postorder() {
      postOrderHelper(this.root);
   }

   public Node searchTree(int k) {
      return searchTreeHelper(this.root, k);
   }

   public Node minimum(Node node) {
      while (node.left != TNULL) {
         node = node.left;
      }
      return node;
   }

   public Node maximum(Node node) {
      while (node.right != TNULL) {
         node = node.right;
      }
      return node;
   }

   public Node successor(Node x) {
      if (x.right != TNULL) {
         return minimum(x.right);
      }

      Node y = x.parent;
      while (y != TNULL && x == y.right) {
         x = y;
         y = y.parent;
      }
      return y;
   }

   public Node predecessor(Node x) {
      if (x.left != TNULL) {
         return maximum(x.left);
      }

      Node y = x.parent;
      while (y != TNULL && x == y.left) {
         x = y;
         y = y.parent;
      }

      return y;
   }

   public void leftRotate(Node x) {
      Node y = x.right;
      x.right = y.left;
      if (y.left != TNULL) {
         y.left.parent = x;
      }
      y.parent = x.parent;
      if (x.parent == null) {
         this.root = y;
      } else if (x == x.parent.left) {
         x.parent.left = y;
      } else {
         x.parent.right = y;
      }
      y.left = x;
      x.parent = y;
   }

   public void rightRotate(Node x) {
      Node y = x.left;
      x.left = y.right;
      if (y.right != TNULL) {
         y.right.parent = x;
      }
      y.parent = x.parent;
      if (x.parent == null) {
         this.root = y;
      } else if (x == x.parent.right) {
         x.parent.right = y;
      } else {
         x.parent.left = y;
      }
      y.right = x;
      x.parent = y;
   }

   public void insert(int key) {
      Node node = new Node();
      node.parent = null;
      node.data = key;
      node.left = TNULL;
      node.right = TNULL;
      node.color = 1;

      Node y = null;
      Node x = this.root;

      while (x != TNULL) {
         y = x;
         if (node.data < x.data) {
            x = x.left;
         } else {
            x = x.right;
         }
      }

      node.parent = y;
      if (y == null) {
         root = node;
      } else if (node.data < y.data) {
         y.left = node;
      } else {
         y.right = node;
      }

      if (node.parent == null) {
         node.color = 0;
         return;
      }

      if (node.parent.parent == null) {
         return;
      }

      fixInsert(node);
   }

   public Node getRoot() {
      return this.root;
   }

   public void deleteNode(int data) {
      deleteNodeHelper(this.root, data);
   }

   public void printTree() {
      printHelper(this.root, "", true);
   }

   public static void main(String[] args) {
      RedBlackTree bst = new RedBlackTree();
      bst.insert(07);
      bst.insert(10);
      bst.insert(01);
      bst.insert(16);
      bst.insert(10);
      bst.insert(97);
      bst.printTree();

      System.out.println("\nAfter deleting some elements:");
      bst.deleteNode(97);
      bst.printTree();
   }
}

输出

R----7(BLACK)
 L----1(BLACK)
 R----10(RED)
L----10(BLACK)
R----16(BLACK)
 R----97(RED)

After deleting some elements:
R----7(BLACK)
 L----1(BLACK)
 R----10(RED)
L----10(BLACK)
  R----16(BLACK)

结论

从本文中,我们详细了解了 TreeMap 类。我们在这里通过 TreeMap 方法介绍了红黑树的各个方面。TreeMap 类借助红黑树在 Java 环境中执行自平衡,提供排序可预测的迭代搜索性能。


相关文章


有用资源