查找算法 -- 簡介

查找(Searching)就是根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素。

查找表(Search Table)：由同一類型的數(shù)據(jù)元素構成的集合

關鍵字(Key)：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，又稱為鍵值

主鍵(Primary Key)：可唯一的標識某個數(shù)據(jù)元素或記錄的關鍵字

查找表按照操作方式可分為：

1.靜態(tài)查找表(Static Search Table)：只做查找操作的查找表。它的主要操作是：

①查詢某個“特定的”數(shù)據(jù)元素是否在表中

②檢索某個“特定的”數(shù)據(jù)元素和各種屬性

2.動態(tài)查找表(Dynamic Search Table)：在查找中同時進行插入或刪除等操作：

①查找時插入數(shù)據(jù)

②查找時刪除數(shù)據(jù)

順序查找

算法簡介

順序查找又稱為線性查找，是一種最簡單的查找方法。適用于線性表的順序存儲結構和鏈式存儲結構。該算法的時間復雜度為O(n)。

基本思路

從第一個元素m開始逐個與需要查找的元素x進行比較，當比較到元素值相同(即m=x)時返回元素m的下標，如果比較到最后都沒有找到，則返回-1。

優(yōu)缺點

缺點：是當n 很大時，平均查找長度較大，效率低；優(yōu)點：是對表中數(shù)據(jù)元素的存儲沒有要求。另外，對于線性鏈表，只能進行順序查找。

算法實現(xiàn)

# 最基礎的遍歷無序列表的查找算法

# 時間復雜度O(n)

def sequential_search(lis, key):

length = len(lis)

for i in range(length):

if lis[i] == key:

return i

else:

return False

if __name__ == '__main__':

LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]

result = sequential_search(LIST, 123)

print(result)

二分查找

算法簡介

二分查找(Binary Search)，是一種在有序數(shù)組中查找某一特定元素的查找算法。查找過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則查找過程結束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種查找算法每一次比較都使查找范圍縮小一半。

算法描述

給予一個包含n個帶值元素的數(shù)組A

1、 令 L為0 ， R為 n-1 ；2、 如果L>R，則搜索以失敗告終 ；3、 令 m (中間值元素)為??(L+R)/2?；4、 如果 AmT，令 R為 m - 1?并回到步驟二；

復雜度分析

時間復雜度：折半搜索每次把搜索區(qū)域減少一半，時間復雜度為O(logn)空間復雜度：O(1)

算法實現(xiàn)

# 針對有序查找表的二分查找算法

def binary_search(lis, key):

low = 0

high = len(lis) - 1

time = 0

while low < high:

time += 1

mid = int((low + high) / 2)

if key < lis[mid]:

high = mid - 1

elif key > lis[mid]:

low = mid + 1

else:

# 打印折半的次數(shù)

print("times: %s" % time)

return mid

print("times: %s" % time)

return False

if __name__ == '__main__':

LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]

result = binary_search(LIST, 99)

print(result)

插值查找

算法簡介

插值查找是根據(jù)要查找的關鍵字key與查找表中最大最小記錄的關鍵字比較后的?查找方法，其核心就在于插值的計算公式?(key-a[low])/(a[high]-a[low])*(high-low)。時間復雜度o(logn)但對于表長較大而關鍵字分布比較均勻的查找表來說，效率較高。

算法思想

基于二分查找算法，將查找點的選擇改進為自適應選擇，可以提高查找效率。當然，差值查找也屬于有序查找。

注：對于表長較大，而關鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數(shù)組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。

復雜度分析

時間復雜性：如果元素均勻分布，則O(log log n))，在最壞的情況下可能需要?O(n)?？臻g復雜度：O(1)。

算法實現(xiàn)

# 插值查找算法

def binary_search(lis, key):

low = 0

high = len(lis) - 1

time = 0

while low < high:

time += 1

# 計算mid值是插值算法的核心代碼

mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))

print("mid=%s, low=%s, high=%s" % (mid, low, high))

if key < lis[mid]:

high = mid - 1

elif key > lis[mid]:

low = mid + 1

else:

# 打印查找的次數(shù)

print("times: %s" % time)

return mid

print("times: %s" % time)

return False

if __name__ == '__main__':

LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]

result = binary_search(LIST, 444)

print(result)

斐波那契查找

算法簡介

