Java TreeMap 特殊方法
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 环境中执行自平衡,提供排序可预测的迭代搜索性能。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

