三.二 插值查找,可唯一地标记有个别数据成分或记录的严重性字

接待大家庭访问问作者的民用网站《刘江先生的博客和学科》:www.liujiangblog.com

详解常用查找数据结构及算法(Python落成),数据结构python

一、基本概念

搜索(Searching)便是基于给定的有个别值,在查找表中规定3个其关键字等于给定值的数码成分(或记录)。

查找表(Search Table):由同样品种的数据成分(或记录)构成的会见

首要字(Key):数据成分中某些数据项的值,又称之为键值。

主键(Primary Key):可唯壹地方统一规范识某些数据成分或记录的要害字。

查找表遵照操作方法可分为:

  • 静态查找表(Static Search
    Table):只做查找操作的查找表。它的关键操作是:
  • 询问有些“特定的”数据成分是或不是在表中
  • 追寻某些“特定的”数据成分和各样品质
  • 动态查找表(Dynamic Search
    Table):在检索中还要开始展览扦插或删除等操作:
  • 探求时插入数据
  • 寻找时去除数据

2、无序表查找

相当于数额不排序的线性查找,遍历数据成分。

算法分析:最棒状态是在第10个职责就找到了,此为O(一);最坏意况在结尾二个职位才找到,此为O(n);所以平均查找次数为(n+1)/2。最终时间复杂度为O(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)

三、有序表查找

查找表中的数据必须按有个别主键实行某种排序!

1. 二分查找(Binary Search)

算法焦点:在查找表中持续取中间成分与查找值实行相比较,以二分之一的倍率举行表范围的紧缩。

# 针对有序查找表的二分查找算法
# 时间复杂度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 False

if __name__ == '__main__':
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 99)
  print(result)

2. 插值查找

二分查找法就算早已很科学了,但还有可以优化的地点。

局地时候,对半过滤还不够狠,若是每一次都消除百分之九十的多少岂不是越来越好?选用这几个值正是关键难点,插值的意思正是:以越来越快的进程实行压缩。

插值的主干就是运用公式:

value = (key – list[low])/(list[high] – list[low])

用这么些value来替代二分查找中的一半。

上面的代码可以直接行使,只必要改一句。

# 插值查找算法
# 时间复杂度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 False

if __name__ == '__main__':
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 444)
  print(result)

插值算法的一体化时间复杂度依然属于O(log(n))品级的。其亮点是,对于表内数据量相当大,且首要字遍及相比较均匀的查找表,使用插值算法的平分质量比二分查找要好得多。反之,对于布满极端不均匀的数额,则不适合利用插值算法。

叁. 斐波那契查找

由插值算法带来的启迪,发明了斐波那契算法。其主旨也是如何优化那些缩减速率,使得寻找次数尽量降低。

接纳那种算法,前提是曾经有1个含有斐波那契数据的列表

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

# 斐波那契查找算法
# 时间复杂度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]-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:
        # 打印查找的次数
        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)

算法分析:斐波那契查找的一体化时间复杂度也为O(log(n))。但就平均质量,要优化二分查找。不过在最坏处境下,举例此处倘使key为一,则平素处在左边半区查找,此时其效能要自愧比不上二分查找。

小结:二分查找的mid运算是加法与除法,插值查找则是错综复杂的四则运算,而斐波那契查找只是最简便的加减运算。在海量数据的寻找中,这种细微的差别恐怕会潜移默化最终的搜寻功能。由此,二种有序表的追寻方法本质上是分割点的取舍不相同,各有优劣,应依据真实意况举办抉择。

肆、线性索引查找

对杨世元量的冬辰数据,为了加强查找速度,一般会为其组织索引表。

目录正是把3个重中之重字与它相对应的笔录实行关联的长河。

3个索引由若干个索引项组成,每一种索引项至少含有关键字和其对应的笔录在存款和储蓄器中的地方等音信。

目录遵照协会能够分成:线性索引、树形索引和千家万户索引。

