# 针对有序查找表的二分查找算法 # 时间复杂度O(log(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: # 打印折半的次数 print("times: %s" % time) return mid print("times: %s" % time) return Falseif __name__ == '__main__': LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444] result = binary_search(LIST, 99) print(result)

# 插值查找算法 # 时间复杂度O(log(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: # 打印查找的次数 print("times: %s" % time) return mid print("times: %s" % time) return Falseif __name__ == '__main__': LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444] result = binary_search(LIST, 54) print(result)

# 斐波那契查找算法 # 时间复杂度O(log(n))def fibonacci_search(lis, key): # 需要一个现成的斐波那契列表。其最大元素的值必须超过查找表中元素个数的数值。 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# 为了使得查找表满足斐波那契特性，在表的最后添加几个同样的值 # 这个值是原查找表的最后那个元素的值 # 添加的个数由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用于展示循环的次数。 time = 0 while low <= high: time += 1 # 为了防止F列表下标溢出，设置if和else if k < 2: mid = low else: mid = low + F[k - 1] - 1print("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: # 打印查找的次数 print("times: %s" % time) return mid else: print("times: %s" % time) return high print("times: %s" % time) return Falseif __name__ == '__main__': LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444] result = fibonacci_search(LIST, 444) print(result)

class BSTNode: """ 定义一个二叉树节点类。 以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。 """ def __init__(self, data, left=None, right=None): """ 初始化 :param data: 节点储存的数据 :param left: 节点左子树 :param right: 节点右子树 """ self.data = https://www.it610.com/article/data self.left = left self.right = rightclass BinarySortTree:""" 基于BSTNode类的二叉排序树。维护一个根节点的指针。 """ def __init__(self): self._root = Nonedef is_empty(self): return self._root is Nonedef search(self, key): """ 关键码检索 :param key: 关键码 :return: 查询节点或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 Nonedef 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 = https://www.it610.com/article/key returndef delete(self, key):""" 二叉排序树最复杂的方法 :param key: 关键码 :return: 布尔值 """ p, q = None, self._root# 维持p为q的父节点，用于后面的链接操作 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 # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。 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 # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树 # 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。 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.leftdef __iter__(self): """ 实现二叉树的中序遍历算法, 展示我们创建的二叉排序树. 直接使用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.rightif __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(100) for i in bs_tree: print(i, end=" ") print("\n", bs_tree.search(4))

• 二叉排序树以链式进行存储，保持了链接结构在插入和删除操作上的优点。
• 在极端情况下，查询次数为1，但最大操作次数不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状，也就引申出了后面的平衡二叉树。
• 给定一个元素集合，可以构造不同的二叉排序树，当它同时是一个完全二叉树的时候，查找的时间复杂度为O(log(n))，近似于二分查找。
• 当出现最极端的斜树时，其时间复杂度为O(n)，等同于顺序查找，效果最差，如右图。

@staticmethod def LL(a, b): a.left = b.right # 将b的右子树接到a的左子结点上 b.right = a #将a树接到b的右子结点上 a.bf = b.bf = 0 #调整a、b的bf值。 return b

@staticmethod def RR(a, b): a.right = b.left b.left = a a.bf = b.bf = 0 return b

@staticmethod def LR(a,b): c = b.right a.left, b.right = c.right, c.left c.left, c.right = b, a if c.bf == 0: #c本身就是插入点 a.bf = b.bf = 0 elif c.bf == 1: #插在c的左子树 a.bf = -1 b.bf = 0 else:#插在c的右子树 a.bf = 0 b.bf = 1 c.bf = 0 return c

@staticmethod def RL(a, b): c = b.left a.right, b.left = c.left, c.right c.left, c.right = a, b if c.bf == 0: a.bf = b.bf = 0 elif c.bf == 1: a.bf = 0 b.bf = -1 else: a.bf = 1 b.bf = 0 c.bf = 0 return c