斐波那契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、····，在數(shù)學上，斐波那契被遞歸方法如下定義：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) (n>=2)。該數(shù)列越往后相鄰的兩個數(shù)的比值越趨向于黃金比例值(0.618)。

算法描述

斐波那契查找就是在二分查找的基礎上根據(jù)斐波那契數(shù)列進行分割的。在斐波那契數(shù)列找一個等于略大于查找表中元素個數(shù)的數(shù)F[n]，將原查找表擴展為長度為F[n](如果要補充元素，則補充重復最后一個元素，直到滿足F[n]個元素)，完成后進行斐波那契分割，即F[n]個元素分割為前半部分F[n-1]個元素，后半部分F[n-2]個元素，找出要查找的元素在那一部分并遞歸，直到找到。

復雜度分析

最壞情況下，時間復雜度為O(log2n)，且其期望復雜度也為O(log2n)。

算法實現(xiàn)

# 斐波那契查找算法

# 時間復雜度O(log(n))

def fibonacci_search(lis, key):

# 需要一個現(xiàn)成的斐波那契列表。其最大元素的值必須超過查找表中元素個數(shù)的數(shù)值。

F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,

233, 377, 610, 987, 1597, 2584, 4181, 6765,

10946, 17711, 28657, 46368]

low = 0

high = len(lis) - 1

# 為了使得查找表滿足斐波那契特性，在表的最后添加幾個同樣的值

# 這個值是原查找表的最后那個元素的值

# 添加的個數(shù)由F[k]-1-high決定

k = 0

while high > F[k]-1:

k += 1

print(k)

i = high

while F[k]-1 > i:

lis.append(lis[high])

i += 1

print(lis)

# 算法主邏輯。time用于展示循環(huán)的次數(shù)。

time = 0

while low <= high:

time += 1

# 為了防止F列表下標溢出，設置if和else

if k < 2:

mid = low

else:

mid = low + F[k-1]-1

print("low=%s, mid=%s, high=%s" % (low, mid, high))

if key < lis[mid]:

high = mid - 1

k -= 1

elif key > lis[mid]:

low = mid + 1

k -= 2

else:

if mid <= high:

# 打印查找的次數(shù)

print("times: %s" % time)

return mid

else:

print("times: %s" % time)

return high

print("times: %s" % time)

return False

if __name__ == '__main__':

LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]

result = fibonacci_search(LIST, 444)

print(result)

樹表查找

1、二叉樹查找算法。

算法簡介

二叉查找樹是先對待查找的數(shù)據(jù)進行生成樹，確保樹的左分支的值小于右分支的值，然后在就行和每個節(jié)點的父節(jié)點比較大小，查找最適合的范圍。?這個算法的查找效率很高，但是如果使用這種查找方法要首先創(chuàng)建樹。

算法思想

二叉查找樹(BinarySearch Tree)或者是一棵空樹，或者是具有下列性質的二叉樹：

1)若任意節(jié)點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

2)若任意節(jié)點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

3)任意節(jié)點的左、右子樹也分別為二叉查找樹。

二叉查找樹性質：對二叉查找樹進行中序遍歷，即可得到有序的數(shù)列。

復雜度分析

它和二分查找一樣，插入和查找的時間復雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間復雜度。原因在于插入和刪除元素的時候，樹沒有保持平衡。

算法實現(xiàn)

# 二叉樹查找 Python實現(xiàn)

class BSTNode:

"""

定義一個二叉樹節(jié)點類。

以討論算法為主，忽略了一些諸如對數(shù)據(jù)類型進行判斷的問題。

"""

def __init__(self, data, left=None, right=None):

"""

初始化

:param data: 節(jié)點儲存的數(shù)據(jù)

:param left: 節(jié)點左子樹

:param right: 節(jié)點右子樹

"""

self.data = data

self.left = left

self.right = right

class BinarySortTree:

"""

基于BSTNode類的二叉查找樹。維護一個根節(jié)點的指針。

"""

def __init__(self):

self._root = None

def is_empty(self):

return self._root is None

def search(self, key):

"""

關鍵碼檢索

:param key: 關鍵碼

:return: 查詢節(jié)點或None

"""

bt = self._root

while bt:

entry = bt.data

if key < entry:

bt = bt.left

elif key > entry:

bt = bt.right

else:

return entry

return None

def insert(self, key):

"""

插入操作

:param key:關鍵碼

:return: 布爾值

"""

bt = self._root

if not bt:

self._root = BSTNode(key)

return

