數據結構專欄 ?(click)
大家好！我是你們的老朋友——想不明白的過度思考者！今天我們要一起探索Java中兩個神奇的數據結構：Map和Set！準備好了嗎？讓我們開始這場魔法之旅吧！🎩
🎯 先來點開胃菜：二叉搜索樹（BST）
🌳 什么是二叉搜索樹？
想象一下，你有一棵神奇的樹，左邊的果子都比樹根小，右邊的果子都比樹根大！這就是我們的二叉搜索樹！
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:
- 若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
- 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
- 它的左右子樹也分別為二叉搜索樹
package Tree;//表示樹的節點
class Node {public int key;public Node left;public Node right;public Node(int key) {this.key = key;}@Overridepublic String toString() {return "Node{" +"key=" + key +", left=" + left +", right=" + right +'}';}
}public class BinarySearchTree {private Node root = null;//把新的元素插入到樹中public void insert(int key) {//如果當前是空樹，那就直接用root指向新節點即可Node newNode = new Node(key);if (root == null) {root = newNode;}// 如果是普通的樹，需要找到哦插入位置，再去進行插入//cur用來找待插入元素的位置//parent記錄cur的父元素Node cur = root;Node parent = null;while (cur != null) {if(key<cur.key) {//往左找parent = cur;cur = cur.left;}else if(key>cur.key) {//往右找parent = cur;cur = cur.right;}else {//對于相等的情況，存在不同的解決方式//當前不允許重復key存在，并且是Set只保存key，直接returnreturn;}}//通過上述循環最終得到的結果就是cur為空//此時的parent就是葉子節點，也就是新插入元素的父親，此時就是要把newNode插入到parent的子節點上//新節點，應該在parent的左子樹還是右子樹呢??直接比較大小if (key> parent.key){parent.right = newNode;}else {parent.left = newNode;}}public void remove(int key) {if (root == null) {return;}//查找要刪除節點的位置，記錄其父節點Node cur = root;Node parent = null;while (cur != null) {if(key<cur.key) {parent = cur;cur = cur.left;}else if(key>cur.key) {parent = cur;cur = cur.right;}else {//找到了removeNode(parent, cur);return;}}}private void removeNode(Node parent, Node cur) {//具體刪除節點要考慮四種情況//1.沒有子樹if(cur.right == null && cur.left == null) {//1.1如果cur就是root，需要對root進行調整if(cur == root) {//說明整棵樹只有root一個節點，直接把root設置為空root = null;}//1.2如果cur不是root，同時cur是parent的左子樹if (cur == parent.left) {parent.left = null;return;}//1.3如果cur不是root，同時cur是parent的右子樹if (cur == parent.right) {parent.right = null;return;}//穩妥起見加個returnreturn;}//2.只有左子樹if(cur.left != null && cur.right == null) {//2.1cur為rootif(cur == root){root = cur.left;return;}//2.2cur不為root，且cur是parent的左子樹if (cur == parent.left) {parent.left = cur.left;return;}//2.3cur不為root，且cur是parent的右子樹if (cur == parent.right) {parent.right = cur.left;return;}}//3.只有右子樹if(cur.left == null && cur.right != null) {//3.1只有rootif(cur == root){root = cur.right;return;}//3.2cur不是root，且cur是parent的左子樹if (cur == parent.left) {parent.left = cur.right;return;}//3.3cur不是root，且cur是parent的右子樹if (cur == parent.right) {parent.right = cur.right;return;}}//4.左右都有子樹if(cur.left != null && cur.right != null) {// 這種情況下，不需要考慮 cur 是不是 root的情況，并沒有真正的刪除 cur指向的節點，即使 cur 是 root，也無需修改 root 的指向//因為實際刪除的是“替罪羊節點”//4.1首先需要找到右子樹中的最小值 =>替罪羊,//后續要刪除替罪羊，也順便把替罪羊的父親，記錄一下.Node goat = cur.right;Node goatParent= cur;while (goat.left != null) {goatParent = goat;goat = goat.left;}//循環結束后。goat指向的就是cur右子樹的最左側元素//4.2移花接木，把替罪羊節點的值復制到cur節點中cur.key = goat.key;//4.3真正刪除goat節點，因為goat是沒有左子樹的，讓goatParent直接連上goat的右子樹即可// 即使goat的右子樹也是空也不影響if(goat == goatParent.left){goatParent.left = goat.right;}else {goatParent.right = goat.right;}}}//查找key是否在樹中，如果存在則返回對應節點位置，如果不存在則返回nullprivate Node find(int key) {if (root == null) {return null;}Node cur = root;while (cur != null) {if(key<cur.key) {cur = cur.left;}else if(key>cur.key) {cur = cur.right;}else {//相等，找到了return cur;}}return null;}//先序遍歷private static void preOrder(Node root) {if (root == null) {return;}System.out.print(root.key + " ");preOrder(root.left);preOrder(root.right);}//中序遍歷private static void inOrder(Node root) {if (root == null) {return;}inOrder(root.left);System.out.print(root.key + " ");inOrder(root.right);}public void print(){//先打印先序遍歷System.out.println("先序遍歷結果：");preOrder(root);System.out.println();//在打印中序遍歷System.out.println("中序遍歷結果：");inOrder(root);//有了先序和中序就能夠畫出樹的結構}public static void main(String[] args) {int[] arr = {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};//BinarySearchTree也總被縮寫成BSTBinarySearchTree tree = new BinarySearchTree();//循環插入for(int key: arr){tree.insert(key);}tree.print();System.out.println();System.out.println(tree.find(7));}
}🎭 BST的表演時刻
| 操作 | 最佳情況（完全二叉樹） | 最差情況（單支樹） |
|---|---|---|
| 查找 | O(logN) | O(N) |
| 插入 | O(logN) | O(N) |
| 刪除 | O(logN) | O(N) |
💡 小貼士：Java中的TreeMap和TreeSet就是用紅黑樹（BST的升級版）實現的哦！
🎩 主角登場：Map和Set
🗺? Map：你的萬能字典
Map就像你的通訊錄，名字（Key）對應電話（Value），而且名字不能重復！
Map<String, String> heroNicknames = new HashMap<>();
heroNicknames.put("林沖", "豹子頭");
heroNicknames.put("李逵", "黑旋風");
heroNicknames.put("宋江", "及時雨");// 獲取外號
System.out.println(heroNicknames.get("林沖")); // 輸出：豹子頭// 遍歷所有英雄
for (Map.Entry<String, String> entry : heroNicknames.entrySet()) {System.out.println(entry.getKey() + "的外號是：" + entry.getValue());
}
- Tip：使用put方法時：
若key不同，value相同則新增鍵值對
若key相同，value不同則為修改對應的value
🎭 Map的兩種實現對比
| 特性 | TreeMap（紅黑樹） | HashMap（哈希表） |
|---|---|---|
| 底層結構 | 紅黑樹 | 哈希桶 |
| 時間復雜度 | O(logN) | O(1) |
| 是否有序 | Key有序 | 無序 |
| 允許null | Key不能為null | Key和Value都可以為null |
🎪 Set：獨一無二的馬戲團
Set就像一個不允許重復演員的馬戲團，每個演員都是獨一無二的！
Set<String> fruitSet = new HashSet<>();
fruitSet.add("蘋果");
fruitSet.add("香蕉");
fruitSet.add("橙子");
fruitSet.add("蘋果"); // 這個不會被添加進去System.out.println(fruitSet.contains("香蕉")); // 輸出：true
System.out.println(fruitSet.size()); // 輸出：3
🎭 Set的兩種實現對比
| 特性 | TreeSet（紅黑樹） | HashSet（哈希表） |
|---|---|---|
| 底層結構 | 紅黑樹 | 哈希桶 |
| 時間復雜度 | O(logN) | O(1) |
| 是否有序 | Key有序 | 無序 |
| 允許null | 不允許 | 允許 |
🔮 哈希表：數據結構的魔法帽
🎩 哈希函數：魔法咒語
哈希函數就像把名字變成數字的咒語：
int hashCode = "魔法".hashCode(); // 返回一個魔法數字
? 哈希沖突：當兩個咒語撞車了
當不同的Key計算出相同的哈希值，就發生了沖突！我們有幾種解決辦法：
-
開放地址法（線性探測/二次探測）
- 線性探測：h(key) = (h(key) + i) % size
- 二次探測：h(key) = (h(key) + i2) % size
-
鏈地址法（哈希桶）
- 每個位置放一個鏈表，沖突的元素都掛在鏈表上
🌟 哈希桶實現：我們的魔法實驗室
public class HashBucket {static class Node {int key, value;Node next;public Node(int key, int value) {this.key = key;this.value = value;}}private Node[] array;private int size;private static final double LOAD_FACTOR = 0.75;public HashBucket() {array = new Node[8];size = 0;}public int put(int key, int value) {int index = key % array.length;// 查找key是否已存在for (Node cur = array[index]; cur != null; cur = cur.next) {if (key == cur.key) {int oldValue = cur.value;cur.value = value;return oldValue;}}// 插入新節點Node node = new Node(key, value);node.next = array[index];array[index] = node;size++;// 檢查是否需要擴容if ((double)size / array.length >= LOAD_FACTOR) {resize();}return -1;}private void resize() {Node[] newArray = new Node[array.length * 2];for (int i = 0; i < array.length; i++) {Node next;for (Node cur = array[i]; cur != null; cur = next) {next = cur.next;int index = cur.key % newArray.length;cur.next = newArray[index];newArray[index] = cur;}}array = newArray;}public int get(int key) {int index = key % array.length;for (Node cur = array[index]; cur != null; cur = cur.next) {if (key == cur.key) return cur.value;}return -1;}
}
📊 哈希表性能分析
| 因素 | 影響 |
|---|---|
| 哈希函數設計 | 決定沖突率高低 |
| 負載因子 | 通常控制在0.75以下 |
| 沖突解決方法 | 影響查找效率和內存使用 |
| 擴容機制 | 影響性能和內存使用的平衡 |
🎯 實戰演練：OJ題目解析
1. 只出現一次的數字
題目：給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。
魔法解法：使用異或運算的特性！
public int singleNumber(int[] nums) {int result = 0;for (int num : nums) {result ^= num;}return result;
}
2. 寶石與石頭
題目：給定字符串J代表寶石的類型，S代表你擁有的石頭。你想知道你擁有的石頭中有多少是寶石。
魔法解法：使用HashSet！
public int numJewelsInStones(String J, String S) {Set<Character> jewels = new HashSet<>();for (char c : J.toCharArray()) {jewels.add(c);}int count = 0;for (char c : S.toCharArray()) {if (jewels.contains(c)) count++;}return count;
}
🎓 知識總結：思維導圖
🎉 結語：選擇你的魔法武器
今天我們一起探索了Map和Set的魔法世界，從二叉搜索樹到哈希表，從TreeMap到HashMap，每個數據結構都有它獨特的魔法特性！
記住：
- 需要快速查找？選HashMap/HashSet！
- 需要有序存儲？選TreeMap/TreeSet！
- 遇到哈希沖突？試試鏈地址法！
希望這篇博客能像魔法一樣幫助你理解這些數據結構！
)