线性索引:将索引项的成团通过线性结构来公司,也叫索引表。

线性索引可分为:稠密索引、分块索引和倒排索引

一.稠密索引

稠密索引指的是在线性索引中,为数据集合中的各类记录都创立3个索引项。

图片 1

那实际就相当于给冬日的集结,建立了一张不改变的线性表。其索引项一定是比照关键码进行有序的排列。

那也一定于把查找进程中须要的排序专门的学问给提前做了。

壹.分块索引

给大气的冬季数据集结实行分块管理,使得块内无序,块与块之间有序。

那实质上是一动不动查找和冬季查找的1种中间状态可能说迁就状态。因为数据量过大,建立完整的稠密索引耗费时间耗力,占用财富过多;但一旦不做另向外排水序恐怕索引,那么遍历的检索也无从经受,只好折中,做一定水平的排序或索引。

图片 2

分块索引的频率比遍历查找的O(n)要高级中学一年级些,但与二分查找的O(logn)如故要差不少。

壹.倒排索引

不是由记录来明确属性值,而是由属性值来规定记录的职位,那种被号称倒排索引。在那之中记录号表存款和储蓄具有同等次重大字的具有记录的地方或引用(能够是指向记录的指针或该记录的主关键字)。

倒排索引是最基础的探求引擎索引技艺。

伍、二叉排序树

二叉排序树又称之为贰叉查找树。它依旧是一颗空树,或许是富有下列性质的2叉树:

  • 若它的左子树不为空,则左子树上全部节点的值均低于它的根结构的值;
  • 若它的右子树不为空,则右子树上全数节点的值均当先它的根结构的值;
  • 它的左、右子树也独家为二叉排序树。

图片 3

结构一颗2叉排序树的目标,往往不是为了排序,而是为了拉长查找和插入删除关键字的进度。

二叉排序树的操作:

一.追寻:比较节点的值和要紧字,相等则评释找到了;小了则往节点的左子树去找,大了则往右子树去找,这么递归下去,最终回到布尔值或找到的节点。

二.插入:从根节点最先逐一与根本字张开对照,小了去右边,大了去动手,蒙受子树为空的情事就将新的节点链接。

3.剔除:假使要删减的节点是卡牌,直接删;假诺唯有左子树或只有右子树,则删除节点后,将子树链接到父节点就可以;假诺还要有左右子树,则足以将二叉排序树举办中序遍历,取就要被删除的节点的前任也许后继节点代替那几个被剔除的节点的岗位。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5


class BSTNode:
  """
  定义一个二叉树节点类。
  以讨论算法为主,忽略了一些诸如对数据类型进行判断的问题。
  """
  def __init__(self, data, left=None, right=None):
    """
    初始化
    :param data: 节点储存的数据
    :param left: 节点左子树
    :param right: 节点右子树
    """
    self.data = data
    self.left = left
    self.right = right


class BinarySortTree:
  """
  基于BSTNode类的二叉排序树。维护一个根节点的指针。
  """
  def __init__(self):
    self._root = None

  def is_empty(self):
    return self._root is None

  def 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 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的父节点,用于后面的链接操作
    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.left

  def __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.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个完全贰叉树的时候,查找的年月复杂度为O(log(n)),近似于二分查找。
  • 当现身最极端的斜树时,其时间复杂度为O(n),等同于顺序查找,效果最差。

图片 4

6、 平衡2叉树

平衡二叉树(AVL树,发明者的姓名缩写):1种中度平衡的排序2叉树,其每贰个节点的左子树和右子树的中度差最多等于1。

平衡贰叉树首先必须是一棵贰叉排序树!

平衡因子(Balance
Factor):将2叉树上节点的左子树深度减去右子树深度的值。

对此平衡贰叉树全体包罗分支节点和叶节点的平衡因子只恐怕是-1,0和1,只要有2个节点的因子不在那四个值之内,该二叉树就是不平衡的。

