二叉搜索樹
樹型數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要用途是用作搜索樹。二叉搜索樹：當(dāng)前節(jié)點(diǎn)值為k醒陆，左子樹的值都小于k浸踩，右子樹的值都大于k。
二叉搜索樹的中序遍歷是按照值增加的順序進(jìn)行的
二叉搜索樹的一些方法
first()：返回一個(gè)包含最小值的節(jié)點(diǎn)
last()：返回一個(gè)包含最大值的節(jié)點(diǎn)
before(p)：返回比節(jié)點(diǎn)p的值小的所有節(jié)點(diǎn)中值最大的節(jié)點(diǎn)（即中序遍歷在p之前最后一個(gè)被訪問的節(jié)點(diǎn)）
after(p)：返回比p的值大的所有節(jié)點(diǎn)中值最小的節(jié)點(diǎn)（即中序遍歷在p后的第一個(gè)節(jié)點(diǎn)）
after方法即中序遍歷的下一個(gè)結(jié)點(diǎn)统求，參考劍指offer第8題
二叉搜索樹的搜索
lc700 二叉搜索樹的搜索
如果要搜索的值小于當(dāng)前節(jié)點(diǎn)的值检碗，則往左子樹搜索，如果要搜索的值大于當(dāng)前節(jié)點(diǎn)的值码邻，則往右子樹搜索
class Solution(object):
def searchBST(self, root, val):
if not root:
return None
if root.val == val:
return root
elif root.val < val:
return Solution().searchBST(root.right,val)
else:
return Solution().searchBST(root.left,val)
二叉搜索樹的插入
在二叉樹中搜索要插入的值折剃，當(dāng)遞歸到空子樹時(shí)，就用插入的值替代空子樹
lc701 二叉搜索樹中的插入操作
class Solution(object):
def insertIntoBST(self, root, val):
def dfs(root,val):
if val<root.val:
if root.left:
dfs(root.left,val)
else:
root.left = TreeNode(val)
else:
if root.right:
dfs(root.right,val)
else:
root.right = TreeNode(val)
dfs(root,val)
return root
二叉搜索樹的刪除
從二叉樹中刪除一個(gè)節(jié)點(diǎn)比插入一個(gè)新的節(jié)點(diǎn)更復(fù)雜像屋，因?yàn)閯h除的位置可能在樹中的任何地方怕犁，而插入總是在搜索路徑的最后一個(gè)位置。要?jiǎng)h除一個(gè)節(jié)點(diǎn)，首先找到該節(jié)點(diǎn)奏甫，然后：
1.如果該節(jié)點(diǎn)最多有一個(gè)子節(jié)點(diǎn)戈轿，則就用其子節(jié)點(diǎn)替換它
2.如果該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，先找到它的前繼節(jié)點(diǎn)r阵子，因?yàn)樗袃蓚€(gè)子節(jié)點(diǎn)思杯，所以其前繼節(jié)點(diǎn)即它的左子樹最右邊的位置。用r節(jié)點(diǎn)替代該節(jié)點(diǎn)挠进，用r的左子節(jié)點(diǎn)替代r原來的位置
lc450 刪除二叉搜索樹中的節(jié)點(diǎn)
AVL樹色乾、伸展樹和紅黑樹是基于少量操作對(duì)標(biāo)準(zhǔn)二叉搜索樹進(jìn)行擴(kuò)展去重新調(diào)整樹并降低樹的高度
平衡二叉搜索樹
平衡二叉搜索樹的主要操作是旋轉(zhuǎn)。在旋轉(zhuǎn)之前领突，如果x是y的左子樹（x<y）暖璧，則旋轉(zhuǎn)之后，y成為x的右子樹君旦。此外澎办，還必須利用被旋轉(zhuǎn)的兩個(gè)位置之間的值連接子樹節(jié)點(diǎn)。
旋轉(zhuǎn)修改了常數(shù)數(shù)量的父子關(guān)系金砍，在一個(gè)二叉樹中實(shí)現(xiàn)它用O(1)時(shí)間局蚀。
AVL樹
高度平衡屬性：對(duì)于T中的每一個(gè)位置p，p的孩子的高度最多相差1
任何滿足高度平衡屬性的二叉搜索樹T被稱為AVL樹捞魁。
高度平衡維持的樹對(duì)數(shù)的高度至会，且?guī)淼囊粋€(gè)直接結(jié)果是AVL樹子樹本身就是一棵AVL樹离咐。同時(shí)也可以保持高度最小谱俭。
一棵存有n個(gè)節(jié)點(diǎn)的AVL樹的高度是O(logn)
對(duì)于一棵二叉搜索樹，如果孩子之間的高度差的絕對(duì)值最多為1宵蛀，則該位置是平衡的昆著，AVL的高度搜索屬性相當(dāng)于每個(gè)位置都是平衡的。
AVL樹的插入和刪除操作類似于二叉搜索樹的操作术陶，當(dāng)因?yàn)槭盏礁淖兊牟焕绊憣?duì)每一部分恢復(fù)平衡所進(jìn)行的操作的后期處理是不一樣的
插入
在葉子節(jié)點(diǎn)p的位置產(chǎn)生了一個(gè)新節(jié)點(diǎn)凑懂，這個(gè)操作可能違反了高度平衡屬性，然而唯一可能變得不平衡的位置是p的祖先梧宫，因?yàn)樵撐恢檬瞧渥訕湮ㄒ蛔兓^的位置接谨。
假設(shè)z是插入p后變得不平衡的最近的p的祖先，y是z的具有更高高度的孩子塘匣，x是y具有更高高度的孩子脓豪，通過一次或多次旋轉(zhuǎn)使他們平衡
刪除
同樣通過旋轉(zhuǎn)恢復(fù)平衡，z表示在T中從p向根方向遇到的第一個(gè)不平衡位置忌卤，y表示z具有更高高度的孩子扫夜；如果y的一個(gè)孩子比另一個(gè)高，令x是較高的孩子，否則笤闯，令x是與y在同一邊的y的孩子堕阔。
但是旋轉(zhuǎn)可能導(dǎo)致中間位置的祖先變得不平衡，所以還要繼續(xù)在T中尋找不平衡的位置颗味。如果找到超陆，則用旋轉(zhuǎn)來恢復(fù)平衡。
伸展樹
伸展樹在高度上沒有一個(gè)嚴(yán)格的對(duì)數(shù)上界脱衙，其效率取決于某一位置移動(dòng)到根的操作（稱為伸展）侥猬，每次在插入、刪除或者搜索都要從最底層的位置p開始捐韩。直觀上講退唠，會(huì)使得被頻繁訪問的元素更快接近于根，從而減少典型的搜索時(shí)間荤胁。它對(duì)插入瞧预、刪除、搜索操作保證了對(duì)數(shù)的運(yùn)行時(shí)間
伸展：已知二叉搜索樹的一個(gè)節(jié)點(diǎn)x仅政，我們通過一系列的重組將x移動(dòng)到T的根來對(duì)x進(jìn)行伸展垢油。分為zig-zig型（節(jié)點(diǎn)x和父節(jié)點(diǎn)y都在樹的左邊或者右邊）、zig-zag型（節(jié)點(diǎn)x和父節(jié)點(diǎn)y一個(gè)是左孩子圆丹，一個(gè)是右孩子）滩愁、zig型（沒有祖父節(jié)點(diǎn)）
何時(shí)進(jìn)行伸展：
1.搜索k時(shí)，發(fā)現(xiàn)k在位置p辫封，則伸展p硝枉。否則，在搜索失敗的位置伸展葉子節(jié)點(diǎn)
2.插入k時(shí)倦微，身材新插入的內(nèi)部節(jié)點(diǎn)k
3.刪除k時(shí)妻味，在位置p進(jìn)行伸展，其中p是被移除節(jié)點(diǎn)的父節(jié)點(diǎn)
（2欣福，4）樹*
紅黑樹
紅黑樹更新之后责球，使用O(1)次結(jié)構(gòu)變化來保持平衡
紅黑樹是一棵帶有紅色和黑色節(jié)點(diǎn)的二叉搜索樹，其具有下面的屬性：
- 根屬性：根節(jié)點(diǎn)是黑色的
- 紅色屬性：紅色節(jié)點(diǎn)的子節(jié)點(diǎn)是黑色的
- 深度屬性：具有零個(gè)子節(jié)點(diǎn)或一個(gè)子節(jié)點(diǎn)的所有節(jié)點(diǎn)都具有相同的黑色深度（黑色祖先節(jié)點(diǎn)的數(shù)量）
紅黑樹存儲(chǔ)n個(gè)條目的高度是O(logn)
操作
搜索
紅黑樹的搜索算法與標(biāo)準(zhǔn)二叉樹中的搜索算法是相同的
插入
特殊情況下拓劝，x是T的唯一節(jié)點(diǎn)雏逾，因此將根著色為黑色。其他情況下郑临，將x著色為紅色栖博，但有可能違法紅色屬性
即x和其父結(jié)點(diǎn)都是紅色的，但x的祖先z是黑色的牧抵，這種情況稱為雙紅色問題
如果y的兄弟姐妹為黑色笛匙，則通過重組把父結(jié)點(diǎn)變?yōu)楹谇劝眩瑇節(jié)點(diǎn)和祖先節(jié)點(diǎn)分別作為父結(jié)點(diǎn)的左右子樹且為紅色
如果y的兄弟姐妹是紅色，則重新著色妹孙，把y和兄弟姐妹著色為黑色秋柄，其父結(jié)點(diǎn)z著色為紅色，但是雙紅色問題可能再次出現(xiàn)
刪除
