樹的相關概念
-
父節點、子節點、兄弟節點
-
沒有父節點的節點叫根節點，沒有子節點的節點叫葉節點
-
節點的高度：節點到葉子節點的最長路徑（邊數）（從下往上，根節點高度為0）
-
節點的深度：根節點到這個節點所經歷的邊數（從上往下，根節點的深度為0）
-
節點的層數：節點的深度+1（類比樓房層數，地面是一樓）
-
樹的高度：根節點的高度
-
示意圖
二叉查找樹
要求樹中任意一個節點，其左子樹每個結點的值都要小于這個節點的值，而右子樹節點的值都大于這個節點的值
- 查找：從根節點開始，如果它等于要找的值則回傳；如果要查找值比根節點值小，則去左子樹遞回查找；如果要查找值比根節點值大，則去右子樹遞回查找
- 插入：和查找相似，從根節點開始，遞回找到合適的葉節點
- 洗掉
-
如果要洗掉的節點沒有子節點，直接父節點對應指標置空
-
如果僅有一個子結點，將父節點對應指標指向子節點
-
如果有兩個子節點，那么需要找到右子樹的最小節點（或是左子樹最大節點），用這個節點替換要洗掉的節點
-
支持重復資料的二叉查找樹
-
插入：如果碰到一個節點的值與要插入資料值相同，那么將其插入右子樹，也就是把它當作大于這個節點的值處理
-
查找：遇到相同節點值時并不直接結束，而是繼續在右子樹中查找，直到葉子節點才停止，將所有等于查找值的節點都找出來
-
洗掉：找到相同節點值后，按一般的洗掉操作進行洗掉，然后繼續在右子樹中尋找是否有相同值節點，將所有等于洗掉值的節點全部洗掉
二叉查找樹與哈希表相比的優勢
-
快速查找最大/小節點
-
中序遍歷可以輸出有序的資料序列
-
穩定動態擴容（哈希表有散列沖突，時間復雜度并不穩定）
-
實作上要考慮的東西不多
-
（這樣看來跳表還真是優秀啊）
二叉查找樹的性能分析
-
查找一個值時花費的時間其實和樹的高度成正比
-
最壞情況下，二叉樹退化為鏈表，查找時間復雜度為O(n)
-
最好情況，二叉平衡樹，高度小于等于log2n，查找時間復雜度為O(logn)
-
為了防止二叉樹在插入資料后出現時間復雜度退化的情況，人們發明了平衡二叉樹來解決這個問題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24746.html
標籤：其他
上一篇：求助！！
下一篇：YOLO在ARM的速度優化方案