图片 5

小小的不平衡子树:距离插入结点近期的,且平衡因子的断然值超越1的节点为根的子树。

平衡二叉树的构建思想:每当插入二个新结点时,先反省是或不是破坏了树的平衡性,若有,寻找最小不平衡子树。在保持二叉排序树本性的前提下,调治最小不平衡子树中各结点之间的连日关系,进行相应的转动,成为新的平衡子树。

下边是由[1,2,3,4,5,6,7,10,9]营造平衡2叉树

图片 6
图片 7
图片 8
图片 9
图片 10
图片 11
图片 12

7、多路查找树(B树)

多路查找树(muitl-way search
tree):其每1个节点的子女可以多于多个,且每贰个结点处能够储存多个因素。
 对于多路找出树,每一个节点能够积攒多少个元素,以及它的男女数的多少是最首要,常用的有那4种样式:二-三树、二-三-肆树、B树和B+树。

2-3树

二-三树:各类结点都怀有二个子女,大概1个子女,恐怕尚未子女。

2个贰结点带有一个要素和多少个儿女(大概未有男女,不能够唯有三个亲骨血)。与二叉排序树类似,其左子树包罗的因素都低于该因素,右子树包涵的要素都赶上该因素。

1个三结点包罗三个成分和五个儿女(或者尚未子女,不能只有1个或三个孩子)。

2-3树中保有的叶子都不可能不在同样等级次序上。

图片 13

其插入操作如下:

图片 14
图片 15
图片 16
图片 17

 其除去操作如下:

图片 18
图片 19
图片 20
图片 21
图片 22
图片 23
图片 24
图片 25

2-3-4树

其实就是贰-3树的庞大,包蕴了四结点的应用。一个4结点带有小中山大学多个要素和多个孩子(或尚未男女)。

其插入操作:

图片 26

其除去操作:

图片 27

B树

B树是一种平衡的多路查找树。节点最大的孩子数目称为B树的阶(order)。贰-三树是三阶B树,二-三-4是4阶B树。

B树的数据结构首要用在内部存款和储蓄器和外存的数码交互中。

图片 28
图片 29
图片 30

B+树

为了缓和B树的具备因素遍历等为主问题,在原来的结构基础上,出席新的要素社团办公室法后,变成了B+树。

B+树是应文件系统所需而出现的1种B树的变形树,严峻意义中将,它曾经不是最大旨的树了。

B+树中,出现在分层节点中的成分会被视作他们在该支行节点地方的中序后继者(叶子节点)中另行列出。此外,每二个叶子节点都会保留一个针对性后1卡片节点的指针。

图片 31

有着的卡牌节点包涵全部的机要字的音讯,及连锁指针,叶子节点本身依关键字的分寸自小到北周序链接

B+树的布局尤其契合带有范围的搜索。举例寻觅年龄在20~二十八虚岁期间的人。

八、散列表(哈希表)

散列表:全数的因素之间从未别的关联。成分的储存地点,是采取成分的显要字通过有个别函数直接计算出来的。那些顺序对应的涉及函数称为散列函数或Hash函数。

使用散列技巧将记录存款和储蓄在1块接二连三的积攒空间中,称为散列表或哈希表(Hash
Table)。关键字对应的仓储地点,称为散列地址。

散列表是一种面向查找的积攒结构。它最符合求解的标题是搜索与给定值相等的笔录。不过对于有个别关键字能对应许多记下的处境就不适用,举个例子寻觅全数的“男”性。也不合乎范围查找,比方搜索年龄20~30之内的人。排序、最大、最小等也不得体。

故而,散列表平时用于重大字不重复的数据结构。举例python的字典数据类型。

设计出三个简约、均匀、存款和储蓄利用率高的散列函数是散列才能中最要紧的难题。

 可是,一般散列函数都面临着争论的难题。