class StackUnderflow(ValueError): passclass SStack(): def __init__(self): self.elems = []def is_empty(self): return self.elems == []def top(self):# 取得栈里最后压入的元素，但不删除 if self.elems == []: raise StackUnderflow('in SStack.top()') return self.elems[-1]def push(self, elem): self.elems.append(elem)def pop(self): if self.elems == []: raise StackUnderflow('in SStack.pop()') return self.elems.pop()class Assoc:# 定义一个关联类 def __init__(self, key, value): self.key = key# 键（关键码） self.value = https://www.it610.com/article/value# 值def __lt__(self, other):# Python解释器中遇到比较运算符<,会去找类里定义的__lt__方法（less than） return self.key < other.keydef __le__(self, other):# （less than or equal to) return self.key < other.key or self.key == other.keydef __str__(self): return'Assoc({0},{1})'.format(self.key, self.value)# key和value分别替换前面{0},{1}的位置。class BinTNode: def __init__(self, dat, left=None, right=None): self.data = https://www.it610.com/article/dat self.left = left self.right = rightclass DictBinTree: def __init__(self, root=None): self.root = rootdef is_empty(self): return self.root is Nonedef search(self, key):# 检索是否存在关键码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 Nonedef insert(self, key, value): bt = self.root if bt is None: self.root = BinTNode(Assoc(key, value)) 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 = https://www.it610.com/article/value returndef print_all_values(self): bt, s = self.root, SStack() while bt is not None or not s.is_empty():# 最开始时栈为空，但bt不为空；bt = bt.right可能为空，栈不为空；当两者都为空时，说明已经全部遍历完成了 while bt is not None: s.push(bt) bt = bt.left bt = s.pop()# 将栈顶元素弹出 yield bt.data.key, bt.data.value bt = bt.right# 将当前结点的右子结点赋给bt，让其在while中继续压入栈内def entries(self): bt, s = self.root, SStack() while bt is not None or not s.is_empty(): while bt is not None: s.push(bt) bt = bt.left bt = s.pop() yield bt.data.key, bt.data.value bt = bt.rightdef print_key_value(self): for k, v in self.entries(): print(k, v)def delete(self, key): # 以下这一段用于找到待删除结点及其父结点的位置。 del_position_father, del_position = None, self.root# del_position_father是待删除结点del_position的父结点 while del_position is not None and del_position.data.key != key:# 通过不断的比较，找到待删除结点的位置 del_position_father = del_position if key < del_position.data.key: del_position = del_position.left else: del_position = del_position.right if del_position is None: print('There is no key') returnif del_position.left is None:# 如果待删除结点只有右子树 if del_position_father is None:# 如果待删除结点的父结点是空，则说明待删除结点是根结点 self.root = del_position.right# 则直接将根结点置空 elif del_position is del_position_father.left:# 如果待删除结点是其父结点的左结点 del_position_father.left = del_position.right# ***改变待删除结点父结点的左子树的指向 else: del_position_father.right = del_position.right return# 如果既有左子树又有右子树，或者仅有左子树时，都可以用直接前驱替换的删除结点的方式，只不过得到的二叉树与原理中说明的不一样，但是都满足要求。 pre_node_father, pre_node = del_position, del_position.left while pre_node.right is not None:# 找到待删除结点的左子树的最右结点，即为待删除结点的直接前驱 pre_node_father = pre_node pre_node = pre_node.right del_position.data = https://www.it610.com/article/pre_node.data# 将前驱结点的data赋给删除结点即可，不需要改变其原来的连接方式if pre_node_father.left is pre_node: pre_node_father.left = pre_node.left if pre_node_father.right is pre_node: pre_node_father.right = pre_node.leftdef build_dictBinTree(entries): dic = DictBinTree() for k, v in entries: dic.insert(k, v) return dicclass AVLNode(BinTNode): def __init__(self, data): BinTNode.___init__(self, data) self.bf = 0class DictAVL(DictBinTree): def __init__(self, data): DictBinTree.___init__(self)@staticmethod def LL(a, b): a.left = b.right# 将b的右子树接到a的左子结点上 b.right = a# 将a树接到b的右子结点上 a.bf = b.bf = 0# 调整a、b的bf值。 return b@staticmethod def RR(a, b): a.right = b.left b.left = a a.bf = b.bf = 0 return b@staticmethod def LR(a, b): c = b.right a.left, b.right = c.right, c.left c.left, c.right = b, a if c.bf == 0:# c本身就是插入点 a.bf = b.bf = 0 elif c.bf == 1:# 插在c的左子树 a.bf = -1 b.bf = 0 else:# 插在c的右子树 a.bf = 0 b.bf = 1 c.bf = 0 return c@staticmethod def RL(a, b): c = b.left a.right, b.left = c.left, c.right c.left, c.right = a, b if c.bf == 0: a.bf = b.bf = 0 elif c.bf == 1: a.bf = 0 b.bf = -1 else: a.bf = 1 b.bf = 0 c.bf = 0 return cdef insert(self, key, value): a = p = self.root if a is None:# 如果根结点为空，则直接将值插入到根结点 self.root = AVLNode(Assoc(key, value)) return a_father, p_father = None# a_father用于最后将调整后的子树接到其子结点上 while p is not None:# 通过不断的循环，将p下移，查找插入位置，和最小非平衡子树 if key == p.data.key:# 如果key已经存在，则直接修改其关联值 p.data.value = value return if p.bf != 0:# 如果当前p结点的BF=0，则有可能是最小非平衡子树的根结点 a_father, a, = p_father, p p_father = p if key < p.data.key: p = p.left else: p = p.right# 上述循环结束后，p_father已经是插入点的父结点，a_father和a记录着最小非平衡子树 node = AVLNode(Assoc(key, value)) if key < p_father.data.key: p_father.left = node else: p_father.right = node# 新结点已插入，a是最小非平衡子树的根结点 if key < a.data.key:# 新结点在a的左子树 p = b = a.left d = 1# d记录新结点被 插入到a的哪棵子树 else: p = b = a.right# 新结点在a的右子树 d = -1# 在新结点插入后，修改b到新结点路径上各结点的BF值。调整过程的BF值修改都在子函数中操作 while p != node: if key < p.data.key: p.bf = 1 p = p.left else: p.bf = -1 p = p.right if a.bf == 0:# 如果a的BF原来为0，那么插入新结点后不会失衡 a.bf = d return if a.bf == -d:# 如果新结点插入在a较低的子树里 a.bf = 0 return# 以上两条if语句都不符合的话，说明新结点被插入在较高的子树里，需要进行调整 if d == 1:# 如果新结点插入在a的左子树 if b.bf == 1:# b的BF原来为0，如果等于1，说明新结点插入在b的左子树 b = DictAVL.LL(a, b) else:# 新结点插入在b的右子树 b = DictAVL.LR(a, b) else:# 新结点插入在a的右子树 if b.bf == -1:# 新结点插入在b的右子树 b = DictAVL.RR(a, b) else:##新结点插入在b的左子树 b = DictAVL.RL(a, b)# 将调整后的最小非平衡子树接到原树中,也就是接到原来a结点的父结点上 if a_father is None:# 判断a是否是根结点 self.root = b else: if a_father == a: a_father.left = b else: a_father.right = bif __name__ =="__main__": # LL调整 entries = [(5, 'a'), (2.5, 'g'), (2.3, 'h'), (3, 'b'), (2, 'd'), (4, 'e'), (3.5, 'f')] dic = build_dictBinTree(entries) dic.print_key_value() print('after inserting') dic.insert(1, 'i') dic.print_key_value()# LR调整 entries = [(2.5, 'g'), (3, 'b'), (4, 'e'), (3.5, 'f')] dic = build_dictBinTree(entries) dic.print_key_value() print('after inserting') dic.insert(3.2, 'i')# LL dic.print_key_value()

