1.二叉樹(shù)
二叉樹(shù)指的是每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)字?jǐn)?shù)的有序樹(shù)。通常左邊的子樹(shù)稱(chēng)為左子樹(shù) ，右邊的子樹(shù)稱(chēng)為右子樹(shù)
2.排序二叉樹(shù)
排序二叉樹(shù)是有順序的，它是一種特殊結(jié)構(gòu)的二叉樹(shù)
主要特性：
若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
若她的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
具有遞歸性，排序二叉樹(shù)的左子樹(shù)、右子樹(shù)也是排序二叉樹(shù)。
3.平衡二叉樹(shù)
平衡二叉數(shù)又被稱(chēng)為 AVL 樹(shù)
具有以下性質(zhì)的排序二叉樹(shù)：
它的左子樹(shù)和右子樹(shù)的深度之差(平衡因子)的絕對(duì)值不超過(guò)1，且它的左子樹(shù)和右子樹(shù)都是一顆平衡二叉樹(shù)。
兩個(gè)條件：
平衡二叉樹(shù)必須是排序二叉樹(shù)，也就是說(shuō)平衡二叉樹(shù)他的左子樹(shù)所有節(jié)點(diǎn)的值必須小于根節(jié)點(diǎn)的值，它的右子樹(shù)上所有節(jié)點(diǎn)的值必須大于它的根節(jié)點(diǎn)的值。
左子樹(shù)和右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1。
4.紅黑樹(shù)
其實(shí)紅黑樹(shù)和上面的平衡二叉樹(shù)類(lèi)似，本質(zhì)上都是為了解決排序二叉樹(shù)在極端情況下退化成鏈表導(dǎo)致檢索效率大大降低的問(wèn)題，紅黑樹(shù)最早是由 Rudolf Bayer 于 1972 年發(fā)明的。
紅黑樹(shù)首先肯定是一個(gè)排序二叉樹(shù)，它在每個(gè)節(jié)點(diǎn)上增加了一個(gè)存儲(chǔ)位來(lái)表示節(jié)點(diǎn)的顏色，可以是 RED 或 BLACK 。
紅黑樹(shù)的特性：
性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。
性質(zhì)2：根節(jié)點(diǎn)永遠(yuǎn)是黑色的。
性質(zhì)3：所有的葉子節(jié)點(diǎn)都是空節(jié)點(diǎn)（即null），并且是黑色的。
性質(zhì)4：每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。（從每個(gè)葉子到根的路徑上不會(huì)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）
性質(zhì)5：從任一節(jié)點(diǎn)到其子樹(shù)中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。
紅黑樹(shù)的插入：
紅黑樹(shù)的插入和普通排序二叉樹(shù)的插入基本一致，排序二叉樹(shù)的要求是左子樹(shù)上的所有節(jié)點(diǎn)都要比根節(jié)點(diǎn)小，右子樹(shù)上的所有節(jié)點(diǎn)都要比跟節(jié)點(diǎn)大，當(dāng)插入一個(gè)新的節(jié)點(diǎn)的時(shí)候，首先要找到當(dāng)前要插入的節(jié)點(diǎn)適合放在排序二
叉樹(shù)哪個(gè)位置，然后插入當(dāng)前節(jié)點(diǎn)即可。紅黑樹(shù)和排序二叉樹(shù)不同的是，紅黑樹(shù)需要在插入節(jié)點(diǎn)調(diào)整樹(shù)的結(jié)構(gòu)來(lái)讓樹(shù)保持平衡。
一般情況下，紅黑樹(shù)中新插入的節(jié)點(diǎn)都是紅色的
紅黑樹(shù)的旋轉(zhuǎn)：
旋轉(zhuǎn)分為左旋和右旋。
1）左旋
逆時(shí)針旋轉(zhuǎn)兩個(gè)節(jié)點(diǎn)，讓一個(gè)節(jié)點(diǎn)被其右子節(jié)點(diǎn)取代，而該節(jié)點(diǎn)成為右子節(jié)點(diǎn)的左子節(jié)點(diǎn)。
2）右旋
順時(shí)針旋轉(zhuǎn)兩個(gè)節(jié)點(diǎn)，讓一個(gè)節(jié)點(diǎn)被其左子節(jié)點(diǎn)取代，而該節(jié)點(diǎn)成為左子節(jié)點(diǎn)的右子節(jié)點(diǎn)。
左左節(jié)點(diǎn)旋轉(zhuǎn)（插入節(jié)點(diǎn)的父節(jié)點(diǎn)是左節(jié)點(diǎn)，插入節(jié)點(diǎn)也是左節(jié)點(diǎn)）
詳細(xì)解釋?zhuān)?a target="_blank">https://mp.weixin.qq.com/s/dSGIHvgth7IqEZxG11rKOA
