上節(jié)課學(xué)習(xí)了二分搜索樹這樣一種有序數(shù)據(jù)結(jié)構(gòu) 冠桃，本節(jié)課將借助二分搜索樹來實(shí)現(xiàn)更高級(jí)的數(shù)據(jù)結(jié)構(gòu)--集合與映射板乙。
1. 集合
1.1 基于二分搜索樹的集合實(shí)現(xiàn)
集合的主要特點(diǎn)是不能盛放重復(fù)元素，在實(shí)際生活中哲泊，應(yīng)用也很廣泛：
- 公司客戶統(tǒng)計(jì)
- 書籍詞匯量統(tǒng)計(jì)
上一節(jié)實(shí)現(xiàn)的二分搜索樹不能添加相同的元素，是非常好的實(shí)現(xiàn)集合的底層數(shù)據(jù)結(jié)構(gòu)。要實(shí)現(xiàn)集合旅挤，首先需要定義如下通用型集合接口：
public interface Set<E> {
// 1. 添加元素
public void add(E e);
// 2. 刪除元素
public void remove(E e);
// 3. 判斷是否為空
public boolean isEmpty();
// 4. 查看集合內(nèi)元素個(gè)數(shù)
public int getSize();
// 5. 判斷是否包含某元素
public boolean contains(E e);
}
然后使用上一節(jié)創(chuàng)建的二分搜索樹來實(shí)現(xiàn)該接口：
import java.util.Comparator;
public class BSTSet<E extends Comparable<E>> implements Set<E> {
private BST<E> data;
public BSTSet() {
data = new BST<>();
}
@Override
public int getSize() {
return data.getSize();
}
@Override
public boolean isEmpty() {
return data.isEmpty();
}
@Override
public boolean contains(E e) {
return data.contains(e);
}
@Override
public void add(E e) {
data.addElement(e);
}
@Override
public void remove(E e) {
data.removeElement(e);
}
}
下面測(cè)試上述實(shí)現(xiàn)，編寫測(cè)試函數(shù)伞鲫，計(jì)算《傲慢與偏見》的詞匯量粘茄，這里需要借助文件讀取，首先實(shí)現(xiàn)文字的切割：
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Locale;
import java.io.File;
import java.io.BufferedInputStream;
import java.io.IOException;
// 文件相關(guān)操作
public class FileOperation {
// 讀取文件名稱為filename中的內(nèi)容秕脓，并將其中包含的所有詞語放進(jìn)words中
public static boolean readFile(String filename, ArrayList<String> words){
if (filename == null || words == null){
System.out.println("filename is null or words is null");
return false;
}
// 文件讀取
Scanner scanner;
try {
File file = new File(filename);
if(file.exists()){
FileInputStream fis = new FileInputStream(file);
scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
scanner.useLocale(Locale.ENGLISH);
}
else
return false;
}
catch(IOException ioe){
System.out.println("Cannot open " + filename);
return false;
}
// 簡(jiǎn)單分詞
// 這個(gè)分詞方式相對(duì)簡(jiǎn)陋, 沒有考慮很多文本處理中的特殊問題
// 在這里只做demo展示用
if (scanner.hasNextLine()) {
String contents = scanner.useDelimiter("\\A").next();
int start = firstCharacterIndex(contents, 0);
for (int i = start + 1; i <= contents.length(); )
if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {
String word = contents.substring(start, i).toLowerCase();
words.add(word);
start = firstCharacterIndex(contents, i);
i = start + 1;
} else
i++;
}
return true;
}
// 尋找字符串s中柒瓣，從start的位置開始的第一個(gè)字母字符的位置
private static int firstCharacterIndex(String s, int start){
for( int i = start ; i < s.length() ; i ++ )
if( Character.isLetter(s.charAt(i)) )
return i;
return s.length();
}
}
測(cè)試函數(shù)：
public static void main(String[] args) {
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
System.out.println("Total words:"+words.size()); // 125901
BSTSet<String> bst = new BSTSet<>();
for(String word:words) {
bst.add(word);
}
System.out.println("Total different words: "+bst.getSize()); // 6530
}
else {
throw new IllegalArgumentException("Read failed");
}
}
可以看到，完成二分搜索樹的增刪邏輯之后吠架，借助二分搜索樹實(shí)現(xiàn)集合是非常簡(jiǎn)單的芙贫，下面考慮用鏈表實(shí)現(xiàn)集合。
1.2 基于鏈表的集合實(shí)現(xiàn)
基于之前構(gòu)造的鏈表結(jié)構(gòu)傍药，也可以實(shí)現(xiàn)集合功能磺平，只不過在添加元素時(shí)，需要先判斷鏈表中是否已包含該元素拐辽，另外拣挪，鏈表集合中的泛型無需實(shí)現(xiàn)比較器：
import java.util.ArrayList;
public class LinkedListSet<E> implements Set<E> {
private LinkedList<E> list;
public LinkedListSet() {
list = new LinkedList<>();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public boolean contains(E e) {
return list.contains(e);
}
@Override
public void add(E e) {
// 加一句判斷，若列表中已包含元素俱诸，則不添加元素
if(!list.contains(e))
list.addFirst(e);
}
@Override
public void remove(E e) {
list.removeElement(e);
}
}
可以采用相同的測(cè)試函數(shù)來驗(yàn)證上述實(shí)現(xiàn)的有效性：
public static void main(String[] args) {
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
System.out.println("Total words:"+words.size()); // 125901
LinkedListSet<String> list = new LinkedListSet<>();
for(String word:words) {
list.add(word);
}
System.out.println("Total different words: "+list.getSize()); // 6530
}
else {
throw new IllegalArgumentException("Read failed");
}
}
運(yùn)行時(shí)可以很明顯感覺到將鏈表作為底層結(jié)構(gòu)菠劝，耗時(shí)要比二分搜索樹長(zhǎng)很多。
1.3 時(shí)間復(fù)雜度分析
對(duì)于底層結(jié)構(gòu)是鏈表的集合睁搭，其時(shí)間復(fù)雜度與鏈表的時(shí)間復(fù)雜度相關(guān)：
- 增(add)：鏈表本身添加操作的時(shí)間復(fù)雜度為O(1)赶诊，然而為實(shí)現(xiàn)集合元素不能重復(fù)的特性，添加元素時(shí)需要先遍歷一遍鏈表介袜，判斷是否包含待添加元素甫何，因此時(shí)間復(fù)雜度為O(n)
- 刪(remove)：鏈表的刪除操作需要找到待刪除元素的前一節(jié)點(diǎn)，因此時(shí)間復(fù)雜度為O(n)
- 查(contains)： 需要遍歷鏈表所有元素遇伞，復(fù)雜度為O(n)
下面分析二分搜索樹的時(shí)間復(fù)雜度辙喂，二分搜索樹本質(zhì)上是一種順序結(jié)構(gòu)，增刪查操作與二分搜索樹的深度h有關(guān)：
image.png
考慮二分搜索樹中節(jié)點(diǎn)個(gè)數(shù)n與深度h的關(guān)系：
- 對(duì)于一個(gè)滿二叉樹，除了葉子節(jié)點(diǎn)巍耗，每個(gè)節(jié)點(diǎn)都有兩個(gè)孩子
image.png
可以看到秋麸，第層有
個(gè)節(jié)點(diǎn)，第
個(gè)節(jié)點(diǎn)炬太，第
個(gè)節(jié)點(diǎn)灸蟆，...，第
層有
個(gè)節(jié)點(diǎn)亲族，因此對(duì)于滿二叉樹炒考，
增刪查的時(shí)間復(fù)雜度為
- 上面滿二叉樹是一種平均情況，對(duì)于極端的情況霎迫，二分搜索樹有可能退化成鏈表斋枢，此時(shí)時(shí)間復(fù)雜度為
image.png
下面的測(cè)試函數(shù)用來簡(jiǎn)單測(cè)試鏈表集合類與二分搜索樹集合類的效率：
public static double testSet(Set<String> set,String filename) {
long startTime = System.nanoTime();
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile(filename, words)) {
System.out.println("Total words:"+words.size());
for(String word:words) {
set.add(word);
}
System.out.println("Total different words: "+set.getSize());
}
long endTime = System.nanoTime();
return (endTime - startTime)/ 1000000000.0;
}
public static void main(String[] args) {
String filename = "pride-and-prejudice.txt";
BSTSet<String> bst = new BSTSet<String>();
double time1 = testSet(bst,filename);
System.out.println("BST set:"+time1+"s"); // 0.3
System.out.println();
LinkedListSet<String> linkedListSet = new LinkedListSet<>();
double time2 = testSet(linkedListSet, filename);
System.out.println("LinkedList set:"+time2+"s"); // 4.0355
}
2. leetcode中與集合有關(guān)的問題
804
國(guó)際摩爾斯密碼定義一種標(biāo)準(zhǔn)編碼方式，將每個(gè)字母對(duì)應(yīng)于一個(gè)由一系列點(diǎn)和短線組成的字符串知给， 比如: "a" 對(duì)應(yīng) ".-", "b" 對(duì)應(yīng) "-...", "c" 對(duì)應(yīng) "-.-.", 等等瓤帚。
所有26個(gè)英文字母對(duì)應(yīng)的摩爾斯密碼表如下：
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
給定一個(gè)單詞列表，每個(gè)單詞可以寫成每個(gè)字母對(duì)應(yīng)摩爾斯密碼的組合涩赢。例如戈次，"cab" 可以寫成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的結(jié)合)筒扒。我們將這樣一個(gè)連接過程稱作單詞翻譯怯邪。不同的單詞有可能被翻譯為相同的摩爾斯密碼，要求返回單詞列表中不同摩爾斯密碼的數(shù)量花墩。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-morse-code-words
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有擎颖。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處观游。
使用集合很容易解答該題请敦，遍歷單詞列表昼窗，將每個(gè)單詞的翻譯結(jié)果放入一個(gè)集合中，由于集合不能存放相同的元素键俱，因此王凑，遍歷完單詞列表后搪柑，集合中元素的數(shù)量即為不同摩爾斯密碼的數(shù)量。
-
應(yīng)用Java集成的TreeSet類
import java.util.TreeSet; // leetcode 804 public class Solution { public int uniqueMorseRepresentations(String[] words) { String[] codes = {".-","-...","-.-.","-..",".","..-.", "--.","....","..",".---","-.-",".-..","--","-.", "---",".--.","--.-",".-.","...","-","..-","...-", ".--","-..-","-.--","--.."}; TreeSet<String> treeSet = new TreeSet<>(); for(String word:words) { StringBuilder res = new StringBuilder(); for(int i=0;i<word.length();i++) { // 將單詞索引為i位置的字母翻譯成摩爾斯密碼索烹，追加到翻譯結(jié)果中 res.append(codes[word.charAt(i)-'a']); } treeSet.add(res.toString()); } return treeSet.size(); } } -
使用上一節(jié)中自己創(chuàng)建的Set類
import java.util.Comparator; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Solution { public int uniqueMorseRepresentations(String[] words) { String[] codes = {".-","-...","-.-.","-..",".","..-.", "--.","....","..",".---","-.-",".-..","--","-.", "---",".--.","--.-",".-.","...","-","..-","...-", ".--","-..-","-.--","--.."}; BSTSet<String> set = new BSTSet<>(); for(String word:words) { StringBuilder res = new StringBuilder(); for(int i=0;i<word.length();i++) { // 將單詞索引為i位置的字母翻譯成摩爾斯密碼工碾，追加到翻譯結(jié)果中 res.append(codes[word.charAt(i)-'a']); } set.add(res.toString()); } return set.getSize(); } }
349
給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集百姓。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [9,4]
說明:
- 輸出結(jié)果中的每個(gè)元素一定是唯一的渊额。
- 我們可以不考慮輸出結(jié)果的順序。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)旬迹，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處火惊。
-
使用基于二分搜索樹構(gòu)造的集合類解決該問題：
class Solution { public int[] intersection(int[] nums1, int[] nums2) { BSTSet<Integer> bstSet = new BSTSet<>(); // 先將第一個(gè)數(shù)組中的元素添加到集合中 for(int num:nums1) { bstSet.add(num); } ArrayList<Integer> arr = new ArrayList<>(); for(int num:nums2) { // 遍歷第二個(gè)數(shù)組中的所有元素，如果存在于集合中奔垦，則將該元素添加到數(shù)組列表中 // 同時(shí)從集合中移除該元素 if(bstSet.contains(num)) { arr.add(num); bstSet.remove(num); } } int[] res = new int[arr.size()]; for(int i = 0;i<arr.size();i++) { res[i] = arr.get(i); } return res; } }
3. 映射
映射（Map）是一種存儲(chǔ)（鍵屹耐，值）數(shù)據(jù)對(duì)的數(shù)據(jù)結(jié)構(gòu)（key,value），鍵在映射中是不可重復(fù)的椿猎，通過鍵（key）來尋找值（value）惶岭。映射在實(shí)際生活中同樣具有廣泛的應(yīng)用：
- 字典中一個(gè)單詞對(duì)應(yīng)一個(gè)釋義
- 名冊(cè)中一個(gè)身份證號(hào)對(duì)應(yīng)一個(gè)人
- 車輛管理中一個(gè)車牌對(duì)應(yīng)一輛車
回顧之前介紹的鏈表和二分搜索樹的結(jié)構(gòu)：
// 鏈表中的節(jié)點(diǎn)結(jié)構(gòu) // 二分搜索樹中的節(jié)點(diǎn)結(jié)構(gòu)
class Node{ class Node{
E e; E e;
Node next; Node left;
} Node right;
}
很容易用這樣的結(jié)構(gòu)來實(shí)現(xiàn)映射機(jī)制，只需在節(jié)點(diǎn)中存儲(chǔ)一對(duì)數(shù)據(jù)即可：
// 存儲(chǔ)鍵值對(duì)的鏈表 // 存儲(chǔ)鍵值對(duì)的二分搜索樹
class Node{ class Node{
K key; K key;
V value; V value;
Node next; Node left;
} Node right;
}
一個(gè)Map應(yīng)該包含如下基本接口：
public interface Map<K,V> {
// 1. 獲取map中鍵值對(duì)個(gè)數(shù)
public int getSize();
// 2. 判斷map是否為空
public boolean isEmpty();
// 3. 添加鍵值對(duì)
public void add(K key,V value);
// 4. 刪除key對(duì)應(yīng)的鍵值對(duì)犯眠，返回value
public V remove(K key);
// 5. 更新key對(duì)應(yīng)的value
public void set(K key,V value);
// 6. 查詢key對(duì)應(yīng)的值
public V get(K key);
// 7. 判斷是否包含指定的key
public boolean contains(K key);
}
3.1 使用鏈表實(shí)現(xiàn)Map
-
首先使用鏈表來實(shí)現(xiàn)Map按灶，對(duì)鏈表節(jié)點(diǎn)結(jié)構(gòu)進(jìn)行修改，注意增加泛型支持：
public class LinkedListMap<K,V> implements Map<K,V> { // 私有結(jié)點(diǎn)類阔逼，存儲(chǔ)鍵值對(duì) private class Node{ private K key; private V value; private Node next; public Node(K key, V value, Node next) { this.key = key; this.value = value; this.next = next; } public Node(K key,V value){ this(key,value,null); } public Node() { this(null,null,null); } @Override public String toString() { return "Key: "+key.toString()+"Value:"+value.toString(); } } private Node dummyHead; private int size; } -
簡(jiǎn)單函數(shù)的實(shí)現(xiàn)
// 1. 獲取map中鍵值對(duì)個(gè)數(shù) public int getSize(){ return size; } // 2. 判斷map是否為空 public boolean isEmpty() { return size == 0; } // 私有成員函數(shù)兆衅，根據(jù)key找到所在節(jié)點(diǎn) private Node getNode(K key) { Node cur = dummyHead.next; while(cur!=null) { if(cur.key.equals(key)) { return cur; } cur = cur.next; } return null; }-
根據(jù)鍵查詢
// 6. 判斷是否包含指定的key @Override public boolean contains(K key) { Node node = getNode(key); return node != null; } // 7. 查詢key對(duì)應(yīng)的值 @Override public V get(K key) { Node node = getNode(key); return node.value; }
-
-
更新/修改
// 5. 更新key對(duì)應(yīng)的value @Override public void set(K key, V value) { Node node = getNode(key); if(node!=null) { node.value = value; Node preNode = dummyHead.next; while(preNode.next!=null) { // 找到待更新結(jié)點(diǎn)的前一結(jié)點(diǎn) if(preNode.next.key.equals(key)) { node.next = preNode.next.next; preNode.next = node; return; } preNode = preNode.next; } } // node.value = value; // 需事先判斷Map中是否存在該鍵 } -
添加元素
// 3. 添加新的鍵值對(duì) @Override public void add(K key, V value) { if(contains(key)) { // 如果已包含該鍵，更新該鍵對(duì)應(yīng)的值 set(key,value); } else { // 如果不包含該鍵嗜浮，添加到鏈表頭 Node node = new Node(key,value); node.next = dummyHead.next; dummyHead.next = node; size++; } } -
刪除元素
// 4. 刪除key對(duì)應(yīng)的鍵值對(duì)羡亩，返回value @Override public V remove(K key) { Node pre = dummyHead; Node delNode = new Node(); // 從虛擬頭節(jié)點(diǎn)出發(fā)，找到待刪除元素的前一節(jié)點(diǎn) while(pre.next!=null) { if(pre.next.key.equals(key)) break; pre = pre.next; } // 如果找到的前一節(jié)點(diǎn)不是最后一個(gè)元素危融，則執(zhí)行刪除操作 if(pre.next!=null) { delNode = pre.next; pre.next = delNode.next; delNode.next = null; size --; } return delNode.value; }
3.2 leetcode中與Map相關(guān)的問題
給定兩個(gè)數(shù)組畏铆，編寫一個(gè)函數(shù)來計(jì)算它們的交集。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說明：
輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)吉殃，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致辞居。
我們可以不考慮輸出結(jié)果的順序。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有蛋勺。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)瓦灶，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
-
利用基于鏈表構(gòu)造的映射類來解決問題
public class Solution { public static int[] intersect(int[] nums1, int[] nums2) { LinkedListMap<Integer,Integer> linkedListMap = new LinkedListMap<Integer,Integer>(); // 遍歷第一個(gè)數(shù)組中的元素抱完，將元素及其對(duì)應(yīng)出現(xiàn)的次數(shù)存入映射中 for(int num:nums1) { // 如果是之前添加過的元素贼陶，將元素出現(xiàn)的次數(shù)+1 if(linkedListMap.contains(num)) { linkedListMap.set(num, linkedListMap.get(num)+1); } // 如果之前沒有添加過，以出現(xiàn)次數(shù)為1添加進(jìn)映射中 else linkedListMap.add(num, 1); } ArrayList<Integer> arr = new ArrayList<>(); for(int num:nums2) { // 遍歷第二個(gè)數(shù)組中的元素巧娱，如果包含在映射中碉怔，加入數(shù)組 列表中 if(linkedListMap.contains(num)) { // 如果該元素的次數(shù)大于1，加入數(shù)組列表禁添，同時(shí)將出現(xiàn)次數(shù)減1 if(linkedListMap.get(num)>=1) { arr.add(num); linkedListMap.set(num, linkedListMap.get(num)-1); } // 如果該元素次數(shù)是0撮胧，則將其從映射中移除 else linkedListMap.remove(num); } } int[] res = new int[arr.size()]; for(int i = 0;i<arr.size();i++) { res[i] = arr.get(i); } return res; } }
3.3 使用二分搜索樹實(shí)現(xiàn)Map
-
支持泛型的二分搜索樹基本結(jié)構(gòu)，注意鍵的可比較性
public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> { // 私有結(jié)點(diǎn)類 private class Node{ private K key; private V value; private Node left,right; public Node(K key, V value) { this.key = key; this.value = value; left = null; right = null; } @Override public String toString() { return "Key: "+key.toString()+"Value:"+value.toString(); } } private Node root; private int size; public BSTMap() { root = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } } -
添加元素
// 向二分搜索樹中添加新的元素（key,value） @Override public void add(K key, V value) { root = add(root,key,value); } // 私有添加方法老翘，遞歸向以node為根結(jié)點(diǎn)的二分搜索樹中添加鍵值對(duì) // 返回插入新結(jié)點(diǎn)后二分搜索樹的根 private Node add(Node node,K key,V value) { if(node==null) { node = new Node(key,value); size++; return node; } if(node.key.compareTo(key)>0) { node.left = add(node.left,key,value); } else if(node.key.compareTo(key)<0) { node.right = add(node.right,key,value); } else { // node.key.compareTo(key)==0 // 如果已存在該元素芹啥，做更新操作 node.value = value; } return node; } -
查詢操作
// 返回以node為根節(jié)點(diǎn)的二分搜索樹中锻离，key所在的節(jié)點(diǎn) private Node getNode(Node node,K key) { if(node==null) { return null; } if(node.key.compareTo(key)>0) { return getNode(node.left,key); } else if(node.key.compareTo(key)<0) { return getNode(node.right,key); } else { // node.key.compareTo(key)==0 return node; } } @Override public boolean contains(K key) { return getNode(root,key)!=null; } @Override public V get(K key) { Node node = getNode(root,key); return (node == null)?null:node.value; } // 返回以node為根的二分搜索樹的最小值所在的節(jié)點(diǎn) private Node minimize(Node node) { if(node.left==null) { return node; } return minimize(node.left); } -
修改/更新
@Override public void set(K key, V newValue) { Node node = getNode(root,key); if(node==null) throw new IllegalArgumentException(key+" doesn't exist!"); node.value = newValue; } -
刪除
// 刪除掉以node為根的二分搜索樹中的最小節(jié)點(diǎn) // 返回刪除節(jié)點(diǎn)后新的二分搜索樹的根 private Node removeMin(Node node){ if(node.left == null) { Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } // 從二分搜索樹中刪除鍵為key的節(jié)點(diǎn) @Override public V remove(K key) { Node node = getNode(root,key); if(node!=null) { root = remove(root,key); } return node.value; } // 刪除掉以node為根的二分搜索樹中鍵為key的結(jié)點(diǎn) // 返回刪除節(jié)點(diǎn)后新的二分搜索樹的根 private Node remove(Node node,K key) { if(node==null) { return null; } if(node.key.compareTo(key)>0) { node.left = remove(node.left,key); return node; } else if(node.key.compareTo(key)<0) { node.right = remove(node.right,key); return node; } else { // node.key.compareTo(key)==0 // 待刪除結(jié)點(diǎn)右子樹為空的情況 if(node.right==null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // 待刪除結(jié)點(diǎn)左子樹為空的情況 if(node.left==null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } // 待刪除節(jié)點(diǎn)左右子樹均不為空的情況 // 找到比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn), 即待刪除節(jié)點(diǎn)右子樹的最小節(jié)點(diǎn) // 用這個(gè)節(jié)點(diǎn)頂替待刪除節(jié)點(diǎn)的位置 Node successor = minimize(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } }
3.4 兩種底層實(shí)現(xiàn)的比較
import java.util.ArrayList;
public class Main {
private static double testMap(Map<String, Integer> map, String filename){
long startTime = System.nanoTime();
System.out.println(filename);
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile(filename, words)) {
System.out.println("Total words: " + words.size());
for (String word : words){
if(map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);
}
System.out.println("Total different words: " + map.getSize());
System.out.println("Frequency of PRIDE: " + map.get("pride"));
System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
String filename = "pride-and-prejudice.txt";
BSTMap<String, Integer> bstMap = new BSTMap<>();
double time1 = testMap(bstMap, filename);
System.out.println("BST Map: " + time1 + " s"); // 0.1520 s
System.out.println();
LinkedListMap<String, Integer> linkedListMap = new LinkedListMap<>();
double time2 = testMap(linkedListMap, filename);
System.out.println("Linked List Map: " + time2 + " s"); // 9.7194 s
}
}
4. 總結(jié)
本節(jié)課主要學(xué)習(xí)了集合與映射兩種高級(jí)數(shù)據(jù)結(jié)構(gòu)，分別以鏈表和二分搜索樹為底層結(jié)構(gòu)實(shí)現(xiàn)了這兩種數(shù)據(jù)結(jié)構(gòu)叁征，并對(duì)存取效率進(jìn)行了比較纳账，存取效率與底層實(shí)現(xiàn)結(jié)構(gòu)相關(guān)，以二分搜索樹為底層結(jié)構(gòu)的數(shù)據(jù)存取效率更高捺疼，這是因?yàn)槎炙阉鳂涞拇嫒r(shí)間復(fù)雜度為疏虫，遠(yuǎn)小于鏈表的時(shí)間復(fù)雜度
。集合與映射在實(shí)際生活中的應(yīng)用非常廣泛啤呼，可以用來實(shí)現(xiàn)很多復(fù)雜任務(wù)卧秘。
