二叉樹的概念#
滿二叉樹#
一顆二叉樹只有度（度是孩子結點）為 0 的結點和度為 2 的結點，且度為 0 的結點在同一層上。
- 總共有 $2^{k}-1$ 個結點（k 為樹的深度）
- 每一層有 $2^{n-1}$ 個結點（n 為當前層數）
完全二叉樹#
只允許最後一層不為滿，且最後一行必須是從左往右排序不能有間隔。
- 底層可以有 1~$2^{k-1}$ 個結點，中間不能有間隔。
二叉搜索樹#
二叉搜索樹是一個有序樹，又名 二叉排序樹 、二叉查找樹。
- 若左子樹非空，則左子樹上所有結點的值均小於其根結點的值；
- 若右子樹非空，則右子樹上所有結點的值均大於其根結點的值；
- 左右子樹分別為二叉排序樹；
- 沒有鍵值相等的結點。
二叉搜索樹的根結點是確定不變的的，當在進行數據的插入和刪除的時候會造成二叉樹朝著單鏈表的方向發展，降低了數據的查詢效率，所有就有平衡二叉樹。
平衡二叉樹#
AVL 樹（Adelson-Velsky and Landis Tree）
平衡二叉樹是基於二叉樹優化而來。
- 可以是空樹；
- 任何一個結點的左子樹與右子樹的都是平衡樹，並且高度之差的絕對值不超過 1；
實現平衡的方法
平衡因子：某結點的左子樹和右子樹的高度（深度）差即為結點平衡因子，平衡二叉樹中不存在平衡因子大於 1 的結點（只有 -1、0、1）。
平衡二叉搜索樹#
平衡二叉搜索樹是一個空樹或者左右子樹都是平衡二叉樹(高度差不超過 1)。