争辨:三个例外的第二字,通过散列函数总括后结果却同样的景观。collision。

八.一 散列函数的构造方法

好的散列函数:总计轻巧、散列地址布满均匀

一.平昔定址法

 例如取关键字的某部线性函数为散列函数:

f(key) = a*key + b (a,b为常数)

2.数字分析法

 抽出关键字里的数字,依照数字的表征进行地址分配

3.平方取中国和法国 

将第壹字的数字求平方,再截取部分

4.折叠法

 将器重字的数字分割后分别计算,再统一总括,一种嘲弄数字的手腕。

伍.除留余数法

 最为广泛的法子之1。

 对于表长为m的数量集合,散列公式为:

f(key) = key mod p (p<=m)

 mod:取模(求余数)

 该办法最要害的是p的选项,而且数据量极大的时候,争辩是任天由命的。一般会选用接近m的质数。

陆.随机数法

 选取八个随意数,取关键字的随机函数值为它的散列地址。

f(key) = random(key)

小结,实际意况下基于不相同的数量性格应用分化的散列方法,思考上边一些首要难点:

  • 总结散列地址所需的小时
  • 入眼字的长短
  • 散列表的高低
  • 驷不及舌字的布满处境
  • 笔录查找的效用

八.二 管理散列争辨

一、开放定址法

正是借使发生争辩,就去搜寻下三个空的散列地址,只要散列表丰裕大,空的散列地址总能找到,并将记录存入。

公式是:

 图片 32

这种简易的争辨消除办法被称为线性探测,无非便是本人的坑被占了,就每一种拜访前边的坑,有空的就进,也不管那么些坑是或不是背后有人预订了的。

 线性探测带来的最大主题材料正是龃龉的堆成堆,你把别人预约的坑占了,旁人也将在像你同一去找坑。

精雕细刻的艺术有一回方探测法和Infiniti制数探测法。

二、再散列函数法

发生抵触时就换四个散列函数计算,总会有多少个足以把争执消除掉,它能够使得关键字不产生聚焦,但对应地增多了计算的年华。

三、链接地址法
 境遇争执时,不转变个方式置,而是将全部重大字为同义词的笔录存款和储蓄在2个链表里,在散列表中只存款和储蓄同义词子表的头指针,如下图:

图片 33

诸如此类的益处是,不怕争持多;缺点是下落了散列结构的人身自由存款和储蓄品质。本质是用单链表结构推搡散列结构的阙如。

4、公共溢出区法

实际正是为具备的顶牛,额外开荒一块存款和储蓄空间。要是相对基本表而言,争论的数码很少的时候,使用那种方法相比适宜。

图片 34

捌.叁 散列表查找完结

上边是一段轻易的得以达成代码:

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 忽略了对数据类型,元素溢出等问题的判断。


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 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))

八.4 散列表查找品质分析

假诺没发生争辨,则其查找时间复杂度为O(一),属于最极端的好了。

可是,现实中争辨可不可幸免的,上边八个方面对寻觅质量影响非常的大:

  • 散列函数是还是不是均匀
  • 拍卖争辨的点子
  • 散列表的装满因子(表内数据装满的水准)

上述正是本文的全体内容,希望对咱们的学习抱有补助,也盼望我们多多援助帮客之家。

http://www.bkjia.com/Pythonjc/1179749.htmlwww.bkjia.comtruehttp://www.bkjia.com/Pythonjc/1179749.htmlTechArticle详解常用查找数据结构及算法(Python实现),数据结构python
1、基本概念
查找(Searching)就是基于给定的某些值,在查找表中鲜明3个其…

首要分享Python 及Django教程以及有关的博客

目录

一、基本概念
2、冬辰表查找
叁、有序表查找

三.一 二分查找(Binary Search)
三.2 插值查找
三.三 斐波那契查找

四、线性索引查找

四.壹 稠密索引
四.2 分块索引
四.3 倒排索引

