二叉樹

二叉樹是一種樹狀結構，它是有根的，其中每個頂點最多有兩個子節點，並且每個頂點的子節點都被指定為其左子節點或右子節點（West 2000，第 101 頁）。換句話說，與真樹不同，子節點的相對位置很重要。

放棄左右子節點被認為是唯一的要求，就得到了一棵被稱為弱二叉樹的真樹（其中，按照慣例，根節點也被要求最多與一個圖頂點相鄰）。

二叉樹的高度是樹內層級的數量。高度 , 2, ... 的二叉樹的節點數量為 1, 3, 21, 651, 457653, ... (OEIS A001699)。給出這些計數的遞推方程是

(1)

其中 。

具有 個節點的二叉樹的數量為 1, 2, 5, 14, 42, ... (OEIS A000108)，它們是卡塔蘭數 。

對於高度為 且有 個節點的二叉樹，

(2)

這些極端情況分別對應於平衡樹（除了樹葉之外的每個節點都有一個左子節點和右子節點，並且所有樹葉都在同一層級）和退化樹（每個節點只有一個外向分支）。

對於組織成二叉樹的資料搜尋，找到一個專案所需的搜尋步驟 的數量受限於

(3)

將任意樹部分平衡為所謂的 AVL 二叉搜尋樹可以提高搜尋速度。