資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告