伍、2叉排序树
六、 平衡二叉树
七、多路查找树(B树)

7.1 2-3树
7.2 2-3-4树
7.3 B树
7.4 B+树

八、散列表(哈希表)

捌.① 散列函数的构造方法
八.二 管理散列冲突
八.三 散列表查找达成
8.四 散列表查找质量分析


参考书目《大话数据结构》

一、基本概念

探究(Searching)正是基于给定的某部值,在查找表中鲜明多少个其关键字等于给定值的数额成分(或记录)。

查找表(Search Table):由同样类别的数量成分(或记录)构成的汇聚
要害字(Key):数据成分中有些数据项的值,又称为键值。
主键(Primary Key):可唯一地方统一标准识有个别数据元素或记录的主要性字。

查找表依据操作方法可分为:

  • 静态查找表(Static Search
    Table):只做查找操作的查找表。它的首要操作是:
  • 询问有些“特定的”数据成分是不是在表中
  • 找出有些“特定的”数据成分和各类品质
  • 动态查找表(Dynamic Search
    Table):在查找中同时拓展插队或删除等操作:
  • 检索时插入数据
  • 搜索时去除数据

②、冬天表查找

相当于数量不排序的线性查找,遍历数据成分。
算法分析:最棒状态是在率先个职位就找到了,此为O(1);最坏情状在倒数地方才找到,此为O(n);所以平均查找次数为(n+1)/2。末段时间复杂度为O(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)

三、有序表查找

查找表中的数据必须按有个别主键举办某种排序!

1. 二分查找(Binary Search)

算法大旨:在查找表中不停取中间元素与查找值实行相比,以二分之一的倍率进行表范围的紧缩。

# 针对有序查找表的二分查找算法
# 时间复杂度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 False

if __name__ == '__main__':
    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = binary_search(LIST, 99)
    print(result)

二. 插值查找

二分查找法尽管曾经很科学了,但还有可以优化的位置。
一些时候,对半过滤还不够狠,尽管每一趟都免去百分之九十的数量岂不是更加好?选取那个值正是关键难题,插值的含义正是:以越来越快的速度实行削减。

插值的中央正是采取公式:
value = (key – list[low])/(list[high] – list[low])

用那一个value来替代二分查找中的八分之四。
地点的代码能够一向使用,只须求改一句。

# 插值查找算法
# 时间复杂度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 False

if __name__ == '__main__':
    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = binary_search(LIST, 444)
    print(result)

插值算法的完好时间复杂度仍旧属于O(log(n))品级的。其优点是,对于表内数据量一点都不小,且首要字遍布比较均匀的查找表,使用插值算法的平分品质比二分查找要好得多。反之,对于布满极端不均匀的数据,则不切合利用插值算法。

三. 斐波那契查找

由插值算法带来的启迪,发明了斐波这契算法。当中央也是什么优化这个缩减速率,使得搜索次数尽量下降。
动用那种算法,前提是早就有二个包涵斐波那契数据的列表
F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…]

# 斐波那契查找算法
# 时间复杂度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]-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:
                # 打印查找的次数
                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)

算法分析:斐波那契查找的完好时间复杂度也为O(log(n))。但就平均品质,要优于二分查找。不过在最坏景况下,比如此处纵然key为一,则始终处于左边半区查找,此时其效能要小于二分查找。

总括:二分查找的mid运算是加法与除法,插值查找则是错综复杂的四则运算,而斐波那契查找只是最简便的加减运算。在海量数据的探寻中,那种细微的差距恐怕会影响最后的寻找功效。由此,三种有序表的搜索方法本质上是分割点的抉择分裂,各有高低,应依靠真实情形开始展览抉择。

肆、线性索引查找

