四、查找 

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

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