Python實現(xiàn)七大查找算法的示例代碼
查找算法 -- 簡介
查找（Searching）就是根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。
查找表（Search Table）：由同一類型的數(shù)據(jù)元素構(gòu)成的集合
關(guān)鍵字（Key）：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，又稱為鍵值
主鍵（Primary Key）：可唯一的標識某個數(shù)據(jù)元素或記錄的關(guān)鍵字
查找表按照操作方式可分為：
1.靜態(tài)查找表（Static Search Table）：只做查找操作的查找表。它的主要操作是：
①查詢某個“特定的”數(shù)據(jù)元素是否在表中
②檢索某個“特定的”數(shù)據(jù)元素和各種屬性
2.動態(tài)查找表（Dynamic Search Table）：在查找中同時進行插入或刪除等操作：
①查找時插入數(shù)據(jù)
②查找時刪除數(shù)據(jù)
順序查找
算法簡介
順序查找又稱為線性查找，是一種最簡單的查找方法。適用于線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。該算法的時間復雜度為O(n)。
基本思路
從第一個元素m開始逐個與需要查找的元素x進行比較，當比較到元素值相同(即m=x)時返回元素m的下標，如果比較到最后都沒有找到，則返回-1。
優(yōu)缺點
缺點：是當n 很大時，平均查找長度較大，效率低；
優(yōu)點：是對表中數(shù)據(jù)元素的存儲沒有要求。另外，對于線性鏈表，只能進行順序查找。
算法實現(xiàn)
# 最基礎(chǔ)的遍歷無序列表的查找算法
# 時間復雜度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ù)組的中間元素開始，如果中間元素正好是要查找的元素，則查找過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。
這種查找算法每一次比較都使查找范圍縮小一半。
算法描述
給予一個包含 n個帶值元素的數(shù)組A
1、 令 L為0 ， R為 n-1 ；
2、 如果L>R，則搜索以失敗告終 ；
3、 令 m (中間值元素)為 ⌊(L+R)/2⌋；
4、 如果 Am<T，令 L為 m + 1 并回到步驟二 ；
5、 如果 Am>T，令 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ù)要查找的關(guān)鍵字key與查找表中最大最小記錄的關(guān)鍵字比較后的 查找方法，其核心就在于插值的計算公式 (key-a[low])/(a[high]-a[low])*(high-low)。
時間復雜度o(logn)但對于表長較大而關(guān)鍵字分布比較均勻的查找表來說，效率較高。
算法思想
基于二分查找算法，將查找點的選擇改進為自適應選擇，可以提高查找效率。當然，差值查找也屬于有序查找。
注：對于表長較大，而關(guān)鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數(shù)組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。
復雜度分析
時間復雜性：如果元素均勻分布，則O（log log n）），在最壞的情況下可能需要 O（n）。
空間復雜度：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(xiàn)(2)=1，F(xiàn)(n)=f(n-1)+F(n-2) （n>=2）。該數(shù)列越往后相鄰的兩個數(shù)的比值越趨向于黃金比例值（0.618）。
算法描述
斐波那契查找就是在二分查找的基礎(chǔ)上根據(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列表下標溢出，設(shè)置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）或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
1）若任意節(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
2）若任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
3）任意節(jié)點的左、右子樹也分別為二叉查找樹。
二叉查找樹性質(zhì)：對二叉查找樹進行中序遍歷，即可得到有序的數(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):
"""
關(guān)鍵碼檢索
:param key: 關(guān)鍵碼
: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:關(guān)鍵碼
: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: 關(guān)鍵碼
: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: # 當樹中沒有關(guān)鍵碼key時，結(jié)束退出。
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(shè)計其它的方法。
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內(nèi)置的列表作為一個棧。
: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還要?。恢虚g節(jié)點也是一個2-3節(jié)點，中間節(jié)點的key值在兩個跟節(jié)點key值之間；右節(jié)點也是一個2-3節(jié)點，節(jié)點的所有key值比兩個key中的最大的key還要大。
2-3查找樹的性質(zhì)
1）如果中序遍歷2-3查找樹，就可以得到排好序的序列；
2）在一個完全平衡的2-3查找樹中，根節(jié)點到每一個為空節(jié)點的距離都相同。（這也是平衡樹中“平衡”一詞的概念，根節(jié)點到葉節(jié)點的最長距離對應于查找算法的最壞情況，而平衡樹中根節(jié)點到葉節(jié)點的距離都一樣，最壞情況也具有對數(shù)復雜度。）
2-3樹的查找效率與樹的高度是息息相關(guān)的。
距離來說，對于1百萬個節(jié)點的2-3樹，樹的高度為12-20之間，對于10億個節(jié)點的2-3樹，樹的高度為18-30之間。
對于插入來說，只需要常數(shù)次操作即可完成，因為他只需要修改與該節(jié)點關(guān)聯(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<self.key1:
return self.left
elif self.key2 is None:
return self.middle
elif key<self.key2:
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.key1:
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<node.key1:
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<node.key2:
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é)點到所以葉子結(jié)點的路徑上，黑色鏈接的個數(shù)都相同。
紅黑樹的性質(zhì)
整個樹完全黑色平衡，即從根節(jié)點到所以葉子結(jié)點的路徑上，黑色鏈接的個數(shù)都相同（2-3樹的第2）性質(zhì)，從根節(jié)點到葉子節(jié)點的距離都相等）。
復雜度分析
最壞的情況就是，紅黑樹中除了最左側(cè)路徑全部是由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é)點為空，不旋轉(zhuǎn)
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é)點為空，不旋轉(zhuǎn)
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為黑色，則不用調(diào)整
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左旋
# 轉(zhuǎn)化為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
# 轉(zhuǎn)化為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，遞歸調(diào)用
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的兄弟結(jié)點
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之間；
④非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1；
⑤非葉子結(jié)點的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] ；
⑥其它節(jié)點至少有M/2個子節(jié)點；
⑦所有葉子結(jié)點位于同一層；
如：（M=3）
B樹算法思想
B-樹的搜索，從根結(jié)點開始，對結(jié)點內(nèi)的關(guān)鍵字（有序）序列進行二分查找，如果命中則結(jié)束，否則進入查詢關(guān)鍵字所屬范圍的兒子結(jié)點；重復，直到所對應的兒子指針為空，或已經(jīng)是葉子結(jié)點；
B樹的特性
1.關(guān)鍵字集合分布在整顆樹中；
2.任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點中；
3.搜索有可能在非葉子結(jié)點結(jié)束；
4.其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找；
5.自動層次控制；
由于限制了除根結(jié)點以外的非葉子結(jié)點，至少含有M/2個兒子，確保了結(jié)點的至少利用率，其最底搜索性能為O(LogN)
B+ 樹簡介
B+樹是B-樹的變體，也是一種多路搜索樹：
1.其定義基本與B-樹同，除了：
2.非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同；
3.非葉子結(jié)點的子樹指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹
4.B-樹是開區(qū)間；
5.為所有葉子結(jié)點增加一個鏈指針；
6.所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)；
如：（M=3）
B+樹算法思想
B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達到葉子結(jié)點才命中（B-樹可以在非葉子結(jié)點命中），其性能也等價于在關(guān)鍵字全集做一次二分查找；
B+樹的特性
1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；
2.不可能在非葉子結(jié)點命中；
3.非葉子結(jié)點相當于是葉子結(jié)點的索引（稀疏索引），葉子結(jié)點相當于是存儲（關(guān)鍵字）數(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、樹表查找總結(jié)
二叉查找樹平均查找性能不錯，為O(logn)，但是最壞情況會退化為O(n)。在二叉查找樹的基礎(chǔ)上進行優(yōu)化，我們可以使用平衡查找樹。平衡查找樹中的2-3查找樹，這種數(shù)據(jù)結(jié)構(gòu)在插入之后能夠進行自平衡操作，從而保證了樹的高度在一定的范圍內(nèi)進而能夠保證最壞情況下的時間復雜度。但是2-3查找樹實現(xiàn)起來比較困難，紅黑樹是2-3樹的一種簡單高效的實現(xiàn)，他巧妙地使用顏色標記來替代2-3樹中比較難處理的3-node節(jié)點問題。紅黑樹是一種比較高效的平衡查找樹，應用非常廣泛，很多編程語言的內(nèi)部實現(xiàn)都或多或少的采用了紅黑樹。
除此之外，2-3查找樹的另一個擴展——B/B+平衡樹，在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中有著廣泛的應用。
分塊查找
算法簡介
要求是順序表，分塊查找又稱索引順序查找，它是順序查找的一種改進方法。
算法思想
將n個數(shù)據(jù)元素"按塊有序"劃分為m塊（m ≤ n）。
每一塊中的結(jié)點不必有序，但塊與塊之間必須"按塊有序"；
即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；
而第2塊中任一元素又都必須小于第3塊中的任一元素，……
算法流程
1、先選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表；
2、查找分兩個部分：先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中；
3、在已確定的塊中用順序法進行查找。
復雜度分析
時間復雜度：O(log(m)+N/m)
哈希查找
算法簡介
哈希表就是一種以鍵-值(key-indexed) 存儲數(shù)據(jù)的結(jié)構(gòu)，只要輸入待查找的值即key，即可查找到其對應的值。
算法思想
哈希的思路很簡單，如果所有的鍵都是整數(shù)，那么就可以使用一個簡單的無序數(shù)組來實現(xiàn)：將鍵作為索引，值即為其對應的值，這樣就可以快速訪問任意鍵的值。這是對于簡單的鍵的情況，我們將其擴展到可以處理更加復雜的類型的鍵。
算法流程
1）用給定的哈希函數(shù)構(gòu)造哈希表；
2）根據(jù)選擇的沖突處理方法解決地址沖突；
常見的解決沖突的方法：拉鏈法和線性探測法。
3）在哈希表的基礎(chǔ)上執(zhí)行哈希查找。
復雜度分析
單純論查找復雜度：對于無沖突的Hash表而言，查找復雜度為O(1)（注意，在查找之前我們需要構(gòu)建相應的Hash表）。
算法實現(xiàn)
# 忽略了對數(shù)據(jù)類型，元素溢出等問題的判斷。
class HashTable:
def __init__(self, size):
self.elem = [None for i in range(size)] # 使用list數(shù)據(jù)結(jié)構(gòu)作為哈希表元素保存方法
self.count = size # 最大表長
def hash(self, key):
return key % self.count # 散列函數(shù)采用除留余數(shù)法
def insert_hash(self, key):
"""插入關(guān)鍵字到哈希表內(nèi)"""
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):
"""查找關(guān)鍵字，返回布爾值"""
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))
到此這篇關(guān)于Python實現(xiàn)七大查找算法的示例代碼的文章就介紹到這了,更多相關(guān)Python 查找算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Python猜數(shù)字算法題詳解
- python算法題 鏈表反轉(zhuǎn)詳解
- 一道python走迷宮算法題
- python實現(xiàn)dbscan算法
- Python機器學習之PCA降維算法詳解
- Python機器學習算法之決策樹算法的實現(xiàn)與優(yōu)缺點
- python排序算法的簡單實現(xiàn)方法
- Python實現(xiàn)K-means聚類算法并可視化生成動圖步驟詳解
- 用Python給圖像算法做個簡單應用界面
- python利用K-Means算法實現(xiàn)對數(shù)據(jù)的聚類案例詳解
- python入門之算法學習
- python實現(xiàn)線性回歸算法
- python 算法題——快樂數(shù)的多種解法
相關(guān)文章
這篇文章主要介紹了python類屬性學習深入講解，文中對于python的類屬性的理解有正在學習python的同學可以一塊學習下2021-03-03
今天小編就為大家分享一篇python用列表生成式寫嵌套循環(huán)的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-11-11
Python實現(xiàn)批量讀取圖片并存入mongodb數(shù)據(jù)庫的方法示例
這篇文章主要介紹了Python實現(xiàn)批量讀取圖片并存入mongodb數(shù)據(jù)庫的方法,涉及Python文件讀取及數(shù)據(jù)庫寫入相關(guān)操作技巧,需要的朋友可以參考下2018-04-04
Python和Excel的完美結(jié)合的常用操作案例匯總
這篇文章主要介紹了Python和Excel的完美結(jié)合的常用操作案例匯總，文章通過圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-09-09
今天小編就為大家分享一篇在python中畫正態(tài)分布圖像的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07
python,pycharm的環(huán)境變量設(shè)置方式
這篇文章主要介紹了python,pycharm的環(huán)境變量設(shè)置方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
Python Django給admin添加Action的方法實例詳解
這篇文章主要介紹了Django給admin添加Action的方法，本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2019-04-04
這篇文章主要為大家詳細介紹了Python實現(xiàn)雙人模式的貪吃蛇小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
詳解Python是如何實現(xiàn)issubclass的
這篇文章主要介紹了詳解Python是如何實現(xiàn)issubclass的，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-07-07
這篇文章主要介紹了python 實現(xiàn)多線程下載視頻的代碼,代碼簡單易懂，非常不錯，具有一定的參考借鑒價值，需要的朋友可以參考下2019-11-11