作者主頁(yè)：paper jie_博客
本文作者：大家好，我是paper jie，感謝你閱讀本文，歡迎一建三連哦。
本文錄入于《JAVA數(shù)據(jù)結(jié)構(gòu)》專欄，本專欄是針對(duì)于大學(xué)生，編程小白精心打造的。筆者用重金(時(shí)間和精力)打造，將javaSE基礎(chǔ)知識(shí)一網(wǎng)打盡，希望可以幫到讀者們哦。
其他專欄：《算法詳解》《C語(yǔ)言》《javaSE》等
內(nèi)容分享：本期將會(huì)分享java數(shù)據(jù)結(jié)構(gòu)中的二叉搜索樹(shù)與Java集合中的Set和Map
目錄
什么是搜索樹(shù)
搜索樹(shù)的模擬實(shí)現(xiàn)
查找功能
代碼實(shí)現(xiàn)
畫(huà)圖分析
新增功能
具體代碼
畫(huà)圖分析
刪除功能
具體代碼
畫(huà)圖分析
搜索樹(shù)的性能
搜索樹(shù)與Java類集合的關(guān)系
Set和Map
概念
模型
Map
Map.Entry,v>
Map的常用方法
TreeMap和HashMap的比較
Set
Set的常用方法
TreeSet和HashMap的比較
什么是搜索樹(shù)
搜索樹(shù)又名二叉搜索樹(shù)，它是一顆完全二叉樹(shù)，且：
左樹(shù)不為空的話，則左子樹(shù)上的所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
右樹(shù)不為空的話，則右子樹(shù)上的所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
它的左右子樹(shù)也是搜索樹(shù)
搜索樹(shù)的模擬實(shí)現(xiàn)
查找功能
實(shí)現(xiàn)這個(gè)功能就可以利用它的性質(zhì)，比根節(jié)點(diǎn)的小的數(shù)在左邊，比根節(jié)點(diǎn)大的數(shù)在右邊，通過(guò)遍歷的方式一直查找，要是遇到了null，代表就沒(méi)有這個(gè)數(shù)。
代碼實(shí)現(xiàn)
//查找元素
//查找復(fù)雜度：O(logN)
//最壞情況：O(N)
public boolean search(int node) {
if(root == null) {
return false;
}
TreeNode cur = root;
while(cur != null) {
if(node < cur.val) {
cur = cur.left;
}else if(node > cur.val) {
cur = cur.right;
}else {
return true;
}
}
return false;
}畫(huà)圖分析
新增功能
新增節(jié)點(diǎn)，我們就分兩種情況，一種沒(méi)有節(jié)點(diǎn)，一種有節(jié)點(diǎn)，但大致開(kāi)始用cur遍歷找到需要插入的位置，再用一個(gè)prev記住cur的前一個(gè)節(jié)點(diǎn)。且相同是不需要添加的。當(dāng)cur等于null的時(shí)候，就用prev來(lái)判斷它大于key，就將新增節(jié)點(diǎn)放在它的左邊不然就放在右邊
具體代碼
//新增元素
public boolean push(int node) {
if(root == null) {
root = new TreeNode(node);
return true;
}
TreeNode cur = root;
TreeNode prve = null;
while(cur != null) {
if(node < cur.val) {
prve = cur;
cur = cur.left;
}else if(node > cur.val){
prve = cur;
cur = cur.right;
}else {
return false;
}
}
TreeNode treeNode = new TreeNode(node);
if(prve.val > node) {
prve.left = treeNode;
}else {
prve.right = treeNode;
}
return true;
}畫(huà)圖分析
刪除功能
刪除就比較復(fù)雜一點(diǎn)，得分幾種情況，而這幾種情況中又得細(xì)分：
當(dāng)需要?jiǎng)h除的節(jié)點(diǎn)左邊沒(méi)有元素
1 需要?jiǎng)h除的是頭節(jié)點(diǎn)
2 需要?jiǎng)h除的在父節(jié)點(diǎn)的左邊
3 需要?jiǎng)h除的節(jié)點(diǎn)在父節(jié)點(diǎn)的右邊
當(dāng)需要?jiǎng)h刪出的節(jié)點(diǎn)右邊沒(méi)有元素
1 需要?jiǎng)h除的是頭節(jié)點(diǎn)
2 需要?jiǎng)h除的在父節(jié)點(diǎn)的左邊
3 需要?jiǎng)h除的節(jié)點(diǎn)在父節(jié)點(diǎn)的右邊
當(dāng)需要?jiǎng)h除的節(jié)點(diǎn)兩邊都有元素
這里是比較難處理的，我們不能直接刪除這個(gè)結(jié)點(diǎn)，這里我們使用替換法：找到刪除節(jié)點(diǎn)右邊的最小節(jié)點(diǎn)，將最小節(jié)點(diǎn)的值賦值給需要?jiǎng)h除的那個(gè)元素，再將最小節(jié)點(diǎn)刪除，在刪除這個(gè)最小節(jié)點(diǎn)的時(shí)候我們也要考慮：
它的左邊有沒(méi)有元素，它的右邊有沒(méi)有元素，還是左右都沒(méi)有元素
具體代碼
//刪除元素
public boolean poll(int key) {
TreeNode cur = root;
TreeNode parent = null;
while(cur != null) {
if(key < cur.val) {
parent = cur;
cur = cur.left;
}else if(key > cur.val) {
parent = cur;
cur = cur.right;
}else {
removeNode(cur, parent);
return true;
}
}
return false;
}
private void removeNode(TreeNode cur, TreeNode parent) {
//刪除節(jié)點(diǎn)左邊為空
if(cur.left == null) {
if(cur == root) {
root = root.right;
}else if(parent.left == cur) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
//刪除節(jié)點(diǎn)右邊為空
}else if(cur.right == null) {
if(root == cur) {
root = root.left;
}else if(parent.left == cur) {
parent.left = cur.left;
}else {
parent.right = cur.left;
}
//都不為空
}else {
TreeNode xparent = cur;
TreeNode x = cur.right;
while(x.left != null) {
xparent = x;
x = x.left;
}
cur.val = x.val;
if(xparent.left == x) {
xparent.left = x.right;
}else {
xparent.right = x.right;
}
}
}
}
畫(huà)圖分析
搜索樹(shù)的性能
這里我們可以把查找的效率看做整個(gè)搜索樹(shù)的性能，因?yàn)椴还苁切略龊蛣h除都是需要查找的嘛。
對(duì)于搜索樹(shù)，我們知道，它就是一顆二叉樹(shù)，所以比較的次數(shù)就是樹(shù)的深度。但是所有情況都是這樣嘛，這里會(huì)因?yàn)橐粋€(gè)數(shù)據(jù)集合，如果他們數(shù)據(jù)插入的次序不一樣，則會(huì)得到不一樣的數(shù)據(jù)結(jié)構(gòu)，比如下圖：
這里我們就知道了，在最壞情況下搜索樹(shù)會(huì)退化成一個(gè)鏈表所以：
最好情況時(shí)間復(fù)雜度：O(logN)
最壞情況時(shí)間復(fù)雜度：O(N)
搜索樹(shù)與Java類集合的關(guān)系
Java中的TreeMap和TreeSet就是利用搜索樹(shù)實(shí)現(xiàn)的，但是呢它們底層使用的是搜索樹(shù)的進(jìn)化再進(jìn)化版紅黑樹(shù)（搜索樹(shù) - LAV樹(shù) - 紅黑樹(shù) ），LAV樹(shù)就是對(duì)搜索樹(shù)的改進(jìn)，遇到鏈表情況下它就是翻轉(zhuǎn)這個(gè)鏈表，讓他變成一個(gè)高度平衡的搜索樹(shù)，而紅黑樹(shù)是在這個(gè)基礎(chǔ)加上顏色一節(jié)紅黑樹(shù)性質(zhì)的驗(yàn)證進(jìn)一步的提高了它的效率。
Set和Map
概念
Map和Set是一種專門用來(lái)進(jìn)行搜索的容器或者數(shù)據(jù)結(jié)構(gòu)，它的搜索效率和實(shí)現(xiàn)它們的子類有關(guān)。一般比較簡(jiǎn)單的搜索方式有：
直接遍歷，復(fù)雜度為O(N),效率比較底下
二分查找，復(fù)雜度為O(logN),但它麻煩的是必須是有序的
而這些搜索方式只適合靜態(tài)的搜索，但對(duì)于區(qū)間這種插入和刪除的操作他們就不行了，這種就屬于動(dòng)態(tài)搜索方式。Map和Set就是用來(lái)針對(duì)這種的動(dòng)態(tài)查找的集合容器
模型
這集合中，一般把搜索的數(shù)據(jù)稱為關(guān)鍵字Key和關(guān)鍵字的對(duì)應(yīng)值Value，這兩個(gè)稱為鍵值對(duì)，一般有兩種模型：
純Key模型，即只需要一個(gè)數(shù)據(jù)，比如：
查找手機(jī)里面有沒(méi)有這個(gè)聯(lián)系人
Key-Value模型，比如：
查找這個(gè)篇文章里面這個(gè)詞出現(xiàn)了幾次 （詞，出現(xiàn)的次數(shù)）
Map就是Key-Value模型，Set是純Key模型
Map接口下繼承了HashMap和TreeMap兩個(gè)類，而Set接口下繼承了TreeSet和HashSet兩個(gè)類
TreeMap和TreeSet底層是紅黑樹(shù)，而HashMap和HashSet底層是哈希表
Map
Map是一個(gè)接口，它沒(méi)有和其他幾個(gè)類一樣繼承Collection，它存儲(chǔ)的是<K,V>鍵值對(duì)，且K是唯一·的，V可以重復(fù)
Map.Entry<K,V>
Map.Entry<K,V>在Map中是一個(gè)內(nèi)存類， 它是用來(lái)Map內(nèi)部實(shí)現(xiàn)存放<K,V>鍵值對(duì)映射關(guān)系的，它還提供了Key，value的設(shè)置和Key的比較方式：
| 方法 | 解釋 |
| K getKey() | 返回Entry中的Key |
| K getValue() | 返回Entry中的Value |
| K setValue(V value) | 設(shè)置Entry中的value |
這里要注意它沒(méi)有提供設(shè)置Key的方法
Map的常用方法
注意事項(xiàng)：
1 Map是一個(gè)接口，它不可以實(shí)例化對(duì)象，要實(shí)例化只能實(shí)例化它的子類TreeMap或者HashMap
2 Map中存放鍵值對(duì)里的Key是唯一的，value是可以重復(fù)的
3 在TreeMap中插入鍵值對(duì)時(shí)，Key不能為空，否則就會(huì)拋NullPointerExecption異常，value可以為空。但是HashMap的Key和value都可以為空
4 Map中的Key是可以分離出來(lái)的，存儲(chǔ)到Set中來(lái)進(jìn)行訪問(wèn)（因?yàn)镵ey不能重合）
5 Map中的value也可以分離出來(lái)，存放到Collection的任何一個(gè)子集合中，但是value可能會(huì)重合?
6 Map中的鍵值對(duì)Key不能直接修改，value可以修改，如果要修改Key，只能先將Key先刪除，再來(lái)插入
TreeMap和HashMap的比較
| Map底層結(jié)構(gòu) | TreeMap | HashMap |
| 底層結(jié)構(gòu) | 紅黑樹(shù) | 哈希桶 |
| 時(shí)間復(fù)雜度 | O(logN) | O(1) |
| 是否有序 | 有序 | 無(wú)序 |
| 線程安全 | 不安全 | 不安全 |
| 插入/刪除/添加的區(qū)別 | 需要進(jìn)行數(shù)據(jù)間的比較 | 直接通過(guò)計(jì)算哈希函數(shù)來(lái)確定地址 |
| 應(yīng)用場(chǎng)景 | 在需要有序的場(chǎng)景下 | 不關(guān)心是否有序，更需要效率的場(chǎng)景下 |
| 比較和重寫 | Key必須是可以比較的，不可以為null | 自定義類型需要重寫哈希Code方法和equals方法 |
使用栗子：
HashMap：
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("豬八戒", 500);
map.put("孫悟空", 550);
map.put("唐僧", 40);
map.put("沙和尚", 100);
map.put("白龍馬", 300);
System.out.println(map.get("豬八戒"));
System.out.println(map.remove("八戒"));
System.out.println(map.get("豬八戒"));
Set<Map.Entry<String, Integer>> set = map.entrySet();
for(Map.Entry<String, Integer> entry : set) {
System.out.println(entry);
}
System.out.println(map.containsKey("豬八戒"));
}TreeMap：
public static void TestMap() {
Map<String, String> m = new TreeMap<>();
// put(key, value):插入key-value的鍵值對(duì)
// 如果key不存在，會(huì)將key-value的鍵值對(duì)插入到map中,返回null
m.put("林沖", "豹子頭");
m.put("魯智深", "花和尚");
m.put("武松", "行者");
m.put("宋江", "及時(shí)雨");
String str = m.put("李逵", "黑旋風(fēng)");
System.out.println(m.size());
System.out.println(m);
// put(key,value): 注意key不能為空，但是value可以為空
// key如果為空，會(huì)拋出空指針異常
// m.put(null, "花名");
str = m.put("無(wú)名", null);
System.out.println(m.size());
// put(key, value):
// 如果key存在，會(huì)使用value替換原來(lái)key所對(duì)應(yīng)的value，返回舊value
str = m.put("李逵", "鐵牛");
// get(key): 返回key所對(duì)應(yīng)的value
// 如果key存在，返回key所對(duì)應(yīng)的value
// 如果key不存在，返回null
System.out.println(m.get("魯智深"));
System.out.println(m.get("史進(jìn)"));
//GetOrDefault(): 如果key存在，返回與key所對(duì)應(yīng)的value，如果key不存在，返回一個(gè)默認(rèn)值
System.out.println(m.getOrDefault("李逵", "鐵牛"));
System.out.println(m.getOrDefault("史進(jìn)", "九紋龍"));
System.out.println(m.size());
//containKey(key)：檢測(cè)key是否包含在Map中，時(shí)間復(fù)雜度：O(logN)
// 按照紅黑樹(shù)的性質(zhì)來(lái)進(jìn)行查找
// 找到返回true，否則返回false
System.out.println(m.containsKey("林沖"));
System.out.println(m.containsKey("史進(jìn)"));
// containValue(value): 檢測(cè)value是否包含在Map中，時(shí)間復(fù)雜度: O(N)
// 找到返回true，否則返回false
System.out.println(m.containsValue("豹子頭"));
System.out.println(m.containsValue("九紋龍"));
// 打印所有的key
// keySet是將map中的key防止在Set中返回的
for (String s : m.keySet()) {
System.out.print(s + " ");
}
System.out.println();
// 打印所有的value
// values()是將map中的value放在collect的一個(gè)集合中返回的
for (String s : m.values()) {
System.out.print(s + " ");
}
System.out.println();
// 打印所有的鍵值對(duì)
// entrySet(): 將Map中的鍵值對(duì)放在Set中返回了
for (Map.Entry<String, String> entry : m.entrySet()) {
System.out.println(entry.getKey() + "--->" + entry.getValue());
}
System.out.println();
}Set
Set和Map的不同點(diǎn)就在于Set是繼承于Collection接口類的，Set只存儲(chǔ)了Key。
Set的常用方法
注意事項(xiàng)：
1 Set是繼承Collection的一個(gè)接口
2 Set只存儲(chǔ)Key，且要求Key是唯一的
3 TreeSet的底層是使用了Map來(lái)實(shí)現(xiàn)的，其使用Key與Object的一個(gè)默認(rèn)對(duì)象作為鍵值對(duì)插入到Map中
4 Set的最大特點(diǎn)就是去重
5 實(shí)現(xiàn)Set接口的常用類有TreeSet和HashSet，還有一個(gè)LinkedSet，它是在HashSet上維護(hù)了一個(gè)雙向鏈表來(lái)記入插入元素的次序
6 Set中的Key不能修改，如果要修改的話，呀先將原來(lái)的刪除，再重新插入
7 TreeSeet中不能插入null的Key，但HashSet可以
TreeSet和HashMap的比較
| Set底層結(jié)構(gòu) | TreeSet | HashSet |
| 底層結(jié)構(gòu) | 紅黑樹(shù) | 哈希桶 |
| 復(fù)雜度 | O(logN) | O(1) |
| 是否有序 | 有序 | 無(wú)序 |
| 線程安全 | 不安全 | 不安全 |
| 插入/刪除/查找區(qū)別 | 使用紅黑樹(shù)的性質(zhì)來(lái)插入和刪除的 | 使用哈希函數(shù)來(lái)計(jì)算插入和刪除的地址 |
| 比較和重寫 | Key必須可以比較，不能為null | 自定義類型需要重寫equals方法和HashCode方法 |
| 應(yīng)用場(chǎng)景 | 需要Key有序場(chǎng)景下 | 需要更高的時(shí)間性能 |
栗子：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-715138.html
public static void TestSet2(){
Set<String> s = new TreeSet<>();
// add(key): 如果key不存在，則插入，返回ture
// 如果key存在，返回false
boolean isIn = s.add("apple");
s.add("orange");
s.add("peach");
s.add("banana");
System.out.println(s.size());
System.out.println(s);
isIn = s.add("apple");
// add(key): key如果是空，拋出空指針異常
//s.add(null);
// contains(key): 如果key存在，返回true，否則返回false
System.out.println(s.contains("apple"));
System.out.println(s.contains("watermelen"));
// remove(key): key存在，刪除成功返回true
// key不存在，刪除失敗返回false
// key為空，拋出空指針異常
s.remove("apple");
System.out.println(s);
s.remove("watermelen");
System.out.println(s);
Iterator<String> it = s.iterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}這里文章中我們提到的HashMap和HashSet的底層 - 哈希桶，下一篇文章就會(huì)介紹，期待一下吧。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-715138.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】搜索樹(shù) 與 Java集合框架中的Set，Map的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
