這是一位 google 工程師分享的8小時的數(shù)據(jù)結構的視頻,我的筆記
Tree: 滿足以下定義的undirected graph(無向圖)
- An acyclic(非循環(huán)的) connected graph
- N nodes and N-1 edges
- 有且只有一條路徑連接任意兩個頂點
任意一個節(jié)點都可以被理解為root
Binary Tree
擁有最多兩個節(jié)點的Tree
Binary Search Tree
服從以下特性的binary tree
- 左子樹的元素小于右子樹
擁有重復元素是允許的，但多數(shù)情況下我們只研究不重復的元素
這是一個有效的BST嗎？
2021-11-29-17-30-45.png
是的（對于單鏈下來的鹿霸，幾乎會直接就滿足右邊比左邊大）
Usage
- BSTs
- implementation of some map and set ADTs
- red black trees
- AVL trees
- splay trees
- ...
- binary heaps
- syntax trees (by compiler and calculators)
- Treap - a probabilistic DS (uses a randomized BST)
Complexity
增刪查平均為O(log n)秽梅，但最差情況下都為O(n)频蛔，即線性時間
Adding elements to a BST
- 第一個為root
- 每一個新數(shù)琴庵，比頂點大，放右邊蛤织，比頂點小艺挪，放左邊不翩，順序下行
- 不是從左到右擺滿再做subtree
- 比如3,6,9, 會得一棵全部數(shù)字擺在右邊的數(shù)，而不是頂3左6右9的三角形
- 這也是為什么極端情況下，時間復雜度是
O(n)口蝠，因為就是一條線到底 - 這也是
balanced binary search trees被引入的原因
Removing elements from a BST
- find
- 從root開始器钟，小的走左右，大的走右邊
- replace (to maintain the BST invariant)
找繼任者的時候妙蔗，如果刪除元素沒有子節(jié)點傲霸，只有左或右子節(jié)點，都很好辦眉反，但如果它有兩個子節(jié)點昙啄，那么應該用哪個來接續(xù)呢？
原則仍然是要服從左邊的比右邊的小寸五，所以你其實有兩種選擇：
- 把左邊最大的數(shù)選出來 或
- 把右邊最小的數(shù)選出來
因為它們的“來源”梳凛，肯定是能保證bst invariant的- 這個數(shù)是要替換這個節(jié)點的，所以要比這個節(jié)點左邊的數(shù)都大梳杏，及比右邊所有的數(shù)都小伶跷，顯然就是左邊的最大數(shù)，或右邊的最小數(shù)了秘狞。
- 只是把找到的元素復制過去后，多了的那個怎么辦呢蹈集？
-
遞歸
新找到的元素當然要從原來的位置刪除烁试，這時又根據(jù)它是否葉節(jié)點，單子節(jié)點還是全節(jié)點拢肆，來反復進行前面的操作减响，最終總是可以退出的
2021-11-29-17-30-45.png
2021-11-29-17-31-11.png
Tree Traversals
(Preorder, Inorder, Postorder & Level order)
2021-11-29-17-38-42.png
- preorder，在遍歷左側元素的時候郭怪，每次已經先取到元素了（最頂層）
- inorder里支示，遍歷元素的時候，直到所有的left走完了鄙才，才取到第一個元素（最底層的）
-
postorder里颂鸿，也是遍歷到最底層，但是下一步就是取兄弟節(jié)點了
2021-11-29-17-45-31.png
inorder一個重要特征：它是從小到大排好序的攒庵！
2021-11-29-17-52-57.png
preorder 和 postorder沒什么特征嘴纺，舉一個post的例子觀察下
而levelorder則是一層一層地取的：
2021-11-29-17-54-34.png
這就是廣度優(yōu)先了（
Breadth First Searth)BFS
實現(xiàn)BFS
- 每處理一個parent的時候，把parent加到結果數(shù)組里
- parent的子節(jié)點加到隊列里
- 每次從隊列里取出一個值加到結果數(shù)組里（步驟1）
- 該值的child加到隊列里（步驟2）
其實就是步驟1浓冒，2的重復栽渴，比如：
2021-11-29-18-04-16.png
[11], [6, 15] 處理第1個數(shù)11， 隊列里多了兩個元素6稳懒， 15
[11, 6], [15, 3, 8] 從隊列里取出6闲擦， 加入結果，它的子元素(3, 8)加入隊列
[11, 6, 15], [3, 8, 13, 17]
[11, 6, 15, 3], [8, 13, 17, 1, 5]
[11, 6, 15, 3, 8], [13, 17, 1, 5] 這一步，8沒有子節(jié)點了墅冷，隊列變短了
[11, 6, 15, 3, 8, 13], [17, 1, 5, 12, 14]
[11, 6, 15, 3, 8, 13, 17], [1, 5, 12, 14, 19] 17只有一個child
[11, 6, 15, 3, 8, 13, 17, 1, 5, 12, 14, 19] 剩下的都沒child了纯路，全部拼進去
