20162325 金立清 S2 W8 C17
20162325 2017-2018-2 《程序設計與數據結構》第8周學習總結
教材學習內容概要
二叉查找樹是一棵二叉樹，對于其中的每個結點，左子樹上的元素小于父結點的值，而右子樹上的元素大于等于父結點的值。
最有效的二叉樹是平衡的，所以每次比較時可以排除一半的元素。
如果沒有其他操作，二叉查找樹的樹形由元素的添加次序來決定。
當從二叉查找樹中刪除元素時要考慮三種情形，其中的兩種比較簡單。
當從二叉查找樹中刪除兩個子結點的結點時，比較好的辦法是用它的中序后繼來取代它。
可以對二叉查找樹進行旋轉以恢復平衡。
二叉查找樹定義：
- 又稱為是二叉排序樹（Binary Sort Tree）或二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
1) 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
2) 若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
3) 左、右子樹也分別為二叉排序樹；
4) 沒有鍵值相等的節點。
- 二叉查找樹的性質：對二叉查找樹進行中序遍歷，即可得到有序的數列。
- 二叉查找樹的時間復雜度：它和二分查找一樣，插入和查找的時間復雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間復雜度。原因在于插入和刪除元素的時候，樹沒有保持平衡。我們追求的是在最壞的情況下仍然有較好的時間復雜度，這就是平衡查找樹設計的初衷。
- 二叉查找樹的高度決定了二叉查找樹的查找效率。
二叉查找樹的插入過程
- 若當前的二叉查找樹為空，則插入的元素為根節點。
- 若插入的元素值小于根節點值，則將元素插入到左子樹中。
- 若插入的元素值不小于根節點值，則將元素插入到右子樹中。
二叉查找樹的刪除
- 分三種情況進行處理：
1. p為葉子節點，直接刪除該節點，再修改其父節點的指針（注意分是根節點和不是根節點），如圖a。
2. p為單支節點（即只有左子樹或右子樹）。讓p的子樹與p的父親節點相連，刪除p即可；（注意分是根節點和不是根節點）；如圖b。
3. p的左子樹和右子樹均不空。找到p的后繼y，因為y一定沒有左子樹，所以可以刪除y，并讓y的父親節點成為y的右子樹的父親節點，并用y的值代替p的值；或者方法二是找到p的前驅x，x一定沒有右子樹，所以可以刪除x，并讓x的父親節點成為y的左子樹的父親節點。如圖c。
平衡二叉樹
二叉排序樹集中了數組的查找優勢以及鏈表的插入、刪除優勢，因此在數據結構中占有一定的地位。但在一定的情況下二叉排序樹又有可能變為鏈表，例如插入從1~100的數，這時進行數據查找的效率就要降低。
為了解決二叉排序樹這種左右子樹深度不均勻的情況引入了一種平衡二叉樹（AVLTree）:任何一個節點的左右子樹深度差不超過1.通過這個限定，阻止了二叉樹的左右子樹深度差較大的情況，維持了二叉樹的穩定。
為了讓二叉樹的左右子樹深度差不超過1，需要對節點進行旋轉，具體參考{數據結構—平衡二叉樹](http://www.cnblogs.com/PerkinsZhu/p/5824015.html)
教材學習中的問題和解決過程
問題1：對Comparable接口的認知，與Comparator、compareTo、compare進行比較
問題1解決方案：
二叉查找樹要求所有的項都能夠排序。要寫出一個一般的類，我們需要提供一個接口來表示這個性質。這個接口就是Comparable，該接口告訴我們，樹中的兩項總可以使用CompareTo()方法比較。
public interface Comparable<t></t>此接口強行對實現它的每個類的對象進行整體排序。這種排序被稱為類的自然排序，類的 compareTo 方法被稱為它的自然比較方法。
備注：已經被大多數的常用類型實現
compareTo
int compareTo(T o)比較此對象與指定對象的順序。如果該對象小于、等于或大于指定對象，則分別返回負整數、零或正整數。
public interface Comparator<t></t>強行對某個對象 collection 進行整體排序 的比較函數?？梢詫?Comparator 傳遞給 sort 方法（如 Collections.sort 或 Arrays.sort），從而允許在排序順序上實現精確控制。還可以使用 Comparator 來控制某些數據結構（如有序 set或有序映射）的順序，或者為那些沒有自然順序的對象 collection 提供排序。
備注：僅有少數類實現了這個接口
int compare(T o1,T o2)比較用來排序的兩個參數。根據第一個參數小于、等于或大于第二個參數分別返回負整數、零或正整數。
代碼調試中的問題和解決過程
- 已寫進實驗博客中
代碼托管
上周考試錯題總結
錯題一：
分析：
這里的all nodes 其實是指同一層上的all nodes，我發現有些時候不能直譯，摳字眼，得順著特征性質來思考錯題二：
分析：
記憶里自己沒做錯啊…….可能是不小心選到相鄰項上了，下次注意
本周結對學習情況
- 20162311
- 結對學習內容
- 實驗二
其他（感悟、思考等，可選）
- 這周主要精力都花在實驗二上，參考了很多博客，也求助了不少同學，勉強按時完成，但自身掌握地還是不到位，打算邊學邊補。
學習進度條
| 代碼行數（新增/累積） | 博客量（新增/累積） | 學習時間（新增/累積） | 重要成長 | |
|---|---|---|---|---|
| 目標 | 5000行 | 30篇 | 400小時 | |
| 第一周 | 58/ | 1/1 | 10/10 | |
| 第二周 | 8/18 | |||
| 第三周 | 134/ | 3/4 | 12/ 30 | |
| 第四周 | 2/6 | 12/42 | ||
| 第五&六周 | 750/ 6595 | 5/11 | 24/66 | |
| 第七周 | 764/7068 | 7/13 | 18/84 | |
| 第八周 | 888/7956 | 9/15 | 20/104 |
計劃學習時間: 18小時
實際學習時間: 20小時
改進情況：閱讀了很多資料
參考資料
- 二叉查找樹的實現
- 樹之二叉查找樹
- 數據結構學習筆記之Java實現二叉查找樹
轉載于:https://www.cnblogs.com/JXY6996/p/7750966.html
總結
以上是生活随笔為你收集整理的20162325 金立清 S2 W8 C17的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 敏捷冲刺每日报告四（Java-Team）
- 下一篇： 求一个日子难熬的个性签名。