while True:

entry = bt.data

if key < entry:

if bt.left is None:

bt.left = BSTNode(key)

return

bt = bt.left

elif key > entry:

if bt.right is None:

bt.right = BSTNode(key)

return

bt = bt.right

else:

bt.data = key

return

def delete(self, key):

"""

二叉查找樹最復雜的方法

:param key: 關鍵碼

:return: 布爾值

"""

p, q = None, self._root # 維持p為q的父節(jié)點，用于后面的鏈接操作

if not q:

print("空樹！")

return

while q and q.data != key:

p = q

if key < q.data:

q = q.left

else:

q = q.right

if not q: # 當樹中沒有關鍵碼key時，結束退出。

return

# 上面已將找到了要刪除的節(jié)點，用q引用。而p則是q的父節(jié)點或者None(q為根節(jié)點時)。

if not q.left:

if p is None:

self._root = q.right

elif q is p.left:

p.left = q.right

else:

p.right = q.right

return

# 查找節(jié)點q的左子樹的最右節(jié)點，將q的右子樹鏈接為該節(jié)點的右子樹

# 該方法可能會增大樹的深度，效率并不算高?？梢栽O計其它的方法。

r = q.left

while r.right:

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

def __iter__(self):

"""

實現(xiàn)二叉樹的中序遍歷算法,

展示我們創(chuàng)建的二叉查找樹.

直接使用python內置的列表作為一個棧。

:return: data

"""

stack = []

node = self._root

while node or stack:

while node:

stack.append(node)

node = node.left

node = stack.pop()

yield node.data

node = node.right

if __name__ == '__main__':

lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]

bs_tree = BinarySortTree()

for i in range(len(lis)):

bs_tree.insert(lis[i])

# bs_tree.insert(100)

bs_tree.delete(58)

for i in bs_tree:

print(i, end=" ")

# print("\n", bs_tree.search(4))

2、平衡查找樹之2-3查找樹(2-3 Tree)

2-3查找樹定義

和二叉樹不一樣，2-3樹運行每個節(jié)點保存1個或者兩個的值。對于普通的2節(jié)點(2-node)，他保存1個key和左右兩個自己點。對應3節(jié)點(3-node)，保存兩個Key，2-3查找樹的定義如下：

1)要么為空，要么：

2)對于2節(jié)點，該節(jié)點保存一個key及對應value，以及兩個指向左右節(jié)點的節(jié)點，左節(jié)點也是一個2-3節(jié)點，所有的值都比key要小，右節(jié)點也是一個2-3節(jié)點，所有的值比key要大。

3)對于3節(jié)點，該節(jié)點保存兩個key及對應value，以及三個指向左中右的節(jié)點。左節(jié)點也是一個2-3節(jié)點，所有的值均比兩個key中的最小的key還要小；中間節(jié)點也是一個2-3節(jié)點，中間節(jié)點的key值在兩個跟節(jié)點key值之間；右節(jié)點也是一個2-3節(jié)點，節(jié)點的所有key值比兩個key中的最大的key還要大。

2-3查找樹的性質

1)如果中序遍歷2-3查找樹，就可以得到排好序的序列；

2)在一個完全平衡的2-3查找樹中，根節(jié)點到每一個為空節(jié)點的距離都相同。(這也是平衡樹中“平衡”一詞的概念，根節(jié)點到葉節(jié)點的最長距離對應于查找算法的最壞情況，而平衡樹中根節(jié)點到葉節(jié)點的距離都一樣，最壞情況也具有對數(shù)復雜度。)

2-3樹的查找效率與樹的高度是息息相關的。

距離來說，對于1百萬個節(jié)點的2-3樹，樹的高度為12-20之間，對于10億個節(jié)點的2-3樹，樹的高度為18-30之間。對于插入來說，只需要常數(shù)次操作即可完成，因為他只需要修改與該節(jié)點關聯(lián)的節(jié)點即可，不需要檢查其他節(jié)點，所以效率和查找類似。

算法實現(xiàn)

class Node(object):

def __init__(self,key):

self.key1=key

self.key2=None

self.left=None

self.middle=None

self.right=None

def isLeaf(self):

return self.left is None and self.middle is None and self.right is None

def isFull(self):

return self.key2 is not None

def hasKey(self,key):

if (self.key1==key) or (self.key2 is not None and self.key2==key):

return True

else:

return False

def getChild(self,key):

if key