对此海量的冬天数据,为了增加查找速度,一般会为其布局索引表。
目录正是把八个首要字与它绝对应的笔录实行关联的经过。
1个索引由若干个索引项组成,每一个索引项至少含有关键字和其对应的笔录在存款和储蓄器中的地点等音讯。
目录依据协会能够分成:线性索引、树形索引和数以万计索引。
线性索引:将索引项的集结通过线性结构来组织,也叫索引表。
线性索引可分为:稠密索引、分块索引和倒排索引

  1. 稠密索引

稠密索引指的是在线性索引中,为多少集结中的各个记录都建立贰个目录项。
图片 35

那实际上就相当于给冬天的聚合,建立了一张不改变的线性表。其索引项一定是遵照关键码进行有序的排列。
那也一定于把查找进程中必要的排序专业给提前做了。

  1. 分块索引

给大气的冬天数据集结实行分块管理,使得块内冬天,块与块之间有序。
那其实是不改变查找和冬日查找的一种中间状态或然说妥协状态。因为数据量过大,建立完整的稠密索引耗费时间耗力,占用能源过多;但借使不做此外排序只怕索引,那么遍历的物色也不知所厝经受,只好折中,做一定水平的排序或索引。
图片 36

分块索引的效用比遍历查找的O(n)要高级中学一年级些,但与二分查找的O(logn)仍然要差不少。

  1. 倒排索引

不是由记录来规定属性值,而是由属性值来显著记录的地点,这种被叫作倒排索引。在那之中记录号表存款和储蓄具有同等次重大字的兼具记录的地点或引用(能够是指向记录的指针或该记录的主关键字)。

倒排索引是最基础的探索引擎索引本事。

伍、贰叉排序树

二叉排序树又叫做二叉查找树。它照旧是一颗空树,或许是颇具下列性质的2叉树:

  • 若它的左子树不为空,则左子树上全体节点的值均低于它的根结构的值;
  • 若它的右子树不为空,则右子树上全部节点的值均大于它的根结构的值;
  • 它的左、右子树也分别为贰叉排序树。
    图片 37

布局一颗贰叉排序树的目标,往往不是为着排序,而是为了抓实查找和插入删除关键字的过程。

二叉排序树的操作:

  1. 寻觅:相比较节点的值和第3字,相等则表明找到了;小了则往节点的左子树去找,大了则往右子树去找,这么递归下去,最后回来布尔值或找到的节点。
  2. 插入:从根节点开头家家户户与第一字展开相比较,小了去右侧,大了去入手,碰着子树为空的事态就将新的节点链接。
  3. 去除:假如要去除的节点是卡片,直接删;假诺唯有左子树或只有右子树,则删除节点后,将子树链接到父节点就能够;就算同时有左右子树,则能够将2叉排序树实行中序遍历,取将在被剔除的节点的前人或然后继节点代替那个被去除的节点的任务。

    #!/usr/bin/env python
    # –– coding:utf-8 –
    # Author: Liu Jiang
    # Python 3.5

class BSTNode:
    """
    定义一个二叉树节点类。
    以讨论算法为主,忽略了一些诸如对数据类型进行判断的问题。
    """
    def __init__(self, data, left=None, right=None):
        """
        初始化
        :param data: 节点储存的数据
        :param left: 节点左子树
        :param right: 节点右子树
        """
        self.data = data
        self.left = left
        self.right = right


class BinarySortTree:
    """
    基于BSTNode类的二叉排序树。维护一个根节点的指针。
    """
    def __init__(self):
        self._root = None

    def is_empty(self):
        return self._root is None

    def 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 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的父节点,用于后面的链接操作
        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.left

    def __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.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))

贰叉排序树总括:

  • 贰叉排序树以链式实行仓库储存,保持了链接结构在插入和删除操作上的帮助和益处。
  • 在Infiniti气象下,查询次数为一,但最大操作次数不会当先树的纵深。也正是说,2叉排序树的搜寻品质取决于二叉排序树的形状,也就引申出了前面包车型大巴平衡2叉树。
  • 给定1个因素集结,能够组织分化的二叉排序树,当它同时是3个截然2叉树的时候,查找的岁月复杂度为O(log(n)),近似于二分查找。
  • 当出现最极致的斜树时,其时间复杂度为O(n),等同于顺序查找,效果最差。

