二叉搜索樹
定義
一種在有序數(shù)組中查找某一特定元素的搜索算法怕午，稱之為二叉查找或者二分查找法。
在樹結(jié)構(gòu)中類似淹魄，從中間元素開始查找郁惜，對比大小，縮小搜索范圍甲锡。
而二叉（分）查找（搜索）樹兆蕉，
每個(gè)節(jié)點(diǎn)的key值大于左子節(jié)點(diǎn)，小于右子節(jié)點(diǎn)缤沦，不一定是二叉樹恨樟。
借助這個(gè)性質(zhì)，二叉搜索樹不僅可以用來搜索查找數(shù)據(jù)疚俱，還可以高效地插入劝术、刪除數(shù)據(jù)。
遍歷
二叉樹的前序遍歷、中序遍歷养晋、后序遍歷
添加
遵循插入元素大于中間元素向右支走衬吆，小于中間元素左支走，不斷迭代循環(huán)绳泉。
刪除
分為三類：
- 沒有子類逊抡，直接刪除
- 有一個(gè)子類，目標(biāo)節(jié)點(diǎn)被刪除零酪，將子節(jié)點(diǎn)移動到已刪除節(jié)點(diǎn)的位置
- 有兩個(gè)子類冒嫡，目標(biāo)節(jié)點(diǎn)被刪除，從刪除節(jié)點(diǎn)的左子樹中找到最大的節(jié)點(diǎn)四苇，將其移到到刪除的節(jié)點(diǎn)的位置
局限
二分搜索樹一旦退化成單鏈表孝凌，查找搜索效率和插入刪除效率降低。
平衡二叉樹（AVL樹）
Wiki
在計(jì)算機(jī)科學(xué)中月腋，AVL樹是最早被發(fā)明的自平衡二叉查找樹蟀架。在AVL樹中，任一節(jié)點(diǎn)對應(yīng)的兩棵子樹的最大高度差為1榆骚，因此它也被稱為高度平衡樹片拍。查找、插入和刪除在平均和最壞情況下的時(shí)間復(fù)雜度都是 O(logn）妓肢。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉(zhuǎn)捌省，以實(shí)現(xiàn)樹的重新平衡。AVL 樹得名于它的發(fā)明者 G. M. Adelson-Velsky 和 Evgenii Landis碉钠。
優(yōu)勢
針對于二叉搜索樹查找效率取決于樹的高度所禀，只要保證樹的高度就可以保證搜索效率。經(jīng)過研究放钦，當(dāng)節(jié)點(diǎn)數(shù)目一定色徘，保持樹的左右兩端平衡，就是平衡二叉樹操禀。
即要求褂策，任意左右子樹的高度差只能是-1、0颓屑、1三個(gè)數(shù)值斤寂，這被稱之為平衡二叉樹。
另外揪惦，上面所謂樹的高度差和深度差都可以表述成平衡二叉樹的平衡因子遍搞。平衡因子只能取-1、0器腋、1溪猿。
AVL樹插入后最小失衡樹與左右旋調(diào)整
最小失衡樹：在新插入的節(jié)點(diǎn)向上查找钩杰，以第一個(gè)平衡因子的絕對值超過 1 的節(jié)點(diǎn)為根的子樹稱為最小不平衡子樹。
失衡調(diào)整方法：通過旋轉(zhuǎn)最小失衡子樹來實(shí)現(xiàn)的
AVL樹刪除節(jié)點(diǎn)
需要重新檢查平衡性并且修正诊县，通過左右旋就能得到讲弄。
小結(jié)
平衡二叉樹的優(yōu)勢在于當(dāng)二叉樹退化成單鏈表失衡，固定了樹的高度依痊，保證了查找搜索效率避除。
但是為了保證平衡性，損失了在動態(tài)插入和刪除的效率
因此需要其他靈活性修改胸嘁，例如紅黑樹（不是真正的平衡二叉樹瓶摆，借鑒了思想，理論基礎(chǔ)2-3-4樹等性宏。）