return self.left

elif self.key2 is None:

return self.middle

elif key

return self.middle

else:

return self.right

class 2_3_Tree(object):

def __init__(self):

self.root=None

def get(self,key):

if self.root is None:

return None

else:

return self._get(self.root,key)

def _get(self,node,key):

if node is None:

return None

elif node.hasKey(key):

return node

else:

child=node.getChild(key)

return self._get(child,key)

def put(self,key):

if self.root is None:

self.root=Node(key)

else:

pKey,pRef=self._put(self.root,key)

if pKey is not None:

newnode=Node(pKey)

newnode.left=self.root

newnode.middle=pRef

self.root=newnode

def _put(self,node,key):

if node.hasKey(key):

return None,None

elif node.isLeaf():

return self._addtoNode(node,key,None)

else:

child=node.getChild(key)

pKey,pRef=self._put(child,key)

if pKey is None:

return None,None

else:

return self._addtoNode(node,pKey,pRef)

def _addtoNode(self,node,key,pRef):

if node.isFull():

return self._splitNode(node,key,pRef)

else:

if key

node.key2=node.key1

node.key1=key

if pRef is not None:

node.right=node.middle

node.middle=pRef

else:

node.key2=key

if pRef is not None:

node.right=Pref

return None,None

def _splitNode(self,node,key,pRef):

newnode=Node(None)

if key

pKey=node.key1

node.key1=key

newnode.key1=node.key2

if pRef is not None:

newnode.left=node.middle

newnode.middle=node.right

node.middle=pRef

elif key

pKey=key

newnode.key1=node.key2

if pRef is not None:

newnode.left=Pref

newnode.middle=node.right

else:

pKey=node.key2

newnode.key1=key

if pRef is not None:

newnode.left=node.right

newnode.middle=pRef

node.key2=None

return pKey,newnode

3、平衡查找樹之紅黑樹(Red-Black Tree)

紅黑樹的定義

紅黑樹是一種具有紅色和黑色鏈接的平衡查找樹，同時滿足：

① 紅色節(jié)點向左傾斜 ；

②一個節(jié)點不可能有兩個紅色鏈接；

③整個樹完全黑色平衡，即從根節(jié)點到所以葉子結點的路徑上，黑色鏈接的個數(shù)都相同。

紅黑樹的性質

整個樹完全黑色平衡，即從根節(jié)點到所以葉子結點的路徑上，黑色鏈接的個數(shù)都相同(2-3樹的第2)性質，從根節(jié)點到葉子節(jié)點的距離都相等)。

復雜度分析

最壞的情況就是，紅黑樹中除了最左側路徑全部是由3-node節(jié)點組成，即紅黑相間的路徑長度是全黑路徑長度的2倍。下圖是一個典型的紅黑樹，從中可以看到最長的路徑(紅黑相間的路徑)是最短路徑的2倍：

算法實現(xiàn)

#紅黑樹

from random import randint

RED = 'red'

BLACK = 'black'

class RBT:

def __init__(self):

# self.items = []

self.root = None

self.zlist = []

def LEFT_ROTATE(self, x):

# x是一個RBTnode

y = x.right

if y is None:

# 右節(jié)點為空，不旋轉

return

else:

beta = y.left

x.right = beta

if beta is not None:

beta.parent = x

p = x.parent

y.parent = p

if p is None:

# x原來是root

self.root = y

elif x == p.left:

p.left = y

else:

p.right = y

y.left = x

x.parent = y

def RIGHT_ROTATE(self, y):

# y是一個節(jié)點

x = y.left

if x is None:

# 右節(jié)點為空，不旋轉

return

else:

beta = x.right

y.left = beta

if beta is not None:

beta.parent = y

p = y.parent

x.parent = p

if p is None:

# y原來是root

self.root = x

elif y == p.left:

p.left = x

else:

p.right = x

x.right = y

y.parent = x

def INSERT(self, val):

z = RBTnode(val)

y = None

x = self.root

while x is not None:

y = x

if z.val < x.val:

x = x.left

else:

x = x.right

z.PAINT(RED)

z.parent = y

if y is None:

# 插入z之前為空的RBT

self.root = z

self.INSERT_FIXUP(z)

return

if z.val < y.val:

y.left = z

else:

y.right = z

if y.color == RED:

# z的父節(jié)點y為紅色，需要fixup。

# 如果z的父節(jié)點y為黑色，則不用調整

