20172324 2018-2019-1 《程序设计与数据结构》第七周学习总结
20172324 2018-2019-1 《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》第七周學(xué)習(xí)總結(jié)
教材學(xué)習(xí)內(nèi)容總結(jié)
概述
二叉查找樹是一種含有附加屬性的二叉樹，即其左孩子小于父節(jié)點(diǎn)，而父節(jié)點(diǎn)又小于等于其右孩子。
它是特殊的二叉樹：對(duì)于二叉樹，假設(shè)x為二叉樹中的任意一個(gè)結(jié)點(diǎn)，x節(jié)點(diǎn)包含關(guān)鍵字key，節(jié)點(diǎn)x的key值記為key[x]。如果y是x的左子樹中的一個(gè)結(jié)點(diǎn)，則key[y] <= key[x]；如果y是x的右子樹的一個(gè)結(jié)點(diǎn)，則key[y] >= key[x]。那么，這棵樹就是二叉查找樹。如下圖所示：
(04) 沒有鍵值相等的節(jié)點(diǎn)（no duplicate nodes）。
二叉查找樹的接口類繼承自二叉樹的接口類BinaryTreeADT，在其基礎(chǔ)上補(bǔ)充了一些操作方法
| addElement | 往樹中添加一個(gè)元素 |
| removeElement | 從樹中刪除一個(gè)元素 |
| removeAllOccurrences | 從樹中刪除所指定元素的任何存在 |
| removeMin | 刪除樹中最小元素 |
| removeMax | 刪除樹中最大元素 |
| findMin | 返回一個(gè)指向樹中的最小元素的引用 |
| findMax | 返回一個(gè)指向樹中的最大元素的引用 |
鏈表實(shí)現(xiàn)二叉查找樹
- 每個(gè)BinaryTreeNode對(duì)象要維護(hù)一個(gè)指向結(jié)點(diǎn)所存儲(chǔ)元素的引用，另外還要維護(hù)指向結(jié)點(diǎn)的每個(gè)孩子的引用。
- LinkedBinarySearchTree類提供了兩個(gè)構(gòu)造函數(shù)
addElement操作：根據(jù)二叉查找樹的性質(zhì)，插入一個(gè)節(jié)點(diǎn)的時(shí)候，如果根節(jié)點(diǎn)為空，就此節(jié)點(diǎn)作為根節(jié)點(diǎn)，如果根節(jié)點(diǎn)不為空，就要先和根節(jié)點(diǎn)比較，如果比根節(jié)點(diǎn)的值小，就插入到根節(jié)點(diǎn)的左子樹中，如果比根節(jié)點(diǎn)的值大就插入到根節(jié)點(diǎn)的右子樹中，如此遞歸下去，找到插入的位置。
例圖(插入65，黃色線為比較的軌跡)：
removeElement操作：
初始狀態(tài)：被刪除的節(jié)點(diǎn)只有左節(jié)點(diǎn)或者只有右節(jié)點(diǎn)，這種情況好辦，因?yàn)楣?jié)點(diǎn)在一條鏈上，沒有分叉，就像處理鏈表一樣把這個(gè)節(jié)點(diǎn)摘掉就行了。讓它的父節(jié)點(diǎn)關(guān)聯(lián)它的子節(jié)點(diǎn)，它的子節(jié)點(diǎn)關(guān)聯(lián)它的父節(jié)點(diǎn)就完事。如果它沒有父節(jié)點(diǎn)，說明它是根節(jié)點(diǎn)，直接將其子節(jié)點(diǎn)作為根節(jié)點(diǎn)就行。
滿足這個(gè)情況的節(jié)點(diǎn)有 34, 70 兩個(gè)節(jié)點(diǎn)，這里以 70 為例，如下圖所示：
刪除 70 的時(shí)候，需要斷兩個(gè)關(guān)系，然后建立父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系，經(jīng)過上述操作后，節(jié)點(diǎn)狀態(tài)如下圖所示：- 被刪除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，這種情況也很簡(jiǎn)單，它是葉子節(jié)點(diǎn)，直接置空，將其父節(jié)點(diǎn)對(duì)應(yīng)的子節(jié)點(diǎn)也置空，就完事。
在我們圖中，符合這個(gè)條件的有 20,32,40,75,100，隨便找個(gè) 20 來演示刪除該節(jié)點(diǎn)：
這種情況是最簡(jiǎn)單的，我們只需要?jiǎng)h除該節(jié)點(diǎn)和父節(jié)點(diǎn)的關(guān)系即可。刪除的時(shí)候需要先判斷自己和父節(jié)點(diǎn)的關(guān)系是左側(cè)還是右側(cè)，如果父節(jié)點(diǎn)的左節(jié)點(diǎn)是自己，就清左側(cè)，否則就是右側(cè)。刪除后如下圖所示： 被刪除的節(jié)點(diǎn)有左右子節(jié)點(diǎn)。樹結(jié)構(gòu)中的所有節(jié)點(diǎn)按順序拍好的話，它的前驅(qū)和它的后繼兩個(gè)節(jié)點(diǎn)剛好在它左右緊挨著它。當(dāng)一個(gè)節(jié)點(diǎn)被刪除時(shí)，為了保證二叉樹的結(jié)構(gòu)不被破壞，要讓它的前驅(qū)或者后繼節(jié)點(diǎn)來代替它的位置，然后將它的前驅(qū)或者后繼節(jié)點(diǎn)同樣做刪除操作。
滿足同時(shí)存在左右節(jié)點(diǎn)的節(jié)點(diǎn)有 50,30,80,35 這 4 個(gè)節(jié)點(diǎn)，30 看起來更復(fù)雜，我們以 30 為例。
當(dāng)二叉查找樹以中序遍歷時(shí)，遍歷的結(jié)果是一個(gè)從小到大排列的順序，如下圖所示：
當(dāng)我們刪除 30 節(jié)點(diǎn)的時(shí)候，整個(gè)中序遍歷的結(jié)果中，從 32 開始都往前移動(dòng)了一位。32 是 30 的后繼節(jié)點(diǎn)，就是比 30 大的節(jié)點(diǎn)中最小的節(jié)點(diǎn)。當(dāng)某個(gè)節(jié)點(diǎn)存在右節(jié)點(diǎn)時(shí)，后繼結(jié)點(diǎn)就是右節(jié)點(diǎn)中的最小值，由于左側(cè)節(jié)點(diǎn)總比右側(cè)節(jié)點(diǎn)和父節(jié)點(diǎn)小，所以后繼節(jié)點(diǎn)一定沒有左節(jié)點(diǎn)。從這一個(gè)特點(diǎn)就能看出來，后繼結(jié)點(diǎn)有可能存在右節(jié)點(diǎn)，也有可能沒有任何節(jié)點(diǎn)。后繼結(jié)點(diǎn)還有一個(gè)特點(diǎn)，就是他比 30 的左節(jié)點(diǎn)大，比 30 所有的右節(jié)點(diǎn)都小，因此刪除 30 的時(shí)候，可以直接將后繼結(jié)點(diǎn) 32 的值（key）轉(zhuǎn)移到 30 節(jié)點(diǎn)上，然后刪除后繼結(jié)點(diǎn) 32。由于后繼結(jié)點(diǎn)最多只有一個(gè)子節(jié)點(diǎn)，因此刪除后繼節(jié)點(diǎn)時(shí)，就變成了 3 種情況中的前兩種。圖示如下：- removeAllOccurrences操作：可以看做調(diào)用了removeElement,當(dāng)在樹中找不到指定元素是，則拋出ElementNotFoundException異常，如果指定的元素不是Comparable，則removeAllOccurrences方法也會(huì)拋出ClassCaseException異常。只要樹中還含有目標(biāo)元素，就會(huì)再次調(diào)用removeElement方法。
- removeMin操作：最小元素在樹中位置的3種情形：
- 樹根沒有左孩子，樹根即為最小元素，樹根右孩子變成新的根結(jié)點(diǎn)；
- 樹的最左側(cè)結(jié)點(diǎn)為一片葉子，該葉子即為最小元素，設(shè)置其父結(jié)點(diǎn)的左孩子應(yīng)用為null；
- 樹的最左側(cè)結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)，設(shè)置其父結(jié)點(diǎn)的左孩子引用指向最小元素的右孩子。
用有序列表實(shí)現(xiàn)二叉查找樹
列表的一些常見操作：
| removeFirst | 刪除列表的首元素 | O(1) | O(logn) |
| removeLast | 刪除列表的末元素 | O(n) | O(logn) |
| remove | 刪除列表中的一個(gè)特定元素 | O(n) | O(logn) |
| first | 考察列表前端的那個(gè)元素 | O(1) | O(logn) |
| last | 考察列表末端的那個(gè)元素 | O(n) | O(logn) |
| contains | 判斷列表是否含有一個(gè)特定元素 | O(n) | O(logn) |
| is Empty | 判定列表是否為空 | O(1) | O(1) |
| size | 判定列表中的元素?cái)?shù)目 | O(1) | O(1) |
有序列表特有的操作：
| add | 向列表添加一個(gè)元素 | O(n) | O(logn) |
平衡二叉查找樹
如果沒有平衡假設(shè)，它的效率比鏈表的還低，因?yàn)槊總€(gè)結(jié)點(diǎn)還附帶額外的開銷。
- AVL樹的旋轉(zhuǎn)規(guī)律:
LL型
平衡二叉樹某一節(jié)點(diǎn)的左孩子的左子樹上插入一個(gè)新的節(jié)點(diǎn)，使得該節(jié)點(diǎn)不再平衡。這時(shí)只需要把樹向右旋轉(zhuǎn)一次即可，如圖所示，原A的左孩子B變?yōu)楦附Y(jié)點(diǎn)，A變?yōu)槠溆液⒆?#xff0c;而原B的右子樹變?yōu)锳的左子樹，注意旋轉(zhuǎn)之后Brh是A的左子樹RR型
平衡二叉樹某一節(jié)點(diǎn)的右孩子的右子樹上插入一個(gè)新的節(jié)點(diǎn)，使得該節(jié)點(diǎn)不再平衡。這時(shí)只需要把樹向左旋轉(zhuǎn)一次即可，如圖所示，原A右孩子B變?yōu)楦附Y(jié)點(diǎn)，A變?yōu)槠渥蠛⒆?#xff0c;而原B的左子樹Blh將變?yōu)锳的右子樹。LR型
平衡二叉樹某一節(jié)點(diǎn)的左孩子的右子樹上插入一個(gè)新的節(jié)點(diǎn)，使得該節(jié)點(diǎn)不再平衡。這時(shí)需要旋轉(zhuǎn)兩次，僅一次的旋轉(zhuǎn)是不能夠使二叉樹再次平衡。如圖所示，在B節(jié)點(diǎn)按照RR型向左旋轉(zhuǎn)一次之后，二叉樹在A節(jié)點(diǎn)仍然不能保持平衡，這時(shí)還需要再向右旋轉(zhuǎn)一次。
平衡二叉樹某一節(jié)點(diǎn)的右孩子的左子樹上插入一個(gè)新的節(jié)點(diǎn)，使得該節(jié)點(diǎn)不再平衡。同樣，這時(shí)需要旋轉(zhuǎn)兩次，旋轉(zhuǎn)方向剛好同LR型相反。
- 實(shí)現(xiàn)二叉查找樹：AVL樹
- 平衡因子：右子樹的高度減去左子樹的高度。
| 孩子的平衡因子<=-1 | 右旋 | 右左旋 |
| 孩子的平衡因子>=1 | 左右旋 | 左旋 |
- 實(shí)現(xiàn)二叉查找樹：紅黑樹
紅黑樹的特性:
（接下來的部分都讓我處于神游狀態(tài)，先把王老師的講解粘下來吧）
紅黑樹-插入:
紅黑樹-刪除：
過于復(fù)雜 放在教材學(xué)習(xí)問題中
教材學(xué)習(xí)中的問題和解決過程
問題1：根據(jù)二叉查找樹的定義，下面這個(gè)圖是否正確？
問題1解決方案：不正確，雖然它作為右子樹滿足大于等于它的父節(jié)點(diǎn)這一個(gè)要求，但它仍然是根結(jié)點(diǎn)左子樹。90大于56了，所以不滿足。可以放在99的左子樹
- 問題2：紅黑樹的刪除
問題2解決方案：我以為我會(huì)懂，但是我沒有，先放個(gè)博客鏈接在這里，以后慢慢理解紅黑樹的刪除（算法導(dǎo)論）
問題3：在課上提出來的一個(gè)問題，如下圖所示，該二叉樹不滿足紅黑二叉樹，一種方法是將10重新染色成黑色，再將7染色成紅色。現(xiàn)在問題來，能不能把10和18都染成黑色？
問題3解決方案：還在討論中
代碼托管
上周考試錯(cuò)題總結(jié)
無錯(cuò)題
點(diǎn)評(píng)過的同學(xué)博客和代碼
- 本周結(jié)對(duì)學(xué)習(xí)情況
- 結(jié)對(duì)同學(xué)學(xué)號(hào)21
- 本周結(jié)對(duì)學(xué)習(xí)情況
內(nèi)容詳略得當(dāng)；
代碼調(diào)試環(huán)節(jié)比較詳細(xì)，出現(xiàn)得問題都差不多
其他（感悟、思考等，可選）
學(xué)習(xí)進(jìn)度條
| 目標(biāo) | 5000行 | 30篇 | 400小時(shí) | |
| 第一周 | 0 | 1/1 | 20/20 | |
| 第二周 | 300/500 | 1/2 | 18/38 | |
| 第三周 | 300/600 | 1/3 | 18/38 | |
| 第四周 | 400/1000 | 2/5 | 18/38 | |
| 第五周 | 300/1300 | 1/6 | 18/38 | |
| 第六周 | 300/1300 | 3/9 | 18/38 | |
| 第七周 | 300/1300 | 3/9 | 18/38 |
參考資料
- 《Java程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)（第四版）》
- 二叉查找樹(三)之 Java的實(shí)現(xiàn)
- 紅黑樹的刪除（算法導(dǎo)論）
轉(zhuǎn)載于:https://www.cnblogs.com/amberR/p/9894955.html
總結(jié)
以上是生活随笔為你收集整理的20172324 2018-2019-1 《程序设计与数据结构》第七周学习总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 第三模块：面向对象（目录）
- 下一篇： 战争中人与武器哪个更重要？