图片 38

6、 平衡二叉树

平衡2叉树(AVL树,发明者的全名缩写):1种中度平衡的排序2叉树,其每3个节点的左子树和右子树的万丈差最多等于壹。

平衡贰叉树首先必须是一棵二叉排序树!

平衡因子(Balance
Factor):将2叉树上节点的左子树深度减去右子树深度的值。

对于平衡贰叉树全数包含分支节点和叶节点的平衡因子只大概是-壹,0和1,只要有二个节点的因数不在那八个值之内,该2叉树正是不平衡的。

图片 39

微小不平衡子树:距离插入结点方今的,且平衡因子的绝对值不止1的节点为根的子树。

平衡2叉树的创设思想:每当插入二个新结点时,先检查是否破坏了树的平衡性,若有,寻找最小不平衡子树。在维系二叉排序树特性的前提下,调节最小不平衡子树中各结点之间的连年关系,进行对应的转动,成为新的平衡子树。

上边是由[1,2,3,4,5,6,7,10,9]构建平衡2叉树

图片 40
图片 41
图片 42
图片 43
图片 44
图片 45
图片 46

7、多路查找树(B树)

多路查找树(muitl-way search
tree):其每1个节点的孩子能够多于三个,且每多少个结点处能够积攒多少个因素。
对此多路搜索树,每一种节点能够积攒多少个成分,以及它的子女数的略微是珍视,常用的有那4种格局:2-三树、二-三-4树、B树和B+树。

2-3树

2-三树:每种结点都有所三个儿女,或然三个孩子,或然没有男女。

2个二结点包蕴1个因素和三个男女(恐怕尚未孩子,不可能唯有贰个孩子)。与二叉排序树类似,其左子树蕴涵的因素都自愧不及该因素,右子树包蕴的要素都不止该因素。
3个叁结点包括八个要素和五个孩子(大概未有男女,不可能惟有一个或七个男女)。

二-三树中全部的卡牌都必须在同样档案的次序上。

图片 47

其插入操作如下:
图片 48
图片 49
图片 50
图片 51
其删除操作如下:

图片 52
图片 53
图片 54
图片 55
图片 56
图片 57
图片 58
图片 59

2-3-4树

实则就是二-3树的扩大,包罗了四结点的利用。3个四结点包罗小中山高校多少个因素和多个男女(或从不孩子)。

其插入操作:
图片 60
其删除操作:
图片 61

B树

B树是一种平衡的多路查找树。节点最大的男女数目称为B树的阶(order)。贰-三树是三阶B树,二-叁-四是4阶B树。
B树的数据结构首要用在内部存储器和外存的数额交互中。
图片 62
图片 63
图片 64

B+树

为了消除B树的持有因素遍历等大旨难题,在原有的结构基础上,加入新的因素组织章程后,产生了B+树。

B+树是应文件系统所需而出现的一种B树的变形树,严苛意义元帅,它已经不是最主题的树了。

B+树中,现身在分层节点中的成分会被当做他们在该支行节点地点的中序后继者(叶子节点)中再一次列出。其余,每3个卡牌节点都会保留1个对准后一叶子节点的指针。
图片 65

具有的叶子节点包括全体的首要性字的音信,及有关指针,叶子节点本人依关键字的尺寸自小到金朝序链接

B+树的结构特别符合带有范围的查找。举个例子寻觅年龄在20~二十八周岁以内的人。

八、散列表(哈希表)

散列表:全部的因素之间未有任何涉及。元素的仓库储存地点,是运用成分的重大字通过某些函数直接计算出来的。这一个顺序对应的关系函数称为散列函数或Hash函数。
利用散列技巧将记录存款和储蓄在壹块一而再的仓库储存空间中,称为散列表或哈希表(Hash
Table)。关键字对应的存款和储蓄地方,称为散列地址。