self.INSERT_FIXUP(z)

else:

return

def INSERT_FIXUP(self, z):

# case 1:z為root節(jié)點

if z.parent is None:

z.PAINT(BLACK)

self.root = z

return

# case 2:z的父節(jié)點為黑色

if z.parent.color == BLACK:

# 包括了z處于第二層的情況

# 這里感覺不必要啊。。似乎z.parent為黑色則不會進入fixup階段

return

# 下面的幾種情況，都是z.parent.color == RED:

# 節(jié)點y為z的uncle

p = z.parent

g = p.parent # g為x的grandpa

if g is None:

return

# return 這里不能return的。。。

if g.right == p:

y = g.left

else:

y = g.right

# case 3-0:z沒有叔叔。即：y為NIL節(jié)點

# 注意，此時z的父節(jié)點一定是RED

if y == None:

if z == p.right and p == p.parent.left:

# 3-0-0:z為右兒子,且p為左兒子，則把p左旋

# 轉化為3-0-1或3-0-2的情況

self.LEFT_ROTATE(p)

p, z = z, p

g = p.parent

elif z == p.left and p == p.parent.right:

self.RIGHT_ROTATE(p)

p, z = z, p

g.PAINT(RED)

p.PAINT(BLACK)

if p == g.left:

# 3-0-1:p為g的左兒子

self.RIGHT_ROTATE(g)

else:

# 3-0-2:p為g的右兒子

self.LEFT_ROTATE(g)

return

# case 3-1:z有黑叔

elif y.color == BLACK:

if p.right == z and p.parent.left == p:

# 3-1-0:z為右兒子,且p為左兒子,則左旋p

# 轉化為3-1-1或3-1-2

self.LEFT_ROTATE(p)

p, z = z, p

elif p.left == z and p.parent.right == p:

self.RIGHT_ROTATE(p)

p, z = z, p

p = z.parent

g = p.parent

p.PAINT(BLACK)

g.PAINT(RED)

if p == g.left:

# 3-1-1:p為g的左兒子，則右旋g

self.RIGHT_ROTATE(g)

else:

# 3-1-2:p為g的右兒子，則左旋g

self.LEFT_ROTATE(g)

return

# case 3-2:z有紅叔

# 則涂黑父和叔，涂紅爺，g作為新的z，遞歸調用

else:

y.PAINT(BLACK)

p.PAINT(BLACK)

g.PAINT(RED)

new_z = g

self.INSERT_FIXUP(new_z)

def DELETE(self, val):

curNode = self.root

while curNode is not None:

if val < curNode.val:

curNode = curNode.left

elif val > curNode.val:

curNode = curNode.right

else:

# 找到了值為val的元素,正式開始刪除

if curNode.left is None and curNode.right is None:

# case1:curNode為葉子節(jié)點：直接刪除即可

if curNode == self.root:

self.root = None

else:

p = curNode.parent

if curNode == p.left:

p.left = None

else:

p.right = None

elif curNode.left is not None and curNode.right is not None:

sucNode = self.SUCCESOR(curNode)

curNode.val, sucNode.val = sucNode.val, curNode.val

self.DELETE(sucNode.val)

else:

p = curNode.parent

if curNode.left is None:

x = curNode.right

else:

x = curNode.left

if curNode == p.left:

p.left = x

else:

p.right = x

x.parent = p

if curNode.color == BLACK:

self.DELETE_FIXUP(x)

curNode = None

return False

def DELETE_FIXUP(self, x):

p = x.parent

# w:x的兄弟結點

if x == p.left:

w = x.right

else:

w = x.left

# case1:x的兄弟w是紅色的

if w.color == RED:

p.PAINT(RED)

w.PAINT(BLACK)

if w == p.right:

self.LEFT_ROTATE(p)

else:

self.RIGHT_ROTATE(p)

if w.color == BLACK:

# case2:x的兄弟w是黑色的，而且w的兩個孩子都是黑色的

if w.left.color == BLACK and w.right.color == BLACK:

w.PAINT(RED)

if p.color == BLACK:

return

else:

p.color = BLACK

self.DELETE_FIXUP(p)

# case3:x的兄弟w是黑色的，而且w的左兒子是紅色的，右兒子是黑色的

if w.left.color == RED and w.color == BLACK:

w.left.PAINT(BLACK)

w.PAINT(RED)

self.RIGHT_ROTATE(w)

