数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Java TreeMap 特殊方法
TreeMap 是 Java 环境中集合框架的一个类。它存储键值对以实现 Map 接口或使用 MapAbstract 类进行 Map 导航。排序后，地图的键将以一致的自然顺序存储。TreeMap 的实现可能并非始终井然有序，因为特定地图可能被多个线程访问。TreeMap 使用自平衡红黑二叉树实现。这种方法对于添加、删除和检索元素非常高效，时间复杂度为 O(log n)。
现在我们对 TreeMap 有了一些基本的了解。让我们深入了解它的更多特性，以便更好地理解。
什么是 Java 环境中的 TreeMap？
TreeMap 是一种数据结构，它以键值对的形式保存数据。
这里的键是唯一的标识符。此方法允许保存多个操作的数据（添加、替换和删除）。
TreeMap 与其他一样是一个排序映射，兼容“=”符号。
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 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();
}
}
输出
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 环境中实现自平衡，从而提供可预测的排序迭代搜索性能。
更新于：2023年4月10日
172 次查看
广告