1. 直接定址法
   例如取关键字的某个线性函数为散列函数：
   f(key) = a*key + b (a,b为常数）
2. 数字分析法
   抽取关键字里的数字，根据数字的特点进行地址分配。是提取关键字中取值较均匀的数字位作为哈希地址的方法。
3. 平方取中法
   将关键字的数字求平方，取分布均匀的即为作为哈希地址的方法。
4. 折叠法
   将关键字的数字分割后分别计算，再合并计算，一种玩弄数字的手段。先把关键字中的若干段作为一小组，然后把各小组折叠相加后分布均匀的即为作为哈希地址的方法。
5. 除留余数法
   最为常见的方法之一。
   对于表长为m的数据集合，散列公式为：
   f(key) = key mod p (p<=m)
   mod：取模（求余数）
   该方法最关键的是p的选择，而且数据量较大的时候，冲突是必然的。一般会选择接近m的质数。
6. 随机数法
   选择一个随机数，取关键字的随机函数值为它的散列地址。
   f(key) = random(key)

• 计算散列地址所需的时间
• 关键字的长度
• 散列表的大小
• 关键字的分布情况
• 记录查找的频率

# 忽略了对数据类型，元素溢出等问题的判断。class HashTable: def __init__(self, size): self.elem = [None for i in range(size)]# 使用list数据结构作为哈希表元素保存方法 self.count = size# 最大表长def hash(self, key): return key % self.count# 散列函数采用除留余数法def insert_hash(self, key): """插入关键字到哈希表内""" address = self.hash(key)# 求散列地址 while self.elem[address]:# 当前位置已经有数据了，发生冲突。 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:# 说明没找到或者循环到了开始的位置 return False return Trueif __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))

• 散列函数是否均匀
• 处理冲突的办法
• 散列表的装填因子（表内数据装满的程度）

推荐阅读

• 

  你们认为诗仙李白最好的一首诗是哪一首？
• 

  一天喝多少牛奶合适？
• 

  青芒的热量高吗
• 

  花胶有什么营养价值
• 

  土大黄的功效与作用 土大黄的副作用
• 

  美国冲突升级!武装民兵冲进议会大厦,议员吓的穿防弹衣上班,州长命令被废,大乱了吗？
• 

  最新热门的12个最佳博客平台合集（以及如何选择一个）
• 

  买笔记本电脑,处理器是选择i5还是i7？
• 

  妒组词语 妒有哪些组词呢
• 

  熊童子简笔画
• 

  Photoshop制作沧桑颓废的城市海报
• 

  手机停机怎么连接网络，手机停机怎么连接网络电视
• 

  176升冰箱购买指南及故障维修解决方案
• 

  早晨八点半
• 

  升级换代，让您的打印更高效 epsonL3153变成2710
• 

  海带有味道了还能吃吗
• 

  照门是什么意思 照门的含义
• 

  获嘉天气30天 获嘉天气预报
• 

  核酸检测假阳性怎么处理
• 

  分享一首小诗（相信）

• 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
• C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
• 数据结构和算法|LeetCode 的正确使用方式
• 先序遍历 中序遍历 后序遍历 层序遍历
• 数据结构|C++技巧（用class类实现链表）
• 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
• 算法|算法-二分查找
• 数据结构学习指导|数据结构初阶（线性表）
• leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
• java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