# case4:x的兄弟w是黑色的，而且w的右兒子是紅

if w.right.color == RED:

p.PAINT(BLACK)

w.PAINT(RED)

if w == p.right:

self.LEFT_ROTATE(p)

else:

self.RIGHT_ROTATE(p)

def SHOW(self):

self.DISPLAY1(self.root)

return self.zlist

def DISPLAY1(self, node):

if node is None:

return

self.DISPLAY1(node.left)

self.zlist.append(node.val)

self.DISPLAY1(node.right)

def DISPLAY2(self, node):

if node is None:

return

self.DISPLAY2(node.left)

print(node.val)

self.DISPLAY2(node.right)

def DISPLAY3(self, node):

if node is None:

return

self.DISPLAY3(node.left)

self.DISPLAY3(node.right)

print(node.val)

class RBTnode:

'''紅黑樹的節(jié)點類型'''

def __init__(self, val):

self.val = val

self.left = None

self.right = None

self.parent = None

def PAINT(self, color):

self.color = color

def zuoxuan(b, c):

a = b.parent

a.left = c

c.parent = a

b.parent = c

c.left = b

if __name__ == '__main__':

rbt=RBT()

b = []

for i in range(100):

m = randint(0, 500)

rbt.INSERT(m)

b.append(m)

a = rbt.SHOW()

b.sort()

equal = True

for i in range(100):

if a[i] != b[i]:

equal = False

break

if not equal:

print('wrong')

else:

print('OK!')

4、B樹和B+樹(B Tree/B+ Tree)

B樹簡介

B 樹可以看作是對2-3查找樹的一種擴展，即他允許每個節(jié)點有M-1個子節(jié)點。? ? ? ? ①根節(jié)點至少有兩個子節(jié)點；

②每個節(jié)點有M-1個key，并且以升序排列；

③位于M-1和M key的子節(jié)點的值位于M-1 和M key對應的Value之間；

④非葉子結點的關鍵字個數(shù)=指向兒子的指針個數(shù)-1；

⑤非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] ；

⑥其它節(jié)點至少有M/2個子節(jié)點；

⑦所有葉子結點位于同一層；如：(M=3)

B樹算法思想

B-樹的搜索，從根結點開始，對結點內的關鍵字(有序)序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為空，或已經(jīng)是葉子結點；

B樹的特性

1.關鍵字集合分布在整顆樹中；

2.任何一個關鍵字出現(xiàn)且只出現(xiàn)在一個結點中；

3.搜索有可能在非葉子結點結束；

4.其搜索性能等價于在關鍵字全集內做一次二分查找；

5.自動層次控制；

由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少利用率，其最底搜索性能為O(LogN)

B+ 樹簡介

B+樹是B-樹的變體，也是一種多路搜索樹：1.其定義基本與B-樹同，除了：2.非葉子結點的子樹指針與關鍵字個數(shù)相同；3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹4.B-樹是開區(qū)間；5.為所有葉子結點增加一個鏈指針；6.所有關鍵字都在葉子結點出現(xiàn)；

如：(M=3)

B+樹算法思想

B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達到葉子結點才命中(B-樹可以在非葉子結點命中)，其性能也等價于在關鍵字全集做一次二分查找；

B+樹的特性

1.所有關鍵字都出現(xiàn)在葉子結點的鏈表中(稠密索引)，且鏈表中的關鍵字恰好是有序的；

2.不可能在非葉子結點命中；

3.非葉子結點相當于是葉子結點的索引(稀疏索引)，葉子結點相當于是存儲(關鍵字)數(shù)據(jù)的數(shù)據(jù)層；

4.更適合文件索引系統(tǒng)；

算法實現(xiàn)

# -*- coding: UTF-8 -*-

# B樹查找

class BTree: #B樹

def __init__(self,value):

self.left=None

self.data=value

self.right=None

def insertLeft(self,value):

self.left=BTree(value)

return self.left

def insertRight(self,value):

self.right=BTree(value)

return self.right

def show(self):

print(self.data)

def inorder(node): #中序遍歷：先左子樹，再根節(jié)點，再右子樹

if node.data:

if node.left:

inorder(node.left)

node.show()

if node.right:

inorder(node.right)

def rinorder(node): #倒中序遍歷

if node.data:

if node.right:

rinorder(node.right)

node.show()

if node.left:

rinorder(node.left)

def insert(node,value):

if value > node.data:

if node.right:

