資料的存儲與檢索是計算機處理資訊最基本的功能，資料需要存儲和使用，是以也會經常被檢索，一般資料檢索有兩種方式，一種叫
集合成員判斷，即在一個資料集合中，确定特定的資料是否在集合中，在具體哪個位置。另一種是
提供用于檢索的資訊，換句話說，需要提供一種和目标資料有聯系的資訊，當檢索該已知資訊時可以直接找到目标資料，這類似于字典查詢。第二種方式中，所提供的資訊被稱為
關鍵碼(key)，與之相關的檢索目标被稱為
相關資料(value)，這種檢索方式又被稱為
基于關鍵碼的資料存儲與檢索。字典
字典由關鍵碼(key)和關聯資料(value)組成，人們通過關鍵碼key來檢索出自己想要的資料value。在字典裡最重要的就是資料的存儲和檢索效率，特别是在存儲資料量和檢索操作特别頻繁的情況下，存儲空間的使用率以及檢索效率顯得格外重要。
字典的操作與效率- 靜态字典：字典一旦建立，字典内容和結構不再變化，主要功能隻有檢索。這種字典建立工作隻需要做一次，但是檢索工作卻可能一直會頻繁往複，是以檢索效率尤其重要。
- 動态字典：初始建立後，仍然允許字典被動态的修改，除了檢索功能之外，還有資料的插入和删除等基本功能。這種字典在實作時不僅要考慮檢索的效率還需要注重資料的插入和删除效率，但是往往這幾種功能是互相沖突的，是以實際情況下需要平衡。
下面是定義一個字典類Assoc：
class Assoc:
def __init__(self,key,value):
self.key=key;self.value=value #關鍵碼和關聯資料的定義
def __lt__(self, other): #考慮大小和排序操作 比如sorted()操作
return self.key<other.key
def __le__(self, other):
return self.key<other.key or self.key == other.key
def __str__(self): #定義字元串表示形式便于輸出和互動
return 'Assoc{(0),(1)}'.format(self.key,self.value) 将關鍵碼關聯的值順序存入線性表，形成關聯的序列，檢索的話就是線上性表裡查找具有特定關鍵碼的資料項，資料項的插入和删除都是普通的線性表操作。這樣的順序字典可以用list來實作，其中關聯可以用前面定義的Assoc對象，也可以用二進制tuple或者list來實作。例如
。但是要檢索特定關鍵碼時，隻能在表中按照順序查找，遇到關鍵碼key時表示檢索成功，并且傳回value，未找到特定關鍵碼時就表示檢索失敗，傳回特殊值。每次檢索都要從表頭順序查找，是以檢索時間複雜度為o(n)。當然如果表是有序的線性表，可以使用
二分檢索法，提高檢索效率。
def bisearch(l,key): #二分檢索法
low,high=0,len(l)-1
while low<=high:
mid=low+(high-low)//2
if key==l[mid].key:
return l[mid].value
if key<l[mid].key:high=mid-1 #在低半區繼續
else:low=mid+1 #在高半區繼續 二分檢索法的時間複雜度為o(logn)，二分法技術隻能适用關鍵碼可以排序，資料按關鍵碼排序的字典，而且隻适用于順序存儲結構，需要連續的存儲塊，不适合實作很大的動态字典。
字典同樣可以考慮采用單連結清單或者雙連結清單來實作。但是采用連結清單來實作字典沒有任何明顯的優勢。也無法利用關鍵碼檢索的價值。
- 如果資料項任意排列，插入操作可以在表頭完成，時間為o(1)，檢索和删除都需要掃描整個表，操作為o(n)。
- 如果表中資料按升降序來排列，插入需要檢索正确的位置，為o(n)操作。檢索和删除同樣需要掃描整個表，o(n)操作。
如果資料連續存儲，關鍵碼就是存儲資料的位址或者下标。
散列的基本思想：如果一個關鍵碼不适合作為資料存儲的下标，則可以通過某種變換把它們映射到一種下标，這樣的話，
基于關鍵碼的檢索就變成基于整數下标的直接元素通路。
散清單的具體方法是：
- 標明一個整數的下标範圍(通常以0，1開始)，建立一個包括相應元素位置範圍的順序表。
- 標明一個從實際關鍵碼集合到上述下标範圍的映射函數h()。
- 在需要存入關鍵碼為key的資料時，将其存入第h(key)個位置。
- 遇到以key為關鍵碼檢索資料時，直接去找表中h(key)位置的資料。
這裡的
h()為散列函數，又稱為哈希函數或雜湊函數，從可能的關鍵碼集合到一個整數區間(下标區間)的映射。一般情況下，可能的關鍵碼集合通常都非常大(例如26個字母組合，有
種可能)，不可能直接作為字典的下标，是以下标集合通常都遠遠小于關鍵碼集合的規模。那麼散列函數h()就是由大集合到小集合的映射，這又會帶來新的問題：必然會出現多個關鍵碼被映射到同一個下标的情況，必然出現
,那麼這裡就出現了
沖突，是以必須考慮基于散清單實作字典時，如何解決沖突的問題？
首先引入
負載因子α的概念，負載因子越大，出現沖突的可能性就越大，顯然擴大散清單存儲空間可以降低負載因子，減小沖突的機率，但負載因子越小，散清單空閑空間的比例也就越大。是以具體執行個體中需要權衡。
負載因子α=散清單中的資料項 / 散清單的基本存儲區能容納的元素個數
散列函數散列函數，就是定義域為
，值域
（下标集合)的映射函數，設計散列函數，
最重要的就是考慮盡可能減少沖突的機率。
1. 折疊法：較長的關鍵碼切成幾段，通過某種運算将其合并。比如關鍵碼為10位數整數，則将其分為3位一段，得到的三位整數相加并去掉進位，結果為散列值。舉個栗子，關鍵碼1234567890，切成3個三位數和1個個位數，将其相加，即123+456+789+0=1368，去掉進位後得到368，這樣就把十位數整數映射到[0,999]區間内了。
2. 中平方法：先求出關鍵碼的平方，然後取出中間幾位作為散列值。對于散列函數的設計一般遵循兩個原則，一是把加大的關鍵碼集合映射到較小區間，一是盡可能消除關鍵碼和映射值之間的規律性，
散列函數映射關系越亂越好，越不清晰越好。3. 除餘法(常用)：若關鍵碼是整數，用key除以一個不大于散清單長度m的值p，以得到的
餘數作為散列值。一般散清單的長度m取2的幂，此時p可取不大于m的
最大素數。比如m取128，512時，p取127，503等，一般表示方式為
。
4. 基數轉換法(常用)：先考慮整數關鍵碼(如果是字元串就考慮其編碼)，去一個正整數r，把關鍵碼看成基數為r的數(r進制)，通常r取素數減少規律性。如果還是不合适可以考慮進一步使用除餘法，把結果歸入下标範圍。
def str_hash(s): #字元串散列函數
h1=0
for c in s:
h1=h1*29+ord(c)
return h1 為了解決散列函數沖突問題，人們提出了2種解決方法：
- 内消解方法(在基本存儲區内部解決沖突問題)
- 外消解方法(在基本的存儲區外部解決沖突)
内消解的基本方法為
開位址法，其基本思想：在準備插入資料并發現沖突時，設法在基本存儲區裡為需要插入的資料項另行安排一個位置，需要設計一種系統的且易于計算的位置安排方式，稱為
探查方式。
首先定義一個遞增數列
,
，定義探查序列為
(除餘法，p為不大于散列長度m的數)。插入資料項時，如果
空閑就直接存入，否則就逐個試探位置
，直至找到第一個空位，并将其資料項存入。
取
，稱為
線性探索；設計另一個散列函數
，令
，稱為
雙散列探索。
舉個栗子：
假設存儲資料的表長度為13，下表範圍為0~12，采用散列函數
，假設有關鍵碼集合
，通過計算可得到h(18)=3，h(73)=8，h(10)=10，h(5)=5，h(68)=3，h(99)=8，h(22)=9，h(32)=6，h(46)=7，h(58)=6，h(25)=12。
首先考慮
線性探查法：如第(1)步，插入前3個數，沒有發生沖突，随後要插入5其散列值也為5，但位置5已經被18給占據，那麼将關鍵碼5插入位置6，随後68存入位置3，99和73在位置8又發生沖突，根據線性探索則将99存入位置9得到第(2)步。下一個值22和99位置沖突，但又在位置10發生沖突，是以将其放入位置11以此類推，最終得到第(3)步。從上面的過程可以看出，
随着插入值越來越多，發生沖突的機率越來越大，新關鍵碼不僅會和之前的同義詞發生沖突也會由于之前沖突而産生遷移的關鍵碼再次産生沖突，情況會越來越糟糕。 其次考慮
雙散列探查法：取
，前3項沒有沖突得到第(1)步，随後關鍵碼5産生沖突，雙散列規則計算
，正好是線性探查，是以将其放入位置6，關鍵碼68存入位置3，關鍵碼99在位置8産生沖突，求出
,往前移動5步即為位置0，發現沒有元素即放入得到第(2)步。以此類推最後得到第(3)步。雙散列探查法在尋找可用位置時跳躍前進，這有可能減小關鍵碼堆積的可能性，但是随着表中元素的增加，情況仍然會變得糟糕。
沖突的外消解：溢出區和桶散列 溢出區方法：開辟一塊溢出存儲區，當插入關鍵碼的散列位置沒有資料時直接插入，發生沖突時将相應資料和關鍵碼一起存入溢出區。資料在溢出區裡順序排列，檢索過程中如果在散列位置發現資料和關鍵碼不比對，則轉為去溢出區繼續尋找。這種方法在發生沖突機率較小的情況下(溢出區資料項很少)，效果很好，但随着溢出區中資料變多，字典的性能也會随之下降。
桶散列(拉鍊法)：在桶散列中，每個資料隻是一個引用域，引用儲存實際資料的存儲桶，在拉鍊法中一個存儲桶就是一個連結的結點，字典中的資料并不存儲在主存儲區裡，而是存入相應結點表的結點裡，具有相同散列的資料都可以儲存在散列值對應的結點表裡，這種方法可以統一處理資料，不考慮關鍵碼是否發生沖突。桶散列結構可用于實作大型字典，組織大量的資料，包括外存的檔案等等。
舉個栗子：
關鍵碼集合
，存儲區有8個存儲位置，散列函數為
，将這些關鍵碼加入字典。
散清單的一些重要性質：散清單無論是外消解還是内消解技術都有一個共同的缺點：随着關鍵碼越多，發生沖突的機率會變大，開位址法中，表中資料增大最終會導緻存儲區溢出；對于溢出區法，資料增多會導緻溢出區元素越來越多，字典的效率會不斷下降；對于桶散列，資料增大，拉鍊的長度就會越長。那麼在負載因子達到一定程度時，可以考慮擴大散清單的存儲空間。存儲區擴大後需要相應調整散列函數，盡可能利用增加的存儲單元，需要把原來的散清單中的元素重新映射到新存儲區。是以擴大存儲區需要付出重新配置設定存儲區和再散列裝入資料的代價。對于散清單，隻需要簡單的擴大存儲，就能從機率上提高字典的存儲效率。這就是
空間換時間原理。 python中的dict字典就是基于散清單實作的。集合
集合有2種表達方式，第一種是
外延表示，将集合種所有的元素全部列出。例如
，第二種是
描述表示，具體寫法是
，e可以是元素或者表達式，p描述了一些變量的性質，例如
。
簡單線性表實作：兩種可以實作集合的方式：(1)插入元素時，檢查集合中是否已經存在相同元素，保證集合元素的唯一性。删除元素找到第一個相同的元素并删除。(2)插入元素時簡單的将其加入集合；删除元素時要檢查整個表，删除所有指定元素的拷貝(隻保留一個元指定素，插入操作過于簡單可能導緻集合中存在多個相同的元素)。
排序順序表實作：如果在集合中元素存在某種序的關系，那麼檢索元素的時間複雜度隻需要o(logn)，與簡單線性表相比有質的改進。一般插入元素的過程為：1.用
二分法檢索再集合中查找插入元素。2.如果找到就結束。3.否則也确定了插入位置，後移後面的元素并插入元素。另外采用排序方式存儲表中元素可以很大提高集合運算效率(交并差)。下面是一段求交集的代碼實作，這裡假設s和t是從小到大排列的順序表，代表S和T兩個集合。
def cross_set(s,t):
i=j=0;r=[] #r為交集
while i<len(s) and j<len(t):
if s[i]>t[j]:j+=1
elif s[i]<t[j]:i+=1
else: #s[i]=t[j]
r.append(s[i])
i+=1;j+=1
return r 假設s和t的長度為m和n，該算法時間複雜度為o(m+n)，即兩個集合的i，j全部升完，必能找到所有相同元素。與簡單線性表求交集操作相比，有很大的提升。簡單線性表交集操作為o(mxn)，因為線性表不存在序，一個集合的元素必須周遊另一個集合才能判斷是否有重複。并集和差集操作與次類似，不再贅述。
散清單的實作：一個集合就是一個散清單；插入/删除操作對應于散清單的插入/删除關鍵碼；集合元素判斷對應于關鍵碼檢索；集合運算可以采用上述操作并建立一個散清單進行實作。在最好的情況下，插入/操作複雜度為o(1)，集合運算的複雜度為o(m+n)。
位向量實作：假設2個集合S和T的并集為
，子集中包含U中元素的記為1，不包含的記為0。那麼U的任何子集都可以用7位的位向量表示，{}表示為0000000，U表示為1111111，
表示為1101010，
表示為0111101，根據位向量可以進行集合的運算。集合的位向量比較緊湊，空間使用率高，在一些情況下比較适用，全集U的規模适當。位向量經常用于操作效率要求較高，或者存儲資源比較受限的情況下。
python的标準字典類與集合類——dict和setpython中dict和set都是基于散清單的技術實作，采用内消解技術解決沖突。下面介紹一下python中dict的一些性質：
- dict基于散清單技術實作，元素為key-value，關鍵碼是任意不可變對象，值是任意可變對象。
- 在建立字典或者很小字典時，初始配置設定的存儲區可容納8個元素
- dict負載因子超過2/3時自動更換更大的存儲區，并把已儲存内容重新配置設定到新存儲區中，如果目前字典不太大，就以當時字典中實際配置設定的4倍配置設定到新存儲區，字典元素超過50000時改為按實際元素的2倍配置設定新存儲區。
，是為了保證散清單的完整性(保證資料項檢索和删除的正确實作)，如果允許關鍵碼為可變對象，插入元素根據關鍵碼散列的位置在關鍵碼改變之後就不符合散列檢查的規則，無法正确找到它們。如果需要修改關鍵碼，則先将原關鍵碼和關聯資料删除，再重新插入新的關鍵碼。
二叉排序樹和字典
二叉排序樹是一種存儲資料的二叉樹，把字典的資料存儲和查詢功能融合在二叉樹的結構裡，采用二叉樹作為字典存儲結構，有可能得到較高的檢索效率，采用連結式的實作方式，資料項的輸入删除操作都比較靈活友善。
其基本思想為：
- 在二叉樹結點中存儲字典中的資訊。
- 為二叉樹安排好一種字典資料項的存儲方式，使字典查詢等操作可以利用二叉樹高度遠小于結點數的性質。使檢索能夠沿着路徑(父子關系)，進而得到更高的檢索效率。
二叉排序樹可用于實作關鍵碼有序的字典，樹中資料的存儲和使用都利用了資料的序。
二叉排序樹的性質：
- 根結點一定儲存一項資料及其關鍵碼。
- 如果其左子樹不空，則左子樹上所有結點儲存的值都不大于根結點儲存的值。
- 如果其右子樹不空，則右子樹所有結點儲存的值都不小于根結點儲存的值。
- 非空的左子樹和右子樹也是二叉排序樹
- 一棵結點中存儲着關鍵碼(資料)的二叉樹為二叉排序樹， 當且僅當通過中序周遊時 ， 這棵二叉排序樹得到的關鍵碼序列為遞增序列。（很重要的性質！）
def bt_search(btree,key): #二叉排序樹的檢索
bt=btree
while bt is not None:
entry=bt.data #根結點
if key <entry.key:bt=bt.left #左子樹檢索
elif key >entry.key:bt=bt.right #右子樹檢索
else:return entry.value #如果發現相同的，則傳回值
return None #如果未找到則傳回None 這裡定義一個二叉排序樹的字典類：
class DictBinTree:
def __init__(self):
self._root=None #根結點屬性
def is_empty(self): #判斷二叉排序樹是否為空
return self._root is None
def search(self,key): #二叉樹檢索方法
bt=self._root
while bt is not None:
entry=bt.data
if key<entry.key:bt=bt.left
elif key>entry.key:bt=bt.right
else:return entry.value
return None 接下來要定義二叉排序樹字典的插入功能，當插入元素時遇到關鍵碼相同的該怎麼辦？可以選擇報錯，可以選擇什麼都不做，也可以允許重複的關鍵碼存在插入新的結點，也可以用新的value值代替原來的。這裡實作的就是用新值代替原值。插入元素的過程如下：
- 如果二叉樹為空，那麼建立一個包括新關鍵碼和新值的根結點
- 遇到應該向左子樹走但左子樹為空的時候，或者往右走右子樹為空時，就是找到了新字典項的插入位置，構造新結點并插入位置。
- 遇到結點裡的關鍵碼等于被檢索關鍵碼時，直接替換關聯值并且替換掉。
def insert(self,key,value):
bt=self._root
if bt is None:
self._root=BinTNode(Assoc(key,value)) #若二叉樹為空，則根結點插入 BinTNode為二叉樹結點類，Assoc為字典類
return
while True:
entry=bt.data
if key<entry.key:
if bt.left is None:
bt.left=BinTNode(Assoc(key,value)) #若左子樹為空，則直接插入左子樹結點
return
bt=bt.left
elif key>entry.key:
if bt.right is None:
bt.right=BinTNode(Assoc(key,value)) #若右子樹為空，則直接插入右子樹結點
return
bt=bt.right
else:
bt.data.value=value #相同關鍵碼，替換掉原值
return 如果我們想要用for循環周遊字典的值,那麼我們可以同樣實作一個疊代器
def values(self): #中序周遊 傳回的值為增序序列 其他周遊無太大意義
t,s=self._root,SStack() #建立一個棧
while t is not None:
s.push(t);t=t.left
t=s.pop()
yield t.data.value #傳回疊代的value
t=t.right 這裡是用疊代器周遊所有的value，那麼有時候我們想要周遊鍵值對怎麼辦？是否可以直接修改上述代碼
yield t.data.value→yield t.data，肯定是不行的，因為這樣傳回的是一個Assoc類(字典類)，是一個可變對象，客戶有意無意會修改這個類，一旦被修改就會破壞二叉排序樹的結構。是以需要一個安全穩定的方式來傳回鍵值對。
yield t.data.key,t.data.value #一定要保證傳回的是不可變對象，防止被修改 下面是二叉排序樹最複雜的·操作——删除操作。要求簡而言之就是
删除所要求的元素之後，剩下的結構還必須是二叉排序樹。有一種方式是指定要删除的資料項，重新建構一棵新的二叉排序樹，建構過程中丢掉指定的資料項。這種方法代價很高，需要耗費樹中結點成比例的時間。我們當然希望的是能夠定位到删除元素，盡量在原有結構基礎之上做局部微小的調整，使得元素删除之後，仍然是一棵二叉排序樹。
我們假設已經确定了要删除的元素q，它是其父結點p的左子結點（右子結點情況類似），這是兩種情況：
- q是葉節點，這時隻需要将p到q的引用置為None，删除就完成了，顯然樹中剩下的結點仍然構成二叉排序樹。
- q不是葉節點，需要将q的子樹連接配接到删除q之後的樹中，而且要保證關鍵碼的順序：
(1) 如果q沒有左子結點，這是直接将右子結點該作q的父結點p的左子樹。
(2)如果q有左子樹，這時先找到q左子樹的最右的子孫結點，設為r，顯然他已經是葉結點，不再有右子樹。用q的左子結點代替q作為p的左子結點，并将q的右子樹作為r的右子樹。
以下為删除結點q時候的兩種情況圖示：
def delete(self,key):
p,q=None,self._root #維持p，q的父結點
while q is not None and q.data.key!=key:
p=q
if key<q.data.key:q=q.left
elif key>q.data.key:q=q.right
if q is None:return #未找到關鍵碼
if q.left is None: #删除的結點沒有左子樹時
if p is None: #說明根結點相等
self._root=q.right
elif q is p.left:
p.left=q.right
else:p.right=q.right
return
r=q.left #删除結點有左子樹時
while r.right is not None:
r=r.right #循環找出左子樹最右結點
r.right=q.right #将删除結點的右子樹接到左子樹最右結點上
if p is None:self._root=q.left
elif p.left is q:p.left=q.left #删除結點左子樹接到父結點左子樹上
else:p.right=q.left 假設給定了遞增的關鍵碼序列key0，key1，key2....，需要構造的内部結點分别與關鍵碼對應，為w0，w1，w2...相應的外部結點為e0，e1，e2.....（擴充二叉樹），假設檢索到達w0，w1，w2...而檢索成功的頻度為p0，p1，p2...，檢索到達e0，e1，e2...而檢索失敗的頻度為q0，q1，q2...，現在要構造一棵二叉排序樹平均檢索長度最小，也就是使函數
達到最小，
是包含n個内部結點和n+1個外部結點的樹的帶權路徑。
三張圖充分展示了某關鍵碼集合為{A，B，C}，内部結點的權值為{2，3，7}，外部結點的權值為{2，1，4，9}，如何構造出包含3個内部結點，4個外部結點的最佳二叉排序樹。
- 首先構造出隻包含1個内部結點和2個外部結點的最佳二叉樹(隻包含一個内結點的二叉樹自然是最佳二叉樹)，由圖(1)所示隻有T(0,1)，T(1,2)和T(2,3)3種，其中T(0,n)表示内部結點為0,1,2....n-1，外部結點為0,1,2....n的最佳二叉排序樹。
- 構造包含2個内結點的最佳二叉樹T(i,i+2)，根據圖2可看出有T(0,2)和T(1,3)2種最佳二叉排序樹，但是T(0,2)的建構有2種可能，一種以e0為左子樹，T(1,2)為右子樹，w0為樹根；一種以T(0,1)為左子樹，e2為右子樹，w1為樹根。此時計算帶權值的路徑長度選擇最短的作為最佳二叉樹。T(1,3)的二叉樹以此類推。
- 建構包含3個内結點的最佳二叉樹T(i,i+3)，根據圖3看出有T(0,3)的最佳二叉樹，那麼建構它有三種可能性，一是以w0為根結點，e0為左子樹，T(1,3)為右子樹。第二種是以w1為根結點，以T(0,1)為左子樹，以T(2,3)為右子樹。第三種是以w2為根結點，以T(0,2)為左子樹，以e3為右子樹。分别計算他們的帶權路徑長度，去最短的作為T(0,3)的構造。
這個時候可以總結一下一般的步驟：
- 構造出所有隻包含一個内結點的最佳二叉樹，如T(0,1)，T(1,2)...
- 基于第一步得到的結果，構造出所有包含2個内部結點的最佳二叉排序樹，T(0,2)，T(1,3)，T(2,4)....(每個最佳二叉排序樹可能有多個選擇，選擇路徑長度最小的那個作為最佳二叉樹)。
- .........
- 根據第n-1部得到的結果，構造出T(0,n)。
下面考慮如何用算法去實作：
我們用二維表
- r[i][j]來記錄構造出的最佳二叉樹T(i,j)的根結點下标；
- c[i][j]來記錄子樹T(i,j)的代價；
- w[i][j]來表示樹中相應的内外交錯結點段的權值之和；
def build_opt_btree(wp,wq):
num=len(wp)+1
if len(wq)!=num:
raise ValueError
w=[[0]*num for j in range (num)]
c=[[0]*num for j in range(num)]
r=[[0]*num for i in range(num)]
for i in range(num):
w[i][j]=wq[i]
for j in range(i+1,num):
w[i][j]=w[i][j-1]+wp[j-1]+wq[j]
for i in range(0,num-1):
c[i][i+1]=w[i][i+1]
r[i][i+1]=i
for m in range(2,num):
for i in range(0,num-m):
k0,j=i,i+m
wmin=inf
for k in range(i,j):
if c[i][k]*c[k+1][j]<wmin:
wmin=c[i][k]+c[k+1][j]
k0=k
c[i][j]=w[i][j]*wmin
r[i][j]=k0
return c,r 時間複雜度為o(n^2)，空間複雜度為o(n^2)。
動态規劃思想是非常重要的算法之一，其特點就是：
在整個計算過程中，逐漸建立并維持好一大批子問題(這裡維護的是較小的最佳二叉樹)，在每一步基于這些小的子問題的解建構出更大的子問題，最終構造出整個問題的解。 平衡二叉樹(AVL樹)建構最佳二叉排序樹的前提是，我們事先知道所有的結點以及對應的權值，除此之外二叉排序樹隻支援靜态字典，不能夠很好的支援動态操作，由于最佳二叉樹要時刻保持其“最佳”狀态，是以插入和删除操作很容易破壞掉這種狀态，即使有好的算法可以在插入和删除操作過程中始終維持其“最佳”狀态，但是這種恢複代價一定很高。實際應用當中，人們需要的是既能維持高效檢索，又能支援動态操作的排序樹結構。最基本的追求是檢索時的時間複雜度為o(logn)。除此之外還要保證插入和删除的動态操作性能也具有o(logn)的複雜度。
定義和性質基本思想：樹中每個結點的左右子樹高度差不多，整個樹的結構比較好，不會出現特别長的路徑。
性質：或為空樹，或者其左右子樹同樣是平衡二叉樹(遞歸結構)，左右子樹的高度差不超過1。
平衡因子BF(Balance factor)：左子樹高度與右子樹高度隻差，取值為{-1,0,1}，在平衡二叉樹結點裡并不記錄左右子樹的高度，隻記錄BF值。
圖中結點旁的數字為BF值，葉結點的BF值都為0，是以不現實。圖(1)和圖(2)為平衡二叉樹，圖(3)因為結點BF值超過1，是以為不平衡二叉樹。
AVL樹的插入操作：如果在檢索過程中，所有途徑的結點BF值都為0，則插入結點并不會導緻失衡，隻不過結點的BF值變為1或-1。如果不是上面的情況，那麼一定存在一棵包含實際插入點的
最小非平衡子樹，即那棵包含新結點插入位置的。其根結點BF非0的最小子樹。我們假設所在的最小非平衡子樹的根結點為a，左子樹較高（右子樹較高情況類似），如下圖(1)，如果插入結點位置在右子樹(較低的樹)，那麼插入之後隻需要調整結點a到插入點路徑上所有結點的BF值即可。a的BF值修改為0。如果新結點需要插入左子樹，a的平衡就被破壞，這時就需要恢複樹的平衡，如下圖(2)所示。數的平衡恢複分為四種情況：(1)LL調整：左子樹較高，新結點插入左子樹的左子樹；(2)LR調整：左子樹較高，新結點插入左子樹的右子樹；(3)RL調整：右子樹較高，新結點插入右子樹的左子樹；(4)RR調整：右子樹較高，新結點插入右子樹的右子樹；
LL(RR)失衡和調整：下圖樹的順序為AbBaC，新結點插入A樹，導緻結點a失衡，如下圖(2)，這時做一個順時針旋轉，調整結點a和b的關系，将結點b作為根結點，a作為b的右子結點，b原來的右子樹作為a的左子樹，這時BF都調整為正常值，平衡恢複。另外調整後的樹順序為A'bBaC，A'為适當位置新結點加入的關鍵碼，可以看出并沒有破壞結點的順序。RR調整情況與LL調整類似。
LR(RL)失衡和調整：以a為根的子樹結點序列AbBcCaD。新結點要插入左子樹(較高)的右子樹上，如下圖(2)，接下來把c作為根結點，b和a作為c的左右子結點如下圖(3)所示，無論新結點插入c子樹的哪個位置，都不會失衡。調整後子樹的高度和插入前一樣，并且對稱序列為AbB'cC'aD，并沒有破壞結點的順序。
以下的圖描述了完整的平衡二叉樹的建構：
時間複雜度分析：插入結點最大時間開銷受限于樹的深度，o(logn)。四種調整操作都是在最小不平衡子樹上進行的，是o(1)關系，是以平均時間複雜度為o(logn)。
AVL樹的删除操作：(1)檢索需要删除的結點；(2)把删除任意結點的問題變成删除某棵子樹的最右結點的問題，隻需要找到被删除結點左子樹的最右結點并交換二者位置；(3)實際删除結點；(4)如果出現樹失衡，則進行調整。
AVL樹的删除操作時調整始終在樹中的一條路徑上進行，是以時間複雜度為o(logn)。綜合來說，AVL樹具有很好的動态插入和删除性能。
幾種二叉排序樹的對比：- 簡單二叉排序樹支援字典操作，檢索效率為o(logn)。插入和删除操作比較簡單，但是缺點是這種操作的高效率得不到保證，删除和插入操作是自然形成的沒有認為的控制，結構可能會發生退化。
- 最佳二叉排序樹構造比較費事，但能保證最高的檢索效率，但如果需要插入和删除操作，維持其最佳性能代價過大，不适用于動态字典。
- 平衡二叉排序樹(AVL樹)的檢索效率與最佳二叉樹處在同一數量級，優點是插入和删除操作可以在局部操作完成複雜度都不超過o(logn)。用于實作動态字典，長期運作和反複動态修改時，可以始終保持o(logn)的操作複雜度，缺點就是操作的實作比較複雜。
紅黑樹是一種自平衡的二叉查找樹，是一種高效的查找樹。它可在
O(logN)
時間内完成查找、增加、删除等操作，是以，紅黑樹在業界應用很廣泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于紅黑樹結構實作的。
紅黑樹具有以下幾種性質：
- 節點是紅色或黑色。
- 根是黑色。
- 所有葉子都是黑色（葉子是NIL節點）。
- 每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）
- 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點（簡稱黑高）。
這些性質可以避免二叉排序樹退化成連結清單的情況，僅僅避免這種情況還不夠，這裡還要考慮某個節點到其每個葉子節點路徑長度的問題。如果某些路徑長度過長，那麼，在對這些路徑上的及诶單進行增删查操作時，效率也會大大降低。這個時候性質4和性質5用途就凸顯了，有了這兩個性質作為限制，即可保證任意節點到其每個葉子節點路徑最長不會超過最短路徑的2倍。原因如下：
當某條路徑最短時，這條路徑必然都是由黑色節點構成。當某條路徑長度最長時，這條路徑必然是由紅色和黑色節點相間構成（性質4限定了不能出現兩個連續的紅色節點）。而性質5又限定了從任一節點到其每個葉子節點的所有路徑必須包含相同數量的黑色節點。此時，在路徑最長的情況下，路徑上紅色節點數量 = 黑色節點數量。該路徑長度為兩倍黑色節點數量，也就是最短路徑長度的2倍。
關于紅黑樹的玄旋轉，插入和删除操作，這裡不詳細贅述，可以參考下面的部落格：
人類身份驗證 - SegmentFaultsegmentfault.com
B樹B樹是一種動态多分支排序樹，通過維護結點分支數來保持樹具有良好的結構。B樹常用于實作大型資料庫的索引B樹的結點用外存存儲快大小的塊表示，記錄的是關鍵碼到資料存儲位置的索引，一個結點裡可能有很多個索引。下圖中階的意思是樹中結點的最大分支數。4階表示，樹中每個結點最多有4個分支。
在B-樹中查找給定關鍵字的方法是，首先把根結點取來，在根結點所包含的關鍵字K1,…,Kn查找給定的關鍵字（可用順序查找或二分查找法），若找到等于給定值的關鍵字，則查找成功；否則，一定可以确定要查找的關鍵字在Ki與Ki+1之間，Pi為指向子樹根節點的指針，此時取指針Pi所指的結點繼續查找，直至找到，或指針Pi為空時查找失敗。(來自百度百科)
其實B樹隻不過是單結點可能包含多個關鍵碼的二叉排序樹，當所要找的關鍵碼在某結點包含，則成功檢索，如果未找到，則可知道在該結點所包含的關鍵碼的範圍中，然後遵循着該範圍的路徑繼續往子樹查找。
下圖為B樹的删除和插入操作：
B+樹和B樹結構類似，但在這裡，分支結點裡的關鍵碼并不是區分關鍵碼，而可以看成子樹的索引關鍵碼，分支結點的關鍵碼并不關聯資料項，隻有葉結點的關鍵碼關聯資料項。一個葉結點可以看作一個基本索引塊，分支結點可以看成索引的索引。
參考書籍：《資料結構與算法—python語言描述》—裘宗燕