散列表是壹种面向查找的仓库储存结构。它最符合求解的主题材料是搜索与给定值相等的笔录。不过对于有个别关键字能对应多数记下的状态就不适用,比方寻觅全体的“男”性。也不合乎范围查找,例如搜索年龄20~30中间的人。排序、最大、最小等也不适用。

从而,散列表平日用于入眼字不另行的数据结构。比如python的字典数据类型。

安插出二个简单易行、均匀、存款和储蓄利用率高的散列函数是散列本事中最要害的标题。
只是,一般散列函数都面临着冲突的标题。
冲突:三个不等的根本字,通过散列函数总括后结果却壹如既往的光景。collision。

八.1 散列函数的构造方法

好的散列函数:计算轻巧、散列地址遍及均匀

  1. 间接定址法
    譬如取关键字的有个别线性函数为散列函数:
    f(key) = a*key + b (a,b为常数)
  2. 数字分析法
    抽出关键字里的数字,依照数字的性状开始展览地址分配
  3. 平方取中国和法国
    将第3字的数字求平方,再截取部分
  4. 折叠法
    将根本字的数字分割后分别计算,再统一总括,一种嗤笑数字的招数。
  5. 除留余数法
    但是普及的方法之壹。
    对此表长为m的数据群集,散列公式为:
    f(key) = key mod p (p<=m)
    mod:取模(求余数)
    该方法最要紧的是p的精选,而且数据量十分大的时候,顶牛是必定的。一般会选择接近m的质数。
  6. 随机数法
    挑选三个即兴数,取关键字的随机函数值为它的散列地址。
    f(key) = random(key)

计算,实际景况下基于不一样的数据天性应用分裂的散列方法,记挂上边一些首要难题:

  • 测算散列地址所需的岁月
  • 要害字的长短
  • 散列表的深浅
  • 关键字的布满情状
  • 记录查找的频率

八.2 管理散列争持

  • 绽开定址法

正是假若发生冲突,就去找出下叁个空的散列地址,只要散列表丰富大,空的散列地址总能找到,并将记录存入。

公式是:
图片 66
那种简易的争持化解办法被称为线性探测,无非便是自个儿的坑被占了,就每个拜访前边的坑,有空的就进,也不论那一个坑是否背后有人预订了的。
线性探测带来的最大难题正是争持的积聚,你把别人预订的坑占了,外人也将要像您同一去找坑。

改革的措施有一回方探测法和自便数探测法。

  • 再散列函数法
    发生抵触时就换2个散列函数总结,总会有二个方可把争执消除掉,它能够使得关键字不发出聚焦,但对应地扩大了计算的光阴。

  • 链接地址法
    遇见冲突时,不转移地点,而是将兼具重要字为同义词的记录存款和储蓄在三个链表里,在散列表中只存款和储蓄同义词子表的头指针,如下图:
    图片 67

这般的补益是,不怕抵触多;缺点是下落了散列结构的轻便存款和储蓄质量。本质是用单链表结构推推搡搡散列结构的不足。

  • 公家溢出区法
    其实正是为保有的冲突,额外开荒壹块存款和储蓄空间。即使相对基本表来说,争执的数据很少的时候,使用那种艺术比较适合。
    图片 68

八.三 散列表查找落成

上边是壹段轻易的实今世码:

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 忽略了对数据类型,元素溢出等问题的判断。


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 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))

捌.四 散列表查找品质分析

假定没发生争持,则其查找时间复杂度为O(1),属于最极致的好了。
而是,现实中争持可不可幸免的,下边多个地点对搜索质量影响异常的大:

  • 散列函数是还是不是均匀
  • 管理争辩的方法
  • 散列表的装满因子(表内数据装满的品位)