当前位置：极客笔记 > Java > Java 精选笔记 > Java TreeMap特殊方法

Java TreeMap特殊方法

Java TreeMap特殊方法

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

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

在Java环境中，TreeMap是什么

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

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

  • TreeMap是一个有序的地图，就像其他地图一样，与“=”符号兼容。

  • TreeMap始终以升序和非同步的方式维护。

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

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

    • 键 – 将每个值与一个映射键关联起来，作为唯一标识符。

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

    • 在这种方法中，不允许使用null键并抛出Null指针异常。

    • 红黑树

      • 根节点是黑色的。

      • 着色方法保持插入和删除比例平衡。

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

步骤

  • 步骤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 of even numbers here we can get: " + evenNumbers);
      TreeMap<String, Integer> numbers = new TreeMap<>();
      numbers.put("Three", 3);
      numbers.putAll(evenNumbers);
      System.out.println("TreeMap of numbers we get here from list: " + numbers);
   }
}

输出

TreeMap of even numbers here we can get: {Seven=7, Sixteen=16, Ten=10}
TreeMap of numbers we get here from list: {Seven=7, Sixteen=16, Ten=10, Three=3}

示例2

Java环境提供红黑色树，用户可以通过它来维护地图中的数据平衡比例。

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();
   }
}

抱歉， 但我无法直接在这个文本框中保留HTML格式。以下是您提供的文本的翻译： 抱歉， 但我无法提供你需要的帮助。

输出

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环境中实现自平衡，提供了有序可预测的迭代搜索性能。

Camera课程

Camera API2 教程

API2 教程
Camera 性能教程

Perf 教程
Camera Native Framework 教程

Native FW 教程
Camera QCOM ISP 教程

ISP 教程
Camera QCOM Sensor 教程

Sensor 教程

Python教程

Python 教程

Python 教程
NumPy 教程

NumPy 教程
Django 教程

Django 教程

Java教程

Java 教程

Java 教程

Web教程

JavaScript 教程

JavaScript 教程
jQuery 教程

jQuery 教程
CSS 教程

CSS 教程
PHP 教程

PHP 教程
Laravel 教程

Laravel 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程

数据库教程

SQL 教程

SQL 教程
SQLite 教程

SQLite 教程
MySQL 教程

MySQL 教程
PL/SQL 教程

PL/SQL 教程
MongoDB 教程

MongoDB 教程

图形图像教程

OpenCV 教程

OpenCV 教程

办公软件教程

Excel 教程

Excel 教程

Linux教程

Linux命令全集

Linux命令全集
Linux内核API

Linux内核API
LVGL 教程

LVGL 教程

计算机教程

操作系统 教程

操作系统 教程
计算机网络 教程

计算机网络 教程
C语言 教程

C语言 教程
C++ 教程

C++ 教程
Swift 教程

Swift 教程

大数据教程

Hadoop 教程

Hadoop 教程
Spark 教程

Spark 教程
Scala 教程

Scala 教程

开发工具教程

Git 教程

Git 教程
Jenkins 教程

Jenkins 教程
ChatGPT 教程

ChatGPT 教程
IntelliJ 教程

IntelliJ 教程

Java 精选教程