[Powered by Google Translate] 你將如何代表所有家庭成員在一台電腦嗎？
我們可以簡單地使用一個列表，
但這裡有一個清晰的層次結構。
>> 比方說，我們已經開始與你的偉大的祖母，愛麗絲。
她有兩個兒子，鮑勃
和你的祖父，查理。
查理有3個孩子，
戴夫，你的叔叔，阿姨，夏娃，你的父親，弗雷德。
你是弗雷德唯一的孩子。
>> 為什麼會以這種方式組織你的家庭成員
比簡單的列表表示？
其中一個原因是，這種分層結構中，
被稱為“樹”，不是一個簡單的列表中包含更多的信息。
我們知道每個人的家庭之間的關係
僅僅通過審查樹。
此外，它可以加快
看時間大幅增加，如果樹對數據進行排序。
>> 我們不能利用的，在這裡，但我們會很快看到一個這樣的例子。
每個人的表示的樹的一個節點上。
節點可以有子節點
以及作為父節點。
這些技術術語，
即使在使用樹木的事情，除了家庭。
Alice的節點有2個孩子，沒有父母，
而查理的節點有3個孩子和1父。
>> 葉節點是一個沒有任何兒童
的外邊緣上的樹。
最上面的節點樹的根節點，
沒有父。
>> 二叉樹是一種特殊類型的樹，
每個節點都有，最多2名兒童。
下面是C中一個節點的二進制樹的結構的
每個節點都有與它相關的一些數據
和2到其他節點的指針。
>> 在我們的家譜，
的相關聯的數據是每個人的名字。
在這裡，它是一個int，但它可以是任何東西。
事實證明，
一個二叉樹不會是一個很好的家庭表示，
因為人們經常有2個以上的孩子。
>> 二叉搜索樹
二叉樹是一種特殊的，有序的類型
讓我們看看在價值迅速。
您可能已經注意到
每個節點的樹的根目錄下
是另一棵樹的根，稱為“子樹。”
在這裡，樹的根是6，
和其子，2，是根的子樹。
>> 在二叉搜索樹
所有節點的值的右子樹
大於該節點的值。 ：6。
那麼，一個節點的左子樹中的值
小於該節點的值。
如果我們需要處理重複的值，
我們可以改變這些鬆散的不平等，
這意味著相同的值，可以向左或向右下降，
只要我們保持一致，整個。
此樹是二叉搜索樹
因為它遵循這些規則。
>> 這是怎麼會看，如果我們把所有的節點C的結構。
請注意，如果一個孩子失踪，
指針為空。
我們如何檢查，看看在樹上嗎？
我們從根開始。
七是大於6，所以如果是在樹中，它必須是正確的。
然後，它是小於8，因此必須將其留下。
在這裡，我們發現了7。
現在，我們將檢查5。
五是小於6，所以它必須是向左側。
五是大於2，
所以它必須是正確的，
也是大於4，所以它必須是便又。
然而，這裡沒有孩子。
指針為NULL。
這意味著，5是不是在我們的樹。
>> 我們可以用下面的代碼的二進制樹搜索：
在每一個節點上，我們要檢查一下，如果我們發現
我們正在尋找的價值。
如果我們不找到它，我們確定它應該是
向左或向右子樹檢查。
這個循環將繼續向下樹
直到有沒有子節點上的左側或右側。
>> 請記住，是不是在樹中。
我們怎麼插入呢？
這個過程看起來類似搜索。
我們遍歷樹從6
左為2，
右至4，
對了，但4有沒有孩子這一邊。
5，這將是新的位置，
它會開始無子女。
>> 二叉搜索樹的操作速度有多快？
請記住，Bigohnotation的目的是提供一個上限。
在最壞的情況下，
我們的樹可能僅僅是一個鍊錶
也就是說，插入，缺失，和搜索
可能需要時間在樹中的節點的數目成正比。
這是O（n）的。
>> 例如，下面是一個有效的二進制搜索樹。
但是，如果我們試圖找到9，
我們要遍歷的每個節點。
這是沒有比一個鍊錶。
理想的情況下，我們希望每一個節點
我們的二叉搜索樹，有2個孩子。
通過這種方式，插入，刪除和搜索
所做的那樣，在最壞的情況下，O（log n）的時間。
從之前的樹更加平衡，
是這樣的。
現在，任何價值需要，頂多3個步驟。
此樹是平衡的，
的意義，這有一個最小的深度
相對於節點的數目。
>> 尋找平衡的二叉搜索樹中的一個值
類似二進制搜索排序的數組。
事實上，如果我們不需要插入或刪除項目，
他們的行為完全一樣的方式。
然而，一個樹結構是更好的
處理插入和刪除
>> 我的的名字是Bannus范德Kloot。
這是CS50。