四、查找 

    一、 知識點(diǎn)　　　　/靜態(tài)查找->數(shù)組　　　
　
　　1、 什么是查找
　　　　　　　　　　\動(dòng)態(tài)查找->鏈樹
　　●順序查找，時(shí)間復(fù)雜度 O(n)
　　●折半查找：條件：有序；時(shí)間復(fù)雜度 O(nlog2n) (時(shí)間復(fù)雜度實(shí)際上是查找樹的高度)
　　●索引查找：條件：第I+1塊的所有元素都大于第Ｉ塊的所有元素。
　　　算法：根據(jù)index來確定X所在的塊（i） 時(shí)間復(fù)雜度：m/2　　　　
　　　　　　在第Ｉ塊里順序查找X　　　　 　時(shí)間復(fù)雜度：n/2 
　　　總的時(shí)間復(fù)雜度：(m+n)/2
　　●二叉排序樹　1）定義：左子樹鍵值大于根節(jié)點(diǎn)鍵值；右子樹鍵值小于根的鍵值，其左右子樹均為二叉排序樹�！�
　　　　　　　　　2）特點(diǎn)：中序遍歷有序->（刪除節(jié)點(diǎn)用到此性質(zhì)）
　　　　　　　　　3）二叉排序樹的查找：如果根大于要查找的樹，則前左子樹前進(jìn)，如果根小于要查找的樹，則向右子樹前進(jìn)。
　　　　　　　　　4）結(jié)點(diǎn)的插入->二叉排序樹的構(gòu)造方法
　　　　　　　　　5）結(jié)點(diǎn)刪除（難點(diǎn)）　 1、右子樹放在左子樹的最右邊
　　　　　　　　　　　　　　　　　　　　2、左子樹放在右子樹的最左邊
　　●avl樹（二叉平衡樹）：左右子樹高度只能差１層，即｜h｜<=1其子樹也一樣。
　　●B樹：n階B樹滿足以下條件　1）每個(gè)結(jié)點(diǎn)（除根外）包含有N～2N個(gè)關(guān)鏈字�！　　　　　　　　　　　　　　　�2）所有葉子節(jié)點(diǎn)都在同一層。
　　　　　　　　　　　　　　　　3）B樹的所有子樹也是一棵B樹。
　　　特點(diǎn)：降低層次數(shù)，減少比較次數(shù)。

上一頁  [1] [2] [3] [4] [5] [6] [7] [8] [9] 下一頁