java數據結構_Map和Set

1. 搜索樹

1.1 概念

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹：

若它的左子樹不為空，則左子樹上所有的結點都小于根結點的值
若它的右子樹不為空，則右子樹上所有的結點都大于根結點的值
它的左右子樹也都分別是二叉搜索樹

如下圖，就是一棵二叉搜索樹，二叉搜索樹的中序遍歷就是升序排列的

1.2 操作-查找

因為二叉搜索樹天然就帶有小的在左，大的在右的順序，所以在查找的時候更加方便，類似于有天然的二分查找

代碼實現如下：

1.3 操作 - 插入

按照二叉搜索樹，小的在左邊，大的在右邊邏輯確定插入位置，插入新結點。因為要插入的結點最終都是稱為葉子結點，所以光定義一個cur來表示要插入的結點還不夠，還要定義一個parent結點來表示cur的父親結點。

代碼如下：

但上面代碼的邏輯性還是有問題的，插入操作，并沒有考慮到，如果要插入的樹是一棵空樹，即root == null的情況，會出現空指針的異常。

修正：

1.4 操作 - 刪除（難）

搜索二叉樹的刪除是會發生很尷尬的情況的

如下圖：

如果要刪除值為8的結點，是很方便的，可以將7結點的right連接到值為9的結點。

但如果刪除的是左邊的值為1的結點呢？

刪除了之后，3的left是連接值為2的結點呢？還是連接值為0的結點呢？這樣就會出現尷尬的情況，采用的方法是替換法（也稱替罪羊法），即可以在要刪除的結點的右子樹中，尋找一個值最小的葉子節點，換個方式講是，找到要刪除的結點的右子樹的最左邊子樹（有點繞，可以多多理解一下），然后用這個最左邊子樹的值來覆蓋要刪除的結點的值，然后將最左邊子樹的結點刪除。注意是覆蓋，并不是將要刪除的結點真的刪除了，最終刪除的結點是要刪除的結點的右子樹的最左邊子樹的結點。

舉例：

如果要刪除的結點是值為90的結點

先找到90結點的右子樹為值為120的結點，然后再找到右子樹120的最左邊子樹，即值為95的結點，用這個結點的值95來覆蓋掉要刪除的結點90的值，然后刪除值為95的這個結點，如何刪除呢？如果值為95的這個結點仍有有右子樹呢？（注意：值為95的這個結點不可能再有左子樹了，因為我們要在前面的操作中找的就是 要刪除的結點的右子樹的最左子樹）就把值為95的結點的右子樹連接到值為120的結點的left上即可。

（上面只是一種方式，是找到要刪除結點的右子樹的最左側子樹，同理，也可以找到要刪除的結點的左子樹的最右側子樹，都相反一下即可，此處以右子樹的最左側左子樹來研究）

代碼實現：

設待刪除結點為cur，帶刪除結點的雙親結點為parent

在刪除中，有多種情況：

1.1情況：cur為root 且 cur.left == null 如下圖，此時直接將cur的left賦值為root即可

刪除后的效果：

1.2情況：cur不是root，cur.left == null，cur在左子樹上，即cur 是 parent.left 如下圖的效果，此時要刪除的結點是值為40的結點，直接parent.left = cur.right即可

1.3 情況：cur不是root，cur.left == null cur是parent.right，即cur在右子樹上，如下圖情況，則直接parent.right = cur.right即可

2.1情況 cur.right == null cur是root 則直接root = cur.left即可

2.2情況：cur不是root cur是parent.left? 且cur.right == null 則parent .left = cur.left

2.3 cur不是root cur是parent.right 且cur.right == null 則parent.right = cur.left

即使用前面所述的替代法。

代碼實現如下：

下面的代碼實現是前面的刪除邏輯

替代法因為要向下找到要刪除結點的右邊子樹的最左邊子樹，所以還需要一個尋找的邏輯，定義一個targetParent和target來尋找找最左子樹

當結束上面的while循環時候，即target指向的是最左子樹結點，然后cur.val = target.val進行覆蓋

如下圖所示：要刪除的結點是cur，t是要刪除節點的右邊結點的最左側結點，將cur的值覆蓋為95，然后將 t 結點刪掉（targetParent.left = target.right）（注意：刪除的時候不要直接targetParent.left = null 因為target可能有右節點也可能沒有右節點）

則代碼如下：

但上面代碼還是存在邏輯漏洞

如果是下圖的情況，cur為值為95的結點，在while循環結束后，t指向的是值為120的結點，直接執行targetParent.left = target.right 就亂套了

所以還應該加一個 if 條件即：if(taregt == targeParent.left)的時候，才能targetParent.left = target.right；否則應該是targetParent.right = target.right；

則替代法的實現代碼應該是：

完整的刪除代碼如下：

 public void remove(int val) {TreeNode cur = root;TreeNode parent = null;while(cur != null) {if(val < cur.val) {parent = cur;cur = cur.left;} else if(val > cur.val) {parent = cur;cur = cur.right;} else {//刪除的邏輯removeNode(parent,cur);return;}}}private void removeNode(TreeNode parent, TreeNode cur) {if(cur.left == null) {if(cur == root) {root = cur.right;} else if(cur == parent.right) {parent.right = cur.right;} else {parent.left = cur.right;}} else if(cur.right == null) {if(cur == root) {root = cur.left;} else if(cur == parent.right) {parent.right = cur.left;} else {parent.left = cur.left;}} else {//替代法：TreeNode targetParent = cur;TreeNode target = cur.right;while(target.left != null) {targetParent = target;target = target.left;}cur.val = target.val;if(targetParent.left == target) {targetParent.left = target.right;} else {targetParent.right = target.right;}}}

1.5 性能分析：

插入和刪除的操作都必須先查找，所以查找的效率可以代表二叉搜索樹中各個操作的性能。

對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找商都是結點在二叉搜索樹的函數，即節點越深，則比較的次數就越多。

但對于同一個關鍵碼集合，如果各關鍵碼插入的次序不同，可能得到不同結構的二叉搜索樹：

最好情況下：二叉搜索樹為完全二叉樹，平均比較次數為logN

最壞情況下：二叉搜索樹退化為單分支樹，其平均比較次數為：N / 2

可以及逆行改進，使得不管按照什么次序插入關鍵碼，都可以使得二叉搜索樹的性能最佳 -- 數據結構高階時候學習！

2. 搜索

2.1 概念及場景

Map和Set是一種專門用來進行搜索的容器或者數據結構，其搜索的效率與其具體的實例化子類有關。之前常見的搜索方式有：

直接遍歷：時間復雜度為O(N)，元素如果比較多的話，效率較低。
二分查找：時間復雜度為O(logN)，但搜索前必須要求序列是有序的

上述方式比較適合靜態類型的數據進行查找，即一般不會對區間內進行插入和刪除操作了，但在現實情況中的查找：1. 根據姓名查詢考試成績 2. 通訊錄，即根據姓名查詢聯系方式 3. 不重復集合，即需要先搜索關鍵字是否已經在集合中，可能在查找的過程中進行一些插入和刪除的操作，即動態查找，那上述兩種方式就不合適了，這里介紹的Map和Set是一種適合動態查找的集合容器。