介紹併查集的章節中已簡單說明過甚麼是樹狀結構，也提到使用樹儲存資料所帶來的好處，接下來會清楚定義甚麼是樹，以及如何利用各種與樹相關的資料結構，提升搜尋的資料效率。
Binary Search
首先介紹常見的二元搜尋法（Binary search），搜尋已排序過的列表（linked List）直觀需要遍歷所有元素，複雜度為O(N)；而如果從列表中間的元素開始比較，小於想要搜尋的元素則繼續搜尋左邊剩餘的元素中，中間的元素，反之大於則搜尋右邊剩餘的元素中，中間的元素，其搜尋的複雜度為 O(logN)。
舉例來說：經排序的列表如圖一，想要找到節點 5，可以從頭到尾找一遍；或是從中間的節點 4 開始尋找，判斷節點 5 大於節點 4，因此尋找右邊剩餘的節點（5、6、7）中，中間的節點 6，從判斷節點 6 大於節點 5，往左邊剩餘的節點（5）中，找到目標節點 5。
接著介紹如何利用樹的資料結構，完成二元搜尋法。
Tree
首先定義一顆樹是由多個節點（node）構成，節點跟節點之間以邊（edge）互相連結，其中一個重要的條件是任意兩個節點的路徑唯一。舉例來說，圖一中間的結構，任意兩個節點的路徑不唯一，則不能稱為樹。
Root tree
假設一顆樹中選定一個節點為根節點（root），代表根節點為最上層的節點，其它所有的節點都依附在根節點底下，而兩個節點之間的依附關係，常以父節點（parent）子節點（child）稱呼。除了根節點以外每個節點都有一個父節點，沒有子節點的節點又可稱葉節點（leaf），而之後談到的樹幾乎都可以默認為 root tree。
Rooted Binary Tree
此時從 root tree 再加上一個條件，限制樹中所有節點的子節點數量至多只有兩個，也就是說子節點數量只有 0 1 2 三種可能，則可稱這棵樹為二元樹。
此時回想上述使用二元搜尋法搜尋排序過的列表中的節點的步驟，一樣先從列表中間的節點 4 開始，將節點 4 視為根節點，如圖三所示。下一步會根據欲搜尋的節點大於或是小於當前的節點 4，決定往右或是往左搜尋剩餘的節點，因此根節點 4 會指向左邊和右邊剩餘的節點中，中間的節點，分別是節點 2 和節點 6。
以此類推比較欲搜尋的節點 5 大於當前節點 4，往右搜尋節點 6，如圖四所示，最終找到節點 5。
而這個以二元樹代替二元搜尋法的資料結構又稱：二元搜尋樹（Binary Search Tree）。
Binary Search Tree(BST)
二元搜尋樹的定義為，滿足二元樹的條件，且每個節點都符合下列規則
- 任意節點 x 所有左邊的子節點（子樹）皆小於節點 x 的值，例如圖四中的節點 1 2 3 皆小於節點 4。
- 任意節點 x 所有右邊的子節點（子樹）皆大於節點 x 的值，例如圖四中的節點 5 6 7 皆大於節點 4。
理想的情況下，搜尋 BST 的節點的複雜度和二元搜尋法一樣，皆為 O(logN)。原本判斷中間節點的值大於或小於想要搜尋的節點，再決定搜尋右半部或是左半部節點的步驟，改為直接搜尋左邊或右邊的節點。也因此搜尋的方法為
static BST find(BST T, Key sk) {
if (T == null)
return null;
if (sk.equals(T.key))
return T;
else if (sk ≺ T.key)
return find(T.left, sk);
else
return find(T.right, sk);
}其中類別 BST 有三個成員 key、left、right，分別代表當前節點用來比較的值；左邊節點指向的小於當前節點的 BST；右邊節點指向大於當前節點的 BST。
理想的情況是指二元搜尋樹的節點分布非常的平衡，如果節點集中在 left 或是 right，雖然符合二元搜尋樹的定義，搜尋的複雜度則會變成O(N)。
如果要對 BST 新增一個節點，透過搜尋的方法搜尋，只要沒有找到重複的節點，就一定會落在 null 的位置，也就是原來葉節點的子節點，如圖五所示。
static BST insert (BST T, Key k) {
if (T == null)
return new BST(k, null, null);
if (sk.equals(T.key))
return T;
else if (k ≺ T.key)
T.left = insert(T.left, k);
else
T.right = insert(T.right, k);
}而如果要刪除一個節點，步驟會相對複雜，首先考慮該節點的三種情況
- 沒有子節點
直接將父節點指向 null，則欲刪除的節點會因為沒有其他任何節點指向它，被 Java 的 GC 自動刪除。 - 有一個子節點
該子節點一定會繼承欲刪除節點大於或小於父節點的特性，只要將其父節點指向唯一的子節點，欲刪除的節點同樣會被 GC 自動刪除。如圖六左邊的 BST，想要刪除的節點 6 有一個子節點 7，因為節點 6 的父節點是節點4，且為節點 4 的 right 成員，代表節點 6 的所有子節點皆大於節點 4，因此只要將節點 4 的 right 成員，指向剩餘唯一的節點 7 即可。 - 有兩個子節點
有兩個子節點意味著該節點的 left 和 right 成員同時存在，如果將該節點刪除，則要考慮刪除的節點須被哪一個子節點取代。重新回想 BST 節點的特性為，考慮一個節點 R，所有 left 的子節點皆小於 R；反之所有 right 的子節點皆大於 R，而如果要刪除 R，則要在 left 或是 right 的子樹中找出一個節點來替代 R，同時維持 BST 的特性。如圖六右邊的 BST，想要刪除節點 4，可以挑選 left 的子樹中最大的節點 3，或是 right 的子樹中最小的節點 5；或著是說， left 的子樹中最右邊的節點，或是 right 的子樹中最左邊的節點。
如今又學習一種新的資料結構 BST 來實現 ADT（Abstract Data Type），以減少程式執行時所花費的時間。舉例來說，在理想的情況（平衡）下，以 BST 實現的集 （Set），執行搜尋的時間複雜度為 O(logN)，而以 array 實現的 Set 搜尋的時間複雜度為 O(N)。接下來，為了確保執行搜尋的複雜度為 O(logN)，則要開始討論如何維持樹的平衡，或稱 B-Tree。
