如何选择品牌网站建设,花店商城网站设计,北京哪个区互联网公司比较多,中国住房和城乡建设部网站官网算法与数据结构
前言
什么是算法和数据结构#xff1f;
你可能会在一些教材上看到这句话#xff1a;
程序 算法 数据结构
算法#xff08;Algorithm#xff09;#xff1a;是指解题方案的准确而完整的描述#xff0c;是一系列解决问题的清晰指令#xff0c;算法代…算法与数据结构
前言
什么是算法和数据结构
你可能会在一些教材上看到这句话
程序 算法 数据结构
算法Algorithm是指解题方案的准确而完整的描述是一系列解决问题的清晰指令算法代表着用系统的方法描述解决问题的策略机制。也就是说能够对一定规范的输入在有限时间内获得所要求的输出。任何代码片段都可视为算法
数据结构Data Structures是计算机存储和组织数据的一种方式可以用来高效地处理数据。
什么样的程序才是好的程序好的程序设计无外乎两点“快和省”。快指程序执行速度快高效省指占用更小的内存空间。这两点其实就对应时间复杂度和空间复杂度的问题。
举个例子二分查找就是一个非常经典的算法而二分查找经常需要作用在一个有序数组上。这里二分就是一种折半的算法思想 而数组是我们最常用的一种数据结构支持根据下标快速访问。很多算法需要特定的数据结构来实现所以经常把它们放到一块讲。
实际上在真正的项目开发中大部分时间都是 从数据库取数据 - 数据操作和结构化 - 返回给前端在数据操作过程中需要合理地抽象 组织、处理数据如果选用了错误的数据结构就会造成代码运行低效。这也是我们需要学习算法和数据结构的原因。
学习方法
这里我们用一种很原始的方法来学习算法
阅读资料了解算法思想纸笔模拟尝试理解用自己熟悉的编程语言来实现
数据结构与类型
在往常我们的开发的的时候经常使用的数据类型或者我们自定义的类。都是可以理解成是一个抽象的数据类型ADT: Abstract Data Type它们泛指一类数据他们有拥有共同的属性与方法。
举例水杯
class glass:def __init__(self,pin_pai,size,height,color):pass实现ADT时我们应注意什么
如何选用恰当的数据结构作为存储选取的数据结构能否满足 ADT 的功能需求实现效率如何
大O表示法
大O表示法使用大写字母O可以认为其含义为order of大约是
大O表示法可以告诉我们算法的快慢
大O比较的是操作数它指出了算法运行时间的增速
O(n) 括号里的是操作数
理解不同的大O运行时间
画一个16个格子的网格下面分别列举几种不同的画法并用大O表示法表示 一次画一个格子。O(n) 折叠纸张折叠四次就能出现16个格子。O(log n)
**注意**大O表示法所表示的是一个算法在最糟糕情况下的运行时间
常见的大O运行时间
O(log n)也叫对数时间二分查找。O(n)也叫线性时间简单查找。O(n * log n)快速排序——一种速度较快的排序算法。O(n²)选择排序——一种速度较慢的排序算法。O(n!)旅行商问题的解决方案——一种非常慢的算法。 通过图我们可以比较不同的大O值O(1)是优秀O(logN)是良好O(N)是还可以O(N^2)则很差了
主要启示
算法的速度指的是操作数的增速而非时间。谈论算法速度说的是随着输入的增加其运行时间将以什么样的速度增加。用大O表示法表示算法的运行时间。随着元素的增加快算法比慢算法增加的速度是指数级的。比如O(log n)和O(n)
线性结构
本节我们从最简单和常用的线性结构开始并结合 Python 语言本身内置的数据结构和其底层实现方式来讲解。 虽然本质上数据结构的思想是语言无关的但是了解 Python 的实现方式有助于你避免一些坑
数组 array
数组是最常用到的一种线性结构其实 python 内置了一个 array 模块但是大部人甚至从来没用过它。 Python 的 array 是内存连续、存储的都是同一数据类型的结构而且只能存数值和字符。
我建议你课下看下 array 的文档https://docs.python.org/2/library/array.html
最常用的还是接下来要说的 list 本节最后我们会用 list 来实现一个固定长度、并且支持所有 Python 数据类型的数组 Array.
操作平均时间复杂度list[index]O(1)list.appendO(1)list.insertO(n)list.pop(index)O(1)list.removeO(n)
用 list 实现 Array ADT
因为在别的语言中array是定长的因此我们在此通过List来实现一个定长的数组
class Array():def __init__(self, size):self.__size sizeself.__item [None] * sizedef __getitem__(self, index):return self.__item[index]def __setitem__(self, key, value):self.__item[key] valuedef __len__(self):return self.__sizedef clear(self, valueNone):for i in range(len(self.__size)):self.__item[i] valuedef __iter__(self):for v in self.__item:yield v
if __name__ __main__:a Array(10)a[0] 10a[2] 20print(len(a))print(a.__len__())练习
完成容量内容扩展完在删除功能
参考https://github.com/python/cpython
链式结构
本节我们讲解最常见的单链表和双链表。
上一节我们分析了 list 的各种操作是如何实现的如果你还有印象的话list 在头部进行插入是个相当耗时的操作需要把后边的元素一个一个挪个位置。
假如你需要频繁在数组两头增删list 就不太合适。
今天我们介绍的链式结构将摆脱这个缺陷当然了链式结构本身也有缺陷比如你不能像数组一样随机根据下标访问你想查找一个元素只能老老实实从头遍历。 所以嘛学习和了解数据结构的原理和实现你才能准确地选择到底什么时候该用什么数据结构而不是瞎选导致代码性能很差。
单链表
和线性结构不同链式结构内存不连续的而是一个个串起来的这个时候就需要每个链接表的节点保存一个指向下一个节点的指针。 这里可不要混淆了列表和链表它们的中文发音类似但是列表 list 底层其实还是线性结构链表才是真的通过指针关联的链式结构。 看到指针你也不用怕这里我们用的 python你只需要一个简单赋值操作就能实现不用担心 c 语言里复杂的指针。
先来定义一个链接表的节点刚才说到有一个指针保存下一个节点的位置我们叫它 next 当然还需要一个 value 属性保存值
class Node:def __init__(self, value, nextNone):self.value valueself.next next然后就是我们的单链表 LinkedList ADT:
class LinkedList(object): 链接表 ADT[root] - [node0] - [node1] - [node2]来看下时间复杂度
链表操作平均时间复杂度linked_list.append(value)O(1)linked_list.appendleft(value)O(1)linked_list.find(value)O(n)linked_list.remove(value)O(n)
代码实现:
class Node():def __init__(self,valueNone,nextNone):self.value value self.next nextdef __str__(self):return Node:{}.format(self.value)
class LinkedList():def __init__(self):self.root Node()self.size 0 #记录有多少元素self.next None #增加新数据时将新数据的地址与谁关联def append(self,value):node Node(value)# 判断是否已经有数据if not self.next: #如果没有节点时self.root.next node #将新节点挂到root后面else:self.next.next node #将新节点挂到最后一个节点上self.next nodeself.size 1def append_first(self,value):node Node(value)if not self.next:self.root.next nodeself.next nodeelse:temp self.root.next # 获取原来root后面的那个节点self.root.next node # 将新的节点挂到root上node.next temp # 新的节点的下一个节点是原来的root后的节点self.size 1def __iter__(self):current self.root.nextif current:while current is not self.next:yield current.valuecurrent current.nextyield current.valuedef find(self,value):for v in self.__iter__():if v value:return Truedef find2(self,value):current self.root.nextif current:while current is not self.next:if current.value value:return currentcurrent current.nextdef remove(self,value):current self.root.nextif current:while current is not self.next: if current.value value:temp.next current.nextdel currentself.size - 1return Truetemp currentcurrent current.nextif __name__ __main__:link LinkedList()link.append(孙悟空)link.append(猪八戒)link.append_first(唐僧)for v in link:print(v)# print(link.find(孙悟空))# print(link.find(六儿猕猴))# print(link.find2(孙悟空))# print(link.find2(六儿猕猴))print(-*30)link.remove(孙悟空)for v in link:print(v)双链表
上边我们亲自实现了一个单链表但是能看到很明显的问题单链表虽然 append 是 O(1)但是它的 find 和 remove 都是 O(n)的 因为删除你也需要先查找而单链表查找只有一个方式就是从头找到尾中间找到才退出。 我们需要在一个链表里能高效的删除元素 并把它追加到访问表的最后一个位置这个时候单链表就满足不了了。
这里就要使用到双链表了相比单链表来说每个节点既保存了指向下一个节点的指针同时还保存了上一个节点的指针。
class Node(object):# 如果节点很多我们可以用 __slots__ 来节省内存把属性保存在一个 tuple 而不是 dict 里# 感兴趣可以自行搜索 python __slots____slots__ (value, prev, next)def __init__(self, valueNone, prevNone, nextNone):self.value, self.prev, self.next value, prev, next对 就多了 prev有啥优势嘛
看似我们反过来遍历双链表了。反过来从哪里开始呢我们只要让 root 的 prev 指向 tail 节点不就串起来了吗直接删除节点当然如果给的是一个值我们还是需要查找这个值在哪个节点 - 但是如果给了一个节点我们把它拿掉直接让它的前后节点互相指过去不就行了哇欧删除就是 O(1) 了两步操作就行啦
循环双端链表操作平均时间复杂度cdll.append(value)O(1)cdll.appendleft(value)O(1)cdll.remove(node)注意这里参数是 nodeO(1)cdll.headnode()O(1)cdll.tailnode()O(1)
代码
class Node():def __init__(self,valueNone,prev None, nextNone):self.value value self.prev prevself.next nextdef __str__(self):return Node: value:{}.format(self.value)
class DoubleLinkedList():def __init__(self):self.root Node()self.size 0 #记录有多少元素self.next None #增加新数据时将新数据的地址与谁关联def append(self,value):node Node(value)# 判断是否已经有数据if not self.next: #如果没有节点时self.root.next node # 将新节点挂到root后面node.prev self.root # 设置新节点的上一个节点为root节点else:self.next.next node #将新节点挂到最后一个节点上node.prev self.next # 设置新节点的上一个节点了之前的最后一个节点self.next node # 更新最后一个节点为新加的nodeself.size 1def append_first(self,value):node Node(value)if not self.next:node.prev self.root # 设置新节点的上一个节点为root节点self.next nodeelse:temp self.root.next # 获取原来root后面的那个节点node.prev self.root # 设置新node的上一个节点为rootnode.next temp # 新的节点的下一个节点是原来的root后的节点temp.prev node # 原来Node的上个节点是新的节点self.root.next node # 将新的节点挂到root上self.size 1def __iter__(self):current self.root.nextif current:while current is not self.next:yield current.valuecurrent current.nextyield current.valuedef revese_iter(self):current self.next #获取最后一节点if current:while current is not self.root:yield currentcurrent current.prevdef find(self,value):for v in self.__iter__():if v value:return Truedef find2(self,value):current self.root.nextif current:while current is not self.next:if current.value value:return currentcurrent current.nextdef remove(self):if self.end is None:return -1else:temp_node self.root.nextself.root.next temp_node.nexttemp_node.next.top self.rootself.size - 1return 1if __name__ __main__:link DoubleLinkedList()link.append(孙悟空)link.append(猪八戒)link.append_first(唐僧)for v in link.revese_iter():print(v)练习
手动实现双端链表是否可以实现循环链表
队列和栈
本节讲解的队列与栈如果你对之前的线性和链式结构顺利掌握了那么下边的队列和栈就小菜一碟了。因为我们会用前两节讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似队列是先进先出结构(FIFO, first in first out) 栈是后进先出结构(LIFO, last in first out)。
生活中的数据结构
队列。没错就是咱平常排队第一个来的第一个走
本章我们详细讲讲常用的队列
队列 Queue
如果你熟悉了上两节讲的内容这里你会选取哪个数据结构作为队列的底层存储?
class Queue():def __init__(self):self.item DoubleLinkedList()def push(self, value):self.item.append(value)def pop(self):value self.item.top_node().valueself.item.remove(value)return value用数组实现队列
难道用数组就不能实现队列了吗其实还是可以的。只不过数组是预先分配固定内存的所以如果你知道了队列的最大长度也是 可以用数组来实现的。
想象一下队列就俩操作进进出出一进一出pop 和 push 操作。 似乎只要两个下标 head, tail 就可以了。 当我们 push 的时候赋值并且前移 headpop 的时候前移 tail 就可以了。你可以在纸上 模拟下试试。列队的长度就是 head-pop这个长度必须不能大于初始化的最大程度。
如果 head 先到了数组末尾咋办重头来呗只要我们保证 tail 不会超过 head 就行。
head 0,1,2,3,4 … 0,1,2,3,4 …
重头再来循环往复仿佛一个轮回。。。。 怎么重头来呢看上边数组的规律你如果还想不起来用取模估计小学数学是体育老师教的。
maxsize 5
for i in range(100):print(i % maxsize)我们来实现一个空间有限的循环队列。ArrayQueue它的实现很简单但是缺点是需要预先知道队列的长度来分配内存。
class Queue:def __init__(self, maxsize4):self.item Array(maxsize)self.head 0self.end 0self.maxsize maxsizedef push(self, value):self.item[self.head % self.maxsize] valueself.head 1def pop(self):value self.item[self.end % self.maxsize]self.end 1return value双端队列 Double ended Queue
你可能还听过双端队列。上边讲到的队列 队头出尾尾进我们如果想头部和尾巴都能进能出呢 这就是双端队列了如果你用过 collections.deque 模块就是这个东西。他能高效在两头操作。
假如让你实现你能想起来嘛 似乎我们需要一个能 append() appendleft() popleft() pop() 都是 O(1) 的数据结构。
上边我们实现 队列的 LinkedList 可以吗貌似就差一个 pop() 最后边的元素无法实现了。 对我们还有双端链表。它有这几个方法
appendappendleftheadnode()tailnode()remove(node)
栈 Stack
from collections import dequeclass Stack():def __init__(self):self.item deque()def add(self,value):self.item.append(value)def pop(self):return self.item.pop()练习
使用 python 的 deque 来实现 queue ADT 吗是否能完成循环队列
哈希表
哈希表是种数据结构它可以提供快速的插入操作和查找操作。第一次接触哈希表时它的优点多得让人难以置信。不论哈希表中有多少数据插入和删除有时包括侧除只需要接近常量的时间即0(1的时间级。
哈希表简单的理解在记录的存储位置和它的关键字之间建立一个确定的对应关系f使每个关键字和结构中一个唯一的存储位置相对应。 哈希表最常见的例子是以学生学号为关键字的成绩表号学生的记录位置在第一条号学生的记录位置在第条…
哈希表的工作原理
哈希表基于数组的正因为数组创建后难于扩展某些哈希表被基本填满时性能下降得非常严重所以程序虽必须要清楚表中将要存储多少数据或者准备好定期地把数据转移到更大的哈希表中这是个费时的过程
如何定位数据存储的位置呢
h(key) key % size这里取模运算使得 h(key) 的结果不会超过数组的长度下标。我们来分别插入以下元素
765, 431, 96, 142, 579, 226, 903, 388
先来计算下它们应用哈希函数后的结果:
size 13
h(765) 765 % size 11
h(431) 431 % size 2
h(96) 96 % size 5
h(142) 142 % size 12
h(579) 579 % size 7
h(226) 226 % size 5
h(903) 903 % size 6
h(388) 388 % size 11哈希冲突 (collision)
这里到插入 226 这个元素的时候不幸地发现 h(226) h(96) 5不同的 key 通过我们的哈希函数计算后得到的下标一样 这种情况成为哈希冲突。怎么办呢聪明的计算机科学家又想到了办法其实一种直观的想法是如果冲突了我能不能让数组中 对应的槽变成一个链式结构呢这就是其中一种解决方法叫做 链接法(chaining)。如果我们用链接法来处理冲突后边的插入是这样的
问题但是如果哈希函数选不好的话可能就导致冲突太多一个链变得太长这样查找就不再是 O(1) 的了。 还有一种叫做开放寻址法(open addressing)它的基本思想是当一个槽被占用的时候采用一种方式来寻找下一个可用的槽。 这里槽指的是数组中的一个位置根据找下一个槽的方式不同分为
线性探查(linear probing): 当一个槽被占用找下一个可用的槽。 $ h(k, i) (h^\prime(k) i) % m, i 0,1,…,m-1 $二次探查(quadratic probing): 当一个槽被占用以二次方作为偏移量。 $ h(k, i) (h^\prime(k) c_1 c_2i^2) % m , i0,1,…,m-1 $双重散列(double hashing): 重新计算 hash 结果。 $ h(k,i) (h_1(k) ih_2(k)) % m $
我们选一个简单的二次探查函数 $ h(k, i) (home i^2) % m $它的意思是如果 遇到了冲突我们就在原始计算的位置不断加上 i 的平方。我写了段代码来模拟整个计算下标的过程
inserted_index_set set()
M 13def h(key, M13):return key % Mto_insert [765, 431, 96, 142, 579, 226, 903, 388]
for number in to_insert:index h(number)first_index indexi 1while index in inserted_index_set: # 如果计算发现已经占用继续计算得到下一个可用槽的位置print(\th({number}) {number} % M {index} collision.format(numbernumber, indexindex))index (first_index i*i) % M # 根据二次方探查的公式重新计算下一个需要插入的位置i 1else:print(h({number}) {number} % M {index}.format(numbernumber, indexindex))inserted_index_set.add(index)这段代码输出的结果如下
h(765) 765 % M 11
h(431) 431 % M 2
h(96) 96 % M 5
h(142) 142 % M 12
h(579) 579 % M 7h(226) 226 % M 5 collision
h(226) 226 % M 6h(903) 903 % M 6 collisionh(903) 903 % M 7 collision
h(903) 903 % M 10h(388) 388 % M 11 collisionh(388) 388 % M 12 collisionh(388) 388 % M 2 collisionh(388) 388 % M 7 collision
h(388) 388 % M 1Cpython 如何解决哈希冲突
如果你对 cpython 解释器的实现感兴趣可以参考下这个文件 dictobject.c。 不同 cpython 版本实现的探查方式是不同的后边我们自己实现 HashTable ADT 的时候会模仿这个探查方式来解决冲突。
The first half of collision resolution is to visit table indices via this
recurrence:j ((5*j) 1) mod 2**iFor any initial j in range(2**i), repeating that 2**i times generates each
int in range(2**i) exactly once (see any text on random-number generation for
proof). By itself, this doesnt help much: like linear probing (setting
j 1, or j - 1, on each loop trip), it scans the table entries in a fixed
order. This would be bad, except thats not the only thing we do, and its
actually *good* in the common cases where hash keys are consecutive. In an
example thats really too small to make this entirely clear, for a table of
size 2**3 the order of indices is:0 - 1 - 6 - 7 - 4 - 5 - 2 - 3 - 0 [and here its repeating]哈希函数
到这里你应该明白哈希表插入的工作原理了不过有个重要的问题之前没提到就是 hash 函数怎么选 当然是散列得到的冲突越来越小就好啦也就是说每个 key 都能尽量被等可能地散列到 m 个槽中的任何一个并且与其他 key 被散列到哪个槽位无关。 如果你感兴趣可以阅读后边提到的一些参考资料。视频里我们使用二次探查函数它相比线性探查得到的结果冲突会更少。
装载因子(load factor)
如果继续往我们的哈希表里塞东西会发生什么空间不够用。这里我们定义一个负载因子的概念(load factor)其实很简单就是已经使用的槽数比哈希表大小。 比如我们上边的例子插入了 8 个元素哈希表总大小是 13 它的 load factor 就是 $ 8/13 \approx 0.62 $。当我们继续往哈希表插入数据的时候很快就不够用了。 通常当负载因子开始超过 0.8 的时候就要新开辟空间并且重新进行散列了。
重哈希(Rehashing)
当负载因子超过 0.8 的时候需要进行 rehashing 操作了。步骤就是重新开辟一块新的空间开多大呢感兴趣的话可以看下 cpython 的 dictobject.c 文件然后搜索 GROWTH_RATE 这个关键字你会发现不同版本的 cpython 使用了不同的策略。python3.3 的策略是扩大为已经使用的槽数目的两倍。开辟了新空间以后会把原来哈希表里 不为空槽的数据重新插入到新的哈希表里插入方式和之前一样。这就是 rehashing 操作。
HashTable ADT
实践是检验真理的唯一标准这里我们来实现一个简化版的哈希表 ADT主要是为了让你更好地了解它的工作原理有了它后边实现起 dict 和 set 来就小菜一碟了。 这里我们使用到了定长数组还记得我们在数组和列表章节里实现的 Array 吧这里要用上了。
解决冲突我们使用二次探查法模拟 cpython 二次探查函数的实现。我们来实现三个哈希表最常用的基本操作这实际上也是使用字典的时候最常用的操作。
add(key, value)get(key, default)remove(key)
class Slot(object):定义一个 hash 表 数组的槽注意一个槽有三种状态看你能否想明白1.从未使用 HashMap.UNUSED。此槽没有被使用和冲突过查找时只要找到 UNUSED 就不用再继续探查了2.使用过但是 remove 了此时是 HashMap.EMPTY该探查点后边的元素扔可能是有key3.槽正在使用 Slot 节点def __init__(self, key, value):self.key, self.value key, valueclass HashTable(object):pass具体的实现和代码编写在视频里讲解。这个代码可不太好实现稍不留神就会有错我们还是通过编写单元测试验证代码的正确性。
递归与栈
递归
递归是很多算法都使用的一种编程方法具体的表现在于自己调用自己。
举例 从前有座山山里有座庙庙里有个老和尚正在给小和尚讲故事呢故事是什么呢从前有座山山里有座庙庙里有个老和尚正在给小和尚讲故事呢故事是什么呢从前有座山山里有座庙庙里有个老和尚正在给小和尚讲故事呢故事是什么呢…… 买的礼品,包装盒子里有第二层包装盒第二层包装盒里有第三层包装盒第三层包装盒里有包装纸… 如上的故事翻译成伪代码如下
def gu_shi():print(从前有座山山里有座庙庙里有个老和尚正在给小和尚讲故事呢)gu_shi()
def bao_zhuang():print(有包装继续拆)bao_zhuang()基线条件和递归条件
由于递归函数调用自己因此编写这样的函数时很容出错进而导致无线循环。例如假设你要编写一个倒计时的函数
5…4…3…2…1
为此我们可以用递归的方式编写如下所示
def count_down(i):print(i)count_donw(i-1)如果运行上面代码那么就会进入死循环直到内存益处或者强制退出(CtrlC)
编写递归函数时必须告诉它何时停止递归。正因为如此每个递归函数都有两部分基线条件 与 递归条件递归条件指的是函数调用自己而基线条件则指的是函数不再调用自己从而避免形成无限循环。
修改上面的代码如下
def count_down(i):print(i)if i1:returnelse:count_donw(i-1)调用栈
调用栈call stack不仅对编程来说很重要使用递归也必须理解这个概念
举例 我们买个来的薯愿(盒装)假如在包装时一片一片的装盒压入在最上的面的那片上添加新的薯片。在我们吃打个包装时我们上面撕开一个口一片片取出来弹出获取最上面那片薯片并吃掉 递归调用栈
递归函数也使用调用栈
举例
我们写一个5的阶乘。定义55 4 3 2 1 。同理33 2 1
def fact(x):if x1:return 1else:return x * fact(x-1)小结
递归指的是调用自己的函数每个递归函数都有两个条件基线条件和递归条件栈有两种操作压入 和 弹出所有函数调用都进入调用栈调用栈可能很长这将占用大量的内存
查找
查找可以说是我们业务代码里用得最多的操作比如我们经常需要在一个列表里找到我们需要的一个元素然后返回它的位置。 其实之前我们介绍的哈希表就是非常高效率的查找数据结构很明显地它是用空间换时间。这一节介绍两个基本的基于线性结构的查找。
线性查找
线性查找就是从头找到尾直到符合条件了就返回。比如在一个 list 中找到一个等于 5 的元素并返回下标
number_list [0, 1, 2, 3, 4, 5, 6, 7]def linear_search(value, iterable):for index, val in enumerate(iterable):if val value:return indexreturn -1assert linear_search(5, number_list) 5是不是 so easy。当然我们需要来一点花样比如传一个谓词进去你要知道在 python 里一切皆对象所以我们可以把函数当成一个参数传给另一个函数。
def linear_search_v2(predicate, iterable):for index, val in enumerate(iterable):if predicate(val):return indexreturn -1assert linear_search_v2(lambda x: x 5, number_list) 5效果是一样的但是传入一个谓词函数进去更灵活一些比如我们可以找到第一个大于或者小于 5 的从而控制函数的行为。 还能玩出什么花样呢前面我们刚学习了递归能不能发挥自虐精神没事找事用递归来实现呢
def linear_search_recusive(array, value):if len(array) 0:return -1index len(array)-1if array[index] value:return indexreturn linear_search_recusive(array[0:index], value)二分查找
上一小节说的线性查找针对的是无序序列假如一个序列已经有序了呢我们还需要从头找到尾吗当然不用折半(二分)是一种经典思想。日常生活中还有哪些经典的二分思想呢
猜数字游戏有些民间股神告诉一堆人某个股票会涨告诉另一半人会跌。后来真涨了慢慢又告诉信了他的一半人另一个股票会涨另一半说会跌。就这样韭菜多了总有一些人信奉他为股神……
举例
def binary_search(sorted_array, val):if not sorted_array:return -1beg 0end len(sorted_array) - 1while beg end:mid int((beg end) / 2) # beg (end-beg)/2 为了屏蔽 python 2/3 差异我用了强转if sorted_array[mid] val:return midelif sorted_array[mid] val:end mid - 1else:beg mid 1return -1def test_binary_search():a list(range(10))排序
冒泡排序Bubble Sort
冒泡排序Bubble Sort是一种计算机科学领域的较简单的排序算法
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端升序或降序排列就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样故名“冒泡排序”
算法原理
比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
举例 第一趟排序
第一次排序10和1比较10大于1交换位置 [1,10,35,61,89,36,55]
第二趟排序10和35比较10小于35不交换位置 [1,10,35,61,89,36,55]
第三趟排序35和61比较35小于61不交换位置 [1,10,35,61,89,36,55]
第四趟排序61和89比较61小于89不交换位置 [1,10,35,61,89,36,55]
第五趟排序89和36比较89大于36交换位置 [1,10,35,61,36,89,55]
第六趟排序89和55比较89大于55交换位置 [1,10,35,61,36,55,89]
第一趟总共进行了六次比较排序结果[1,10,35,61,36,55,89]
第二趟排序
第一次排序1和10比较1小于10不交换位置 1,10,35,61,36,55,89
第二次排序10和35比较10小于35不交换位置 1,10,35,61,36,55,89
第三次排序35和61比较35小于61不交换位置 1,10,35,61,36,55,89
第四次排序61和36比较61大于36交换位置 1,10,35,36,61,55,89
第五次排序61和55比较61大于55交换位置 1,10,35,36,55,61,89
第二趟总共进行了5次比较排序结果1,10,35,36,55,61,89
第三趟排序
1和10比较1小于10不交换位置 1,10,35,36,55,61,89
第二次排序10和35比较10小于35不交换位置 1,10,35,36,55,61,89
第三次排序35和36比较35小于36不交换位置 1,10,35,36,55,61,89
第四次排序36和61比较36小于61不交换位置 1,10,35,36,55,61,89
第三趟总共进行了4次比较排序结果1,10,35,36,55,61,89
代码如下
num [10,1,35,61,89,36,55]def bubble_sort(array):length len(array)for i in range(length - 1):for j in range(length - i-1):if array[j] array[j1]:array[j], array[j1] array[j1], array[j]选择排序Selection sort
选择排序Selection sort是一种简单直观的排序算法
算法原理
第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
举例 第一趟排序所有数据中找出最小1与第1位 10 交换位置 [1 | 10,35,61,89,36,55]
第二趟排序[10,35,61,89,36,55] 找出最小10放到第2位 [1,10 | 35,61,89,36,55]
第三趟排序[35,61,89,36,55]找出最小35放到第3位 [1,10,35 | 61,89,36,55]
第四趟排序[61,89,36,55]找出最小36放到第4位 [1,10,35,36 | 61,89,55]
第五趟排序[61,89,55]找出最小55放到第5位 [1,10,35,36,55 | 61,89]
第六趟排序[61,89]找出最小61放到第6位 [1,10,35,36,55,61 | 89]
第一趟总共进行了六次比较排序结果 [1,10,35,36,55,61,89]
代码
def selection_sort(list2):for i in range(0, len (list2)-1):min_ ifor j in range(i 1, len(list2)):if list2[j] list2[min_]:min_ jlist2[i], list2[min_] list2[min_], list2[i]插入排序Insertion sort
插入排序Insertion sort是一种简单直观且稳定的排序算法
算法原理
它的原理是 每插入一个数 都要将它 和 之前的 已经完成排序的序列进行重新排序也就是要找到新插入的数对应原序列中的位置。那么也就是说每次插入一个数都要对原来排序好的那部分序列进行重新的排序时间复杂度同样为On²。 这种算法是稳定的排序方法。
举例 第一趟排序取出第2个数据10与第1个数据排序 [1,10 | 35,61,89,36,55]
第二趟排序取出第3个数据35与前2数据排序 [1,10, 35 | 61,89,36,55]
第三趟排序取出第4个数据61与第3个数据排序 [1,10,35,61 | 89,36,55]
第四趟排序取出第5个数据89与第4个数据排序 [1,10,35,61,89 | 36,55]
第五趟排序取出第6个数据36与第5个数据排序 [1,10,35,36, 61,89 | 55]
第六趟排序取出第7个数据55与第6个数据排序 [1,10,35,36,55,61,89]
第一趟总共进行了六次比较排序结果 [1,10,35,36,55,61,89]
代码
def insert_sort(list):for i in range(1,Length): # 默认第一个元素已经在有序序列中从后面元素开始插入 for j in range(i,0,-1): # 逆向遍历比较交换位置实现插入 if list[j] list[j-1]: list[j],list[j-1] list[j-1],list[j]
print(after sort:,list)归并排序Merge sort
归并排序Merge sort是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
算法原理
从归并排序的定义来看其主要是归并操作而归并操作的前提是两个已经排序的序列所以首先需要将一个序列划分一个个有序的的序列然后再进行归并。 它的核心思想是先分后归先拆分为一个个有序的子序列再将一个个有序子序列进行归并操作最后合并为一个有序的序列 第一次分解将主序列分解成2个序列 [1,10,35,61] [89,36,55]
第二次分解将2个序列分解成4个序列 [1,10] [ 35,61] [89,36] [55]
第三次分解将4个序列分解成7个序列 [1] [10] [35] [61] [89] [36] [55]
第四次合并将7个序列合成成4个序列合并时排序 [1,10] [35,61] [36, 89 ] [55]
第五趟排序将4个序列合成成2个序列合并时排序序 [1,10, 35,61] [36, 55,89 ]
第六趟排序将2个序列合成成1个序列合并时排序 [1,10,35,36,55,61,89]
第一趟总共进行了六次比较排序结果 [1,10,35,36,55,61,89]
def merge_sort(lists):if len(lists) 1:return listsnum int( len(lists) / 2 )left MergeSort(lists[:num])right MergeSort(lists[num:])return Merge(left, right)
def merge(left,right):r, l0, 0result[]while llen(left) and rlen(right):if left[l] right[r]:result.append(left[l])l 1else:result.append(right[r])r 1result list(left[l:])result list(right[r:])return result快速排序算法(Quicksort)
快速排序Quicksort是对冒泡排序的一种改进。
算法原理
通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。 快速排序算法通过多次比较和交换来实现排序其排序流程如下 (1)首先设定一个分界值通过该分界值将数组分成左右两部分。 [ (2)将大于或等于分界值的数据集中到数组右边小于分界值的数据集中到数组的左边。此时左边部分中各元素都小于或等于分界值而右边部分中各元素都大于或等于分界值。 (3)然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。 (4)重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后整个数组的排序也就完成了 举例 代码如下
def quick_sort(data): 快速排序 if len(data) 2: # 递归入口及出口 mid data[len(data)//2] # 选取基准值也可以选取第一个或最后一个元素 left, right [], [] # 定义基准值左右两侧的列表 data.remove(mid) # 从原始数组中移除基准值 for num in data: if num mid: right.append(num) else: left.append(num) return quick_sort(left) [mid] quick_sort(right) else: return data树(Tree)
树结构是一种包括节点(nodes)和边(edges)的拥有层级关系的一种结构 它的形式和家谱树非常类似: 如果你了解 linux 文件结构tree 命令它的结构也是一棵树。我们快速看下树涉及到的一些概念 根节点(root): 树的最上层的节点任何非空的树都有一个节点路径(path): 从起始节点到终止节点经历过的边父亲(parent)除了根节点每个节点的上一层边连接的节点就是它的父亲(节点)孩子(children): 每个节点由边指向的下一层节点兄弟(siblings): 同一个父亲并且处在同一层的节点子树(subtree): 每个节点包含它所有的后代组成的子树叶子节点(leaf node): 没有孩子的节点成为叶子节点
二叉树
了解完树的结构以后我们来看树结构里一种简单但是却比较常用的树-二叉树。 二叉树是一种简单的树它的每个节点最多只能包含两个孩子以下都是一些合法的二叉树: 通过上边这幅图再来看几个二叉树相关的概念:
节点深度(depth): 节点对应的 level 数字树的高度(height): 二叉树的高度就是 level 数 1因为 level 从 0开始计算的树的宽度(width): 二叉树的宽度指的是包含最多节点的层级的节点数树的 size二叉树的节点总个数。
一棵 size 为 n 的二叉树高度最多可以是 n最小的高度是 $ \lfloor lgn \rfloor 1 $这里 log 以 2 为底简写为 lgn和算法导论保持一致。这个结果你只需要用高中的累加公式就可以得到。
一些特殊的二叉树
在了解了二叉树的术语和概念之后我们来看看一些特殊的二叉树后续章节我们会用到
满二叉树(full binary tree)
如果每个内部节点非叶节点都包含两个孩子就成为满二叉树。下边是一些例子它可以有多种形状 完全二叉树(complete binary tree)
当一个高度为 h 的完美二叉树减少到 h-1并且最底层的槽被毫无间隙地从左到右填充我们就叫它完全二叉树。 下图就是完全二叉树的例子
[
完美二叉树(perfect binary tree)
当所有的叶子节点都在同一层就是完美二叉树毫无间隙填充了 h 层。 二叉树的表示
那么怎么表示一棵二叉树呢其实你发现会和链表有一些相似之处一个节点然后节点需要保存孩子的指针我以构造下边这个二叉树为例子 我们先定义一个类表示节点 class Node(object):def __init__(self, data, leftNone, rightNone):self.data, self.left, self.right data, left, right当然和链表类似root 节点是我们的入口于是乎定义一个 二叉树
class Tree(object):def __init__(self, rootNone):self.root root怎么构造上图中的二叉树呢似乎其他课本没找到啥例子(有些例子是写了一堆嵌套节点来定义很难搞清楚层次关系)我自己定义了一种方法首先我们输入节点信息仔细看下边代码叶子节点的 left 和 right 都是 None并且只有一个根节点 A:
node_list [{data: A, left: B, right: C, is_root: True},{data: B, left: D, right: E, is_root: False},{data: D, left: None, right: None, is_root: False},{data: E, left: H, right: None, is_root: False},{data: H, left: None, right: None, is_root: False},{data: C, left: F, right: G, is_root: False},{data: F, left: None, right: None, is_root: False},{data: G, left: I, right: J, is_root: False},{data: I, left: None, right: None, is_root: False},{data: J, left: None, right: None, is_root: False},
]然后我们给 BinTreeNode 定义一个 build_from 方法当然你也可以定义一种自己的构造方法
class Tree(object):def __init__(self, rootNone):self.root rootdef install_data(self, node_list):node_dict {}{A:node(A,B,C)Bnode...}for n in node_list:node Node(n[data], n[left], n[right])node_dict[n[data]] nodefor n in node_list:node node_dict[n[data]]data:a left: node(b,d,e) right:cif node.left:node.left node_dict[node.left]if node.right:node.right node_dict[node.right]if n[is_root]:self.root node大功告成这样我们就构造了一棵二叉树对象。下边我们看看它的一些常用操作。
二叉树的遍历
不知道你有没有发现二叉树其实是一种递归结构因为单独拿出来一个 subtree 子树出来其实它还是一棵树。那遍历它就很方便啦我们可以直接用递归的方式来遍历它。但是当处理顺序不同的时候树又分为三种遍历方式:
先(根)序遍历: 先处理根之后是左子树然后是右子树中(根)序遍历: 先处理左子树之后是根最后是右子树后(根)序遍历: 先处理左子树之后是右子树最后是根
我们来看下实现其实算是比较直白的递归函数: def iter_node1(self, node):if node is not None:print(node.data)self.iter_node1(node.left)self.iter_node1(node.right)怎么样是不是挺简单的比较直白的递归函数。如果你不明白视频里我们会画个图来说明。
二叉树层序遍历
除了递归的方式遍历之外我们还可以使用层序遍历的方式。层序遍历比较直白就是从根节点开始按照一层一层的方式遍历节点。 我们可以从根节点开始之后把所有当前层的孩子都按照从左到右的顺序放到一个列表里下一次遍历所有这些孩子就可以了。 def iter_node2(self, node):node_list [node]for node in node_list:print(node.data)if node.left:node_list.append(node.left)if node.right:node_list.append(node.right)还有一种方式就是使用一个队列之前我们知道队列是一个先进先出结构如果我们按照一层一层的顺序从左往右把节点放到一个队列里 也可以实现层序遍历
def layer_trav_use_queue(self, subtree):q Queue()q.append(subtree)while not q.empty():cur_node q.pop()print(cur_node.data)if cur_node.left:q.append(cur_node.left)if cur_node.right:q.append(cur_node.right)from collections import deque
class Queue(object): # 借助内置的 deque 我们可以迅速实现一个 Queuedef __init__(self):self._items deque()def append(self, value):return self._items.append(value)def pop(self):return self._items.popleft()def empty(self):return len(self._items) 0反转二叉树 def reverse(self, subtree):if subtree is not None:subtree.left, subtree.right subtree.right, subtree.leftself.reverse(subtree.left)self.reverse(subtree.right)堆(heap)
什么是堆
堆是一种完全二叉树请你回顾下上一章的概念有最大堆和最小堆两种。
最大堆: 对于每个非叶子节点 VV 的值都比它的两个孩子大称为 最大堆特性(heap order property) 最大堆里的根总是存储最大值最小的值存储在叶节点。最小堆和最大堆相反每个非叶子节点 VV 的两个孩子的值都比它大。 堆的操作
堆提供了很有限的几个操作
插入新的值。插入比较麻烦的就是需要维持堆的特性。需要 sift-up 操作具体会在视频和代码里解释文字描述起来比较麻烦。获取并移除根节点的值。每次我们都可以获取最大值或者最小值。这个时候需要把底层最右边的节点值替换到 root 节点之后 执行 sift-down 操作。
堆的表示
之前我们用一个节点类和二叉树类表示树这里其实用数组就能实现堆。 仔细观察下因为完全二叉树的特性树不会有间隙。对于数组里的一个下标 i我们可以得到它的父亲和孩子的节点对应的下标
parent int((i-1) / 2) # 取整
left 2 * i 1
right 2 * i 2超出下标表示没有对应的孩子节点。
实现一个最大堆
class Heap:def __init__(self):self.items Array(8)self.count 0def add(self, value):# 根据count来决定将值暂时赋值到哪块空间self.items[self.count] value# 为了保证下一个数据添加时不替换上一个添加所在的索引的值self.count 1# 将本次添加的数据的索引传到 提权函数中self.sift_up(self.count - 1)def sift_up(self, index):if index 0:returnelse:parent (index - 1) / 2if self.items[parent] self.items[index]:self.items[parent], self.items[index] self.items[index], self.items[parent]self.sift_up(parent)def remove(self):value self.items[0]self.count - 1self.items[0] self.items[self.count]self.items[self.count] Noneself.sift_down(0)return valuedef sift_down(self, index):left index * 2 1right index * 2 2largest indexif right self.count:if self.item[right] self.item[largest] and self.item[right] self.item[left]:largest rightelif self.item[right] self.item[largest] and self.item[right] self.item[left]:largest leftelif self.item[right] self.item[largest] and self.item[left] self.item[largest]:largest leftelif left self.count:if self.item[left] self.item[largest]:largest leftif largest ! index:self.item[index],self.item[largest] self.item[largest],self.item[index]self.siftdown(largest)def __iter__(self):for i in self.items:if i is not None:yield i实现堆排序
上边我们实现了最大堆每次我们都能 extract 一个最大的元素了于是一个倒序排序函数就能很容易写出来了
def heapsort_reverse(array):length len(array)maxheap MaxHeap(length)for i in array:maxheap.add(i)res []for i in range(length):res.append(maxheap.extract())return resdef test_heapsort_reverse():import randoml list(range(10))random.shuffle(l)assert heapsort_reverse(l) sorted(l, reverseTrue)Python 里的 heapq 模块
python 其实自带了 heapq 模块用来实现堆的相关操作原理是类似的。请你阅读相关文档并使用内置的 heapq 模块完成堆排序。 一般我们刷题或者写业务代码的时候使用这个内置的 heapq 模块就够用了内置的实现了是最小堆。
Top K 问题(扩展)
面试题中有这样一类问题让求出大量数据中的top k 个元素比如一亿个数字中最大的100个数字。 对于这种问题有很多种解法比如直接排序、mapreduce、trie 树、分治法等当然如果内存够用直接排序是最简单的。 如果内存不够用呢 这里我们提一下使用固定大小的堆来解决这个问题的方式。
一开始的思路可能是既然求最大的 k 个数是不是应该维护一个包含 k 个元素的最大堆呢 稍微尝试下你会发现走不通。我们先用数组的前面 k 个元素建立最大堆然后对剩下的元素进行比对但是最大堆只能每次获取堆顶 最大的一个元素如果我们取下一个大于堆顶的值和堆顶替换你会发现堆底部的小数一直不会被换掉。如果下一个元素小于堆顶 就替换也不对这样可能最大的元素就被我们丢掉了。
相反我们用最小堆呢 先迭代前 k 个元素建立一个最小堆之后的元素如果小于堆顶最小值跳过否则替换堆顶元素并重新调整堆。你会发现最小堆里 慢慢就被替换成了最大的那些值并且最后堆顶是最大的 topk 个值中的最小值。 比如1000个数找10个最后堆里剩余的是 [990, 991, 992, 996, 994, 993, 997, 998, 999, 995]第一个 990 最小)
按照这个思路很容易写出来代码
import heapqclass TopK:获取大量元素 topk 大个元素固定内存思路1. 先放入元素前 k 个建立一个最小堆2. 迭代剩余元素如果当前元素小于堆顶元素跳过该元素肯定不是前 k 大否则替换堆顶元素为当前元素并重新调整堆def __init__(self, iterable, k):self.minheap []self.capacity kself.iterable iterabledef push(self, val):if len(self.minheap) self.capacity:min_val self.minheap[0]if val min_val: # 当然你可以直接 if val min_val操作这里我只是显示指出跳过这个元素passelse:heapq.heapreplace(self.minheap, val) # 返回并且pop堆顶最小值推入新的 val 值并调整堆else:heapq.heappush(self.minheap, val) # 前面 k 个元素直接放入minheapdef get_topk(self):for val in self.iterable:self.push(val)return self.minheapdef test():import randomi list(range(1000)) # 这里可以是一个可迭代元素节省内存random.shuffle(i)_ TopK(i, 10)print(_.get_topk()) # [990, 991, 992, 996, 994, 993, 997, 998, 999, 995]if __name__ __main__:test()二叉查找树(BST)
二叉树的一种应用就是来实现堆我们再看看用二叉查找树(Binary Search Tree, BST)。 前面有章节说到了查找操作包括线性查找、二分查找、哈希查找等线性查找效率比较低二分又要求必须是有序的序列 为了维持有序插入的代价比较高、哈希查找效率很高但是浪费空间。能不能有一种插入和查找都比较快的数据结构呢二叉查找树就是这样一种结构可以高效地插入和查询节点。
BST 定义
二叉查找树是这样一种二叉树结构它的每个节点的左子节点小于该节点每个节点的右子节点小于该节点 我们先来定义一下 BST 的节点结构
class BSTNode(object):def __init__(self, data, leftNone, rightNone):self.data, self.left, self.right data, left, right构造一个 BST
我们还像之前构造二叉树一样按照上图构造一个 BST 用来演示
class BST(object):def __init__(self, rootNone):self.root rootclassmethoddef build_from(cls, node_list):cls.size 0key_to_node_dict {}for node_dict in node_list:key node_dict[key]key_to_node_dict[key] BSTNode(key)for node_dict in node_list:key node_dict[key]node key_to_node_dict[key]if node_dict[is_root]:root nodenode.left key_to_node_dict.get(node_dict[left])node.right key_to_node_dict.get(node_dict[right])cls.size 1return cls(root)NODE_LIST [{key: 60, left: 12, right: 90, is_root: True},{key: 12, left: 4, right: 41, is_root: False},{key: 4, left: 1, right: None, is_root: False},{key: 1, left: None, right: None, is_root: False},{key: 41, left: 29, right: None, is_root: False},{key: 29, left: 23, right: 37, is_root: False},{key: 23, left: None, right: None, is_root: False},{key: 37, left: None, right: None, is_root: False},{key: 90, left: 71, right: 100, is_root: False},{key: 71, left: None, right: 84, is_root: False},{key: 100, left: None, right: None, is_root: False},{key: 84, left: None, right: None, is_root: False},
]
bst BST.build_from(NODE_LIST)BST 操作
查找
如何查找一个指定的节点呢根据定义我们知道每个内部节点左子树的 key 都比它小右子树的 key 都比它大所以 对于带查找的节点 search_key从根节点开始如果 search_key 大于当前 key就去右子树查找否则去左子树查找。 一直到当前节点是 None 了说明没找到对应 key。 好撸代码 def _bst_search(self, subtree, key):if subtree is None: # 没找到return Noneelif key subtree.data:return self._bst_search(subtree.left, key)elif key subtree.data:return self._bst_search(subtree.right, key)else:return subtreedef get(self, key, defaultNone):node self._bst_search(self.root, key)if node is None:return defaultelse:return node.value获取最大和最小 key 的节点
其实还按照其定义最小值就一直向着左子树找最大值一直向右子树找递归查找就行。 def _bst_min_node(self, subtree):if subtree is None:return Noneelif subtree.left is None: # 找到左子树的头return subtreeelse:return self._bst_min_node(subtree.left)def bst_min(self):node self._bst_min_node(self.root)return node.value if node else None插入
插入节点的时候我们需要一直保持 BST 的性质每次插入一个节点我们都通过递归比较把它放到正确的位置。 你会发现新节点总是被作为叶子结点插入。请你思考这是为什么 def _bst_insert(self, subtree, data): 插入并且返回根节点:param subtree::param key::param value:if subtree is None: # 插入的节点一定是根节点包括 root 为空的情况subtree BSTNode(data)elif data subtree.data:subtree.left self._bst_insert(subtree.left,data)elif data subtree.data:subtree.right self._bst_insert(subtree.right,data)return subtreedef add(self, data):node self._bst_search(self.root, data)if node is not None: # 更新已经存在的 keyreturn Falseelse:self.root self._bst_insert(self.root, data)self.size 1return True删除节点
删除操作相比上边的操作要麻烦很多首先需要定位一个节点删除节点后我们需要始终保持 BST 的性质。 删除一个节点涉及到三种情况
节点是叶节点节点有一个孩子节点有两个孩子
我们分别来看看三种情况下如何删除一个节点
删除叶节点
这是最简单的一种情况只需要把它的父亲指向它的指针设置为 None 就好。 删除只有一个孩子的节点
删除有一个孩子的节点时我们拿掉需要删除的节点之后把它的父亲指向它的孩子就行因为根据 BST 左子树都小于节点右子树都大于节点的特性删除它之后这个条件依旧满足。 删除有两个孩子的内部节点
假如我们想删除 12 这个节点改怎么做呢你的第一反应可能是按照下图的方式 但是这种方式可能会影响树的高度降低查找的效率。这里我们用另一种非常巧妙的方式。 还记得上边提到的吗如果你中序遍历 BST 并且输出每个节点的 key你会发现就是一个有序的数组。 [1 4 12 23 29 37 41 60 71 84 90 100]。这里我们定义两个概念逻辑前任(predecessor)和后继(successor)请看下图: 12 在中序遍历中的逻辑前任和后继分别是 4 和 23 节点。于是我们还有一种方法来删除 12 这个节点
找到待删除节点 N(12) 的后继节点 S(23)复制节点 S 到节点 N从 N 的右子树中删除节点 S并更新其删除后继节点后的右子树
说白了就是找到后继并且替换这里之所以能保证这种方法是正确的你会发现替换后依旧是保持了 BST 的性质。 有个问题是如何找到后继节点呢待删除节点的右子树的最小的节点不就是后继嘛上边我们已经实现了找到最小 key 的方法了。 我们开始编写代码实现和之前的操作类似我们还是通过辅助函数的形式来实现这个递归函数会比较复杂请你仔细理解: def _bst_remove(self, subtree, key):删除节点并返回根节点if subtree is None:return Noneelif key subtree.key:subtree.left self._bst_remove(subtree.left, key)return subtreeelif key subtree.key:subtree.right self._bst_remove(subtree.right, key)return subtreeelse: # 找到了需要删除的节点if subtree.left is None and subtree.right is None: # 叶节点返回 None 把其父亲指向它的指针置为 Nonereturn Noneelif subtree.left is None or subtree.right is None: # 只有一个孩子if subtree.left is not None:return subtree.left # 返回它的孩子并让它的父亲指过去else:return subtree.rightelse: # 俩孩子寻找后继节点替换并从待删节点的右子树中删除后继节点successor_node self._bst_min_node(subtree.right)subtree.key, subtree.value successor_node.key, successor_node.valuesubtree.right self._bst_remove(subtree.right, successor_node.key)return subtreedef remove(self, key):assert key in selfself.size - 1return self._bst_remove(self.root, key)延伸阅读
《Data Structures and Algorithms in Python》14 章树的概念和算法还有很多我们这里介绍最基本的帮你打个基础了解红黑树。普通二叉查找树有个很大的问题就是难以保证树的平衡极端情况下某些节点可能会非常深导致查找复杂度大幅退化。而平衡二叉树就是为了解决这个问题。请搜索对应资料了解下。了解 mysql 索引使用的 B-Tree 结构(多路平衡查找树)这个是后端面试数据库的常考点。想想为什么当元素非常多的时候二叉树的深度会很深导致多次磁盘查找。从B树、B树、B*树谈到R 树
Leetcode
验证是否是合法二叉搜索树 [validate-binary-search-tree](https://leetcode.com/problems/validate-binary-search-tree/
