首先說(shuō)一下，凡是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)的樹(shù)都叫二叉樹(shù)。
二叉查找樹(shù)
二叉查找樹(shù)，也稱二叉搜索樹(shù)，或二叉排序樹(shù)。其定義也比較簡(jiǎn)單，要么是一顆空樹(shù)，要么就是具有如下性質(zhì)的二叉樹(shù)：
（1）若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
（2） 若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
（3） 任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)；
（4） 沒(méi)有鍵值相等的節(jié)點(diǎn)。
平衡二叉樹(shù)（AVL二叉樹(shù)）
? 平衡二叉搜索樹(shù)，又被稱為AVL樹(shù)，且具有以下性質(zhì)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。
紅黑樹(shù)
一種二叉查找樹(shù)，但在每個(gè)節(jié)點(diǎn)增加一個(gè)存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅或黑（非紅即黑）。通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)節(jié)點(diǎn)著色的方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其它路徑長(zhǎng)出兩倍，因此，紅黑樹(shù)是一種弱平衡二叉樹(shù)（由于是弱平衡，可以看到，在相同的節(jié)點(diǎn)情況下，AVL樹(shù)的高度低于紅黑樹(shù)），相對(duì)于要求嚴(yán)格的AVL樹(shù)來(lái)說(shuō)，它的旋轉(zhuǎn)次數(shù)少，所以對(duì)于搜索，插入，刪除操作較多的情況下，我們就用紅黑樹(shù)。
Attention:
平衡樹(shù)（AVL）是為了解決 二叉查找樹(shù)（BST）退化為鏈表的情況。
紅黑樹(shù)（RBT）是為了解決 平衡樹(shù) 在刪除等操作需要頻繁調(diào)整的情況