insert(node.right,value)

else:

node.insertRight(value)

else:

if node.left:

insert(node.left,value)

else:

node.insertLeft(value)

if __name__ == "__main__":

l=[88,11,2,33,22,4,55,33,221,34]

Root=BTree(l[0])

node=Root

for i in range(1,len(l)):

insert(Root,l[i])

print("中序遍歷(從小到大排序 )")

inorder(Root)

print("倒中序遍歷(從大到小排序)")

rinorder(Root)

5、樹表查找總結

二叉查找樹平均查找性能不錯，為O(logn)，但是最壞情況會退化為O(n)。在二叉查找樹的基礎上進行優(yōu)化，我們可以使用平衡查找樹。平衡查找樹中的2-3查找樹，這種數(shù)據(jù)結構在插入之后能夠進行自平衡操作，從而保證了樹的高度在一定的范圍內進而能夠保證最壞情況下的時間復雜度。但是2-3查找樹實現(xiàn)起來比較困難，紅黑樹是2-3樹的一種簡單高效的實現(xiàn)，他巧妙地使用顏色標記來替代2-3樹中比較難處理的3-node節(jié)點問題。紅黑樹是一種比較高效的平衡查找樹，應用非常廣泛，很多編程語言的內部實現(xiàn)都或多或少的采用了紅黑樹。除此之外，2-3查找樹的另一個擴展——B/B+平衡樹，在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中有著廣泛的應用。

分塊查找

算法簡介

要求是順序表，分塊查找又稱索引順序查找，它是順序查找的一種改進方法。

算法思想

將n個數(shù)據(jù)元素"按塊有序"劃分為m塊(m ≤ n)。每一塊中的結點不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一元素的關鍵字都必須小于第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，……

算法流程

1、先選取各塊中的最大關鍵字構成一個索引表；2、查找分兩個部分：先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中；3、在已確定的塊中用順序法進行查找。

復雜度分析

時間復雜度：O(log(m)+N/m)

哈希查找

算法簡介

哈希表就是一種以鍵-值(key-indexed) 存儲數(shù)據(jù)的結構，只要輸入待查找的值即key，即可查找到其對應的值。

算法思想

哈希的思路很簡單，如果所有的鍵都是整數(shù)，那么就可以使用一個簡單的無序數(shù)組來實現(xiàn)：將鍵作為索引，值即為其對應的值，這樣就可以快速訪問任意鍵的值。這是對于簡單的鍵的情況，我們將其擴展到可以處理更加復雜的類型的鍵。

算法流程

1)用給定的哈希函數(shù)構造哈希表；

2)根據(jù)選擇的沖突處理方法解決地址沖突；

常見的解決沖突的方法：拉鏈法和線性探測法。

3)在哈希表的基礎上執(zhí)行哈希查找。

復雜度分析

單純論查找復雜度：對于無沖突的Hash表而言，查找復雜度為O(1)(注意，在查找之前我們需要構建相應的Hash表)。

算法實現(xiàn)

# 忽略了對數(shù)據(jù)類型，元素溢出等問題的判斷。

class HashTable:

def __init__(self, size):

self.elem = [None for i in range(size)] # 使用list數(shù)據(jù)結構作為哈希表元素保存方法

self.count = size # 最大表長

def hash(self, key):

return key % self.count # 散列函數(shù)采用除留余數(shù)法

def insert_hash(self, key):

"""插入關鍵字到哈希表內"""

address = self.hash(key) # 求散列地址

while self.elem[address]: # 當前位置已經(jīng)有數(shù)據(jù)了，發(fā)生沖突。

address = (address+1) % self.count # 線性探測下一地址是否可用

self.elem[address] = key # 沒有沖突則直接保存。

def search_hash(self, key):

"""查找關鍵字，返回布爾值"""

star = address = self.hash(key)

while self.elem[address] != key:

address = (address + 1) % self.count

if not self.elem[address] or address == star: # 說明沒找到或者循環(huán)到了開始的位置

return False

return True

if __name__ == '__main__':

list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]

hash_table = HashTable(12)

for i in list_a:

hash_table.insert_hash(i)

for i in hash_table.elem:

if i:

print((i, hash_table.elem.index(i)), end=" ")

print("\n")

print(hash_table.search_hash(15))

print(hash_table.search_hash(33))

總結

以上是生活随笔為你收集整理的python 查找算法_七大查找算法（Python）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。