本章以搜尋樹為例，示範樹狀結構上的歸納證明。本章於初次閱讀時可跳過。

許多應用需要將資料收集在某種表達「集合」的資料結構中。 我們希望能做的操作包括：尋找並判斷某筆資料是否在集合中、加入某筆新資料、刪除某筆資料，等等。 許多演算法都仰賴這些操作能有效率地被實作。

我們可以用串列表達一個集合，但在一般的簡單實作中，在串列中尋找與刪除都需要與串列長度成正比的時間。若集合中的資料是能比大小的，使用一個陣列並將元素排序好，可用二元搜尋法在對數時間內尋找某筆資料。但在陣列中加入與刪除元素也都需要與陣列長度成正比的時間挪出或消除空位。

因此，許多針對此類應用的樹狀結構被發展出來。