8.1.1 数据存储和检索
数据访问的基本方式是基于存储位置。
找到数据的存储位置，称为检索。
概述
数据检索牵涉两个方面，一是已存储的数据集合，二是用户检索时提供的信息。检索可以是确定特定数据是否存在于数据集中；也可以是找到与所提供信息相关的数据。后一方式中，用户提供的信息被看作检索码或关键码。关键码作为数据的一部分，存储在数据集里，这就是基于关键码的数据存储和检索。
作为检索基础的关键码，通常是数据项的某种(可能具有唯一性)特征，可以是数据内容的一个组成部分；也可以是专门为数据检索建立的标签，例如学生的学号。
下面的讨论都是基于这样的基本假设：需要存储的数据元素由两部分组成，一是与检索有关的关键码，二是与之关联的数据。
字典操作和效率
实际中使用的字典可以分为两类：
1）静态字典：创建之后，字典内容和结构都不再变化，主要操作只有检索。
2）动态字典：创建之后，字典内容或结果一直处于动态变动之中，除检索操作之外，还有数据项的插入和删除等。
在字典检索中，要么检索成功要么检索失败。有关检索效率的评价标准，通常考虑在一次完整检索过程中比较关键码的平均次数，即平均检索长度。
字典和索引
索引：从关键码到数据存储位置的映射。
8.1.2 字典实现的问题
字典抽象数据类型
各种字典中都不应该允许修改关键码。
字典元素：关联
基于基本假设，一个数据项包括关键码和数据两部分，可以看成一个二元组，称之为关联。
下面定义一个关联对象的类：
1 class Assoc: 2 def __init__(self, key, value): 3 self.key = key 4 self.value = value 5 6 # python解释器遇到"<"就会去类里找该方法 7 def __lt__(self, other): 8 return self.key < other.key 9 10 def __le__(self, other): 11 return self.key <= other.key 12 13 def __str__(self): 14 return 'Assoc({0},{1})'.format(self.key, self.value)
字典的实现
一个细节。字典插入有一个特殊情况：要求插入的关键码已经在字典里了。常见处理方式包括修改已有关键码对应的值，或者插入一个新数据项，或者报错。与之对应，执行删除操作时，可能未找到相应项，或者存在多个关键码相同的项。如何处理视需求而定。
下面采用较简单的方式：如果插入时遇到关键码相同的项，就修改对应值；如果删除时没找到相应项，就什么都不做。
8.2 线性表实现
8.2.1 基本实现
将关键码和值的关联作为元素顺序存入线性表，形成关联的序列，可以作为字典的一种实现技术。检索就是在线性表里查找具有特定关键码的数据项，数据项的插入和删除都是普通的线性表操作。
python中，线性表可以使用list，其中的关联可以使用前面定义的Assoc类对象，也可以使用二元的tuple或list。
如果插入操作的实现是直接把元素放在已有元素之后，不检查重复，这就是O(1)操作。
检索操作的复杂性，考虑检索中的比较次数：
1）字典中存在该关键码：1*p0 + 2*p1 + … + n*pn-1 = 1/n*(1+2+…+n) = (n+1)/2 = O(n) # 假定每个关键码的检索概率相同。
2）字典中不存在该关键码：即经过n次比较后，以检索失败结束，复杂度仍为O(n)。
删除元素需要先检索，确定了元素位置后再删除，因此也为O(n)。
总之，由线性表实现的字典效率较低。
8.2.2 有序线性表和二分法检索
要想提高操作效率，就需要把字典里的数据项组织好，使之具有可利用的结构，从而能更好地支持检索。如果关键码取自一个有序集合，就可以按关键码的顺序排列字典中的项，检索时采用二分法实现快速检索。
1 def bi_search(lst, key): 2 left = 0 3 right = len(lst) - 1 4 while left <= right: 5 mid = (left+right)//2 6 if lst[mid].key == key: 7 return mid 8 elif lst[mid].key < key: 9 left = mid + 1 10 else: 11 right = mid - 1 12 return None
采用有序的顺序表和二分检索的优缺点：
1）检索速度块，O(logn)。
2）插入和删除操作都要移动元素，因此是O(n)操作。
3）二分法只能用于关键码可以排序、数据项按关键码排序的字典，而且只适用于顺序存储结构，需要连续的存储块，不适合实现很大的动态字典。
采用链表实现字典，检索和删除都需要顺序扫描整个表，是O(n)操作，没有任何明显优势，而且无法利用关键码排序的价值。
8.3 散列和散列表
如果数据项连续存储，而关键码就是存储数据的地址(或下标)时，基于关键码能最快找到所需数据，只需O(1)时间。但一般而言，字典所用的关键码可能不是整数，因此不能作为下标。另一方面，即使关键码是整数，也可能因为取值范围太大而不适合作为下标。例如，以身份证号做关键码，身份证号是一个18位的整数，取值范围达到1018，如果以它作为数据存储的下标，表里就需要有1018个元素位置，而实际人数为109量级。也就是说，这个表的实际填充率仅为1/109，这种存储方式显然不合适。
如果一种关键码不能或不适合作为数据存储的下标，可以考虑通过一个变换把它们映射到一种下标，这样就把基于关键码的检索转为基于整数下标的直接元素访问，有可能得到一种高效的字典实现技术。
以散列表的思想实现字典，具体方法是：
1）选定一个整数的下标范围(通常以0或1开始)，建立一个包括相应元素位置范围的顺序表。
2）选定一个从实际关键码集合到上述下标范围的适当映射h：
1. 当存入关键码为key的数据时，将其存入表中第h(key)个位置。
2. 当检索以hey为关键码的数据时，直接去找表中第h(key)个位置的元素。
散列技术：设计和性质
针对一种关键码实现字典时，所用下标集合通常都远远小于关键码集合的规模。也就是说，散列函数h是从一个大集合到一个小集合的映射。这样必然会出现多个不同的关键码被h对应到同一个下标位置的情况，也就是说，必然会出现key1 != key2但h(key1) = h(key2)的情况。这种情况称为冲突(或碰撞)，此时称key1和key2为h下的同义词。冲突是散列表使用中必然出现的情况，在考虑散列表的实现时，必须考虑如何解决冲突的问题。
这里有一个考察散列表在运行中的性质的参数：负载因子a = 散列表中当时的实际数据项数 / 散列表的基本存储区能容纳的元素个数。
负载因子越大，出现冲突的可能性越大。如果扩大散列表的存储空间，负载因子是会减小，但散列表里的空闲空间也会越大。
总之，基于散列技术实现字典，必须解决两大问题：散列函数的设计、冲突的消解机制。
8.3.2 散列函数
在设计字典时，首先应该根据实际需要确定数据项集合，选定相应的关键码集合KEY。为了实现散列表字典，还要确定一个存储位置区间INDEX。它们分别是散列函数的定义域和值域，是定义散列函数的基础。
设计散列函数，最重要的考虑就是尽可能减少出现冲突的可能性。为此：
1）函数应能把关键码映射到值域INDEX中尽可能大的部分。
2）不同关键码的散列值在INDEX里均匀分布。(实际情况还与关键码分布有关，如果不知道关键码的实际分布，就只能考虑均匀分布。)
3）函数的计算比较简单，使用散列表的本意就是提高效率，不能开销过大。
用于整数关键码的若干散列方法
1）数字分析法：适用于关键码集合已知的情况。
2）折叠法，将较长的关键码切分为几段，通过某种运算将其合并。
3）中平方法，先求出关键码的平方值，然后取出其中几位作为散列值。
常用散列函数
通用的散列方法只能基于关键码集合的均匀分布假设。实际中最常用的是除余法和基数转换法。
1）除余法：关键码key是整数，用key除以某个不大于散列表长度m的整数p，得到的余数(或者余数加 l，由下标开始值确定)作为散列地址。
为了存储管理方便，经常将m取为2的某个幂值，此时p可以取小于m的最大素数。例如m取128、256、512、1024时，p可以分别取127、251、503、1023。除余法在实际中使用最为广泛，还常用于将其他散列函数的结果归入所需区间。
设计散列函数的一个基本想法是使得到的结果尽可能没有明显规律。而如果用偶数做除数，就会出现偶数关键码映射到偶数散列值，奇数关键码映射到奇数散列值的情况。这种情况应该避免。
除余法的一个缺点是相近的关键码(如值相差1)将映射到相近的值。如果关键码的数字位数较多，可以考虑用较大的除数求余，然后去掉最低位(或去掉最低的一个或几个二进制位)，以排除最低位的规律性。还可以考虑其他方法排除规律性。
2）基数转换法：先考虑整数关键码。把关键码看作基数为r 的数(也就是r 进制)，将其转换为十进制或二进制数。通常r 取素数以减少规律性。
例如取r=13，关键码335647，有下面计算：
然后整数的散列方法将其归入所需下标范围。
以字符串作为关键码。最常见的散列方法是把一个字符看作一个整数(直接用字符的编码值)，把一个字符串看作以某个整数为基数的“整数”，以素数29或31为基数，通过基数转换法把字符串转换为整数，再用整数的散列方法(例如求余法)，把结果归入散列表的下标范围。
8.3.3 冲突的内消解：开地址技术
冲突消解方法分为两类：
1）内消解：即在基本的存储区内部解决冲突问题
2）外消解：即在基本的存储区外部解决冲突。
在散列表的使用中需要插入数据项时，用散列函数根据关键码算出了存储位置，但却发现那里已经有关键码不同的项了，这时就知道出现了冲突。处理冲突，有两方面的基本要求：
1）保证当前这次存入数据项的工作能正常完成。
2）保证字典的基本存储性质：即在任何时候，从任何以前存入字典而后没有删除的关键码出发，都能找到对应的数据项。
也就是，能存入新数据，又不影响旧数据。
开地址法和探查序列
开地址法的基本思想是：在准备插入数据并发现冲突时，设法在基本存储区里为需要插入的数据项另行安排一个位置。
为此需要设计一种系统的且易于计算的位置安排方式，称为探查方式。线性探查和双散列探查。
线性探查：随着表中数据的增加，产生冲突的可能性也不断增长。数据在表中逐渐堆及成段，使线性探查序列变得越来越长。新关键码不仅与前面的同义词冲突，而且可能与由于冲突而迁移来的关键码冲突，情况变得越来越糟，字典操作的效率大大下降。
双散列探查：检查位置以不同方式跳跃进行，有可能减少关键码堆积的情况，但随着表中元素的增加，冲突越来越严重的情况不会改变。
开地址方法下的检索和删除
检索过程：
开地址法给删除操作带来了一个麻烦：被删除的数据有可能处于其他元素的探索路径上，如果简单地将其删除，就会切断其他元素的探索路径，导致那些元素“失联”。解决方法是：不在被删除的元素位置放入空位标志，而是存入另一个特殊标记。在执行检索操作时，将其看作有元素并继续向下探查；在执行插入操作时，则将其看作空位，把新元素存入这里。
总之，内消解法不适合有大量元素的表。
8.3.4 外消解技术
溢出区方法
当插入关键码的散列位置没有数据时就直接插入，发生冲突时将相应数据项存入溢出区，数据项在溢出区里顺序排列。对应的检索和删除操作也是先找到散列位置，如果那里有数据但关键码不匹配，就转到溢出区顺序检索，直至找到要找的关键码，或确定相应数据项不存在。
桶散列方法
另一冲突消解方式是数据项不存放在散列表的基本存储区里，而是另外存放，在散列表里保存对数据的引用，这种设计被称为桶散列。其中最简单的设计是拉链法。
在桶散列技术里，散列表的每个元素只是一个引用域，引用着一个保存实际数据的存储桶，具体字典可以采用不同的存储桶结构，拉链法中一个存储桶就是一个链表。具有同样散列值的数据项保存在同一个桶里。
实例：
拉链法是最简单的桶结构，可以换为其他结构。这种“同义词表”也可以采用顺序表或散列表，还可以采用其他结构。桶散列结构可用于实现大型字典，用于组织大量的数据，包括外存文件等。
8.3.5 散列表的性质
扩大存储区，用空间交换时间
当负载因子达到一定程度时，扩大散列表的基本存储区。问题是不能简单地把元素拷贝到新存储区。存储区扩大后，需要相应调整散列函数，以便尽可能利用增加的存储单元。然后，把字典里已有数据项重新散列到新存储区。可见，扩大存储要付出重新分配存储区和再散列装入数据项的代价。
负载因子和操作效率
散列表的负载因子对效率有决定性的影响。根据经验：采用内部消解技术时，负载因子a<=0.7~0.75时，散列表的平均检索长度接近于常数。采用桶散列技术时，负载因子就是桶的平均大小，随着负载因子变大，检索时间也趋于线性(平均桶长 = 数据项数 / 桶数)。
只有在下面这两个假设下，散列表字典检索、插入、删除操作的时间开销才能看作常量：
1）实际存入字典的数据(的关键码)的散列函数值均匀分布。
2）字典散列表的负载因子不能太高(试验证明应在0.7以下)。
一些必然情况：
1）常量时间的操作代价是平均代价，不是每次操作的实际代价。由于不同元素的探查序列长度不一，可能出现有些操作代价较高的情况。
2）一般而言，关键码冲突是必然发生的情况，并因此导致不同操作的代价之间差异可能很大，而且不能事先确知。
3）不断插入元素导致负载因子不断增大。为了保证操作效率就需要扩大存储，从而导致一次高代价的插入操作。而且，无法预知高代价什么时候出现。
4）字典内部数据项的排列顺序无法预知，也没有任何保证。
8.4 集合
8.4.1 集合的概念、运算和抽象数据类型
概念和集合描述
描述集合的一种方法是明确列出其中的所有元素，这种写法称为集合的外延表示，例如，{1, 2, 3}。这种外延表示只能描述有穷集合。
集合的另一种描述方法是给出集合中的元素应该满足的性质，这种表示称为集合的描述式，或集合的内涵表示。
一个集合中元素个数称为该集合的基数，或集合的大小。无穷集合也有不同的基数，是集合论中的一个基本结论。
两个集合S和T相等，当且仅当它们包含同样的元素。
集合之际另一重要关系是子集关系。如果集合S中所有元素都是集合T的元素，则说S是T的子集。显然，一个集合也是其自身的子集，空集是任何集合的子集。
如果两个集合相等，则它们互为子集。
如果S是T的子集，但两个集合不相等，则说S是T的真子集。
集合运算：并集、交集、差集
抽象数据类型
8.4.2 集合的实现
成员关系判断需要在集合里做检索，集合的元素在这里起的作用类似于关键码在字典中的作用，只是没有关联数据。也就是说，任何字典实现技术都可以用于实现集合。除了求并集、交集、差集这些集合运算外，像其他的判断元素与集合的关系、创建/空集检查/加入/删除等操作，字典里都有与之对应的操作。
简单线性表实现
下面两套插入和删除方式都可以正确实现集合的功能：
1）插入元素时，检查它是否已在集合中，保证集合中元素的唯一性；删除元素时找到第一个相同元素并将其删除。(保持唯一性)
2）插入元素时，简单地将其加入集合；删除时检查整个集合，删除指定元素的所有拷贝。(不要求唯一性)
集合运算的实现：求交集，需要找到所有同属于两个集合的元素。为找到这些元素，就要逐个考察一个集合的元素，如果它也属于另一集合就将其加入结果集合。假定两个集合的大小分布为m、n。检查第一个集合的各元素，需要检查元素m次，判断每个元素是否也属于另一集合是O(n)操作，所以求交集的复杂度为O(m*n)。求并集和差集的情况与此类似，几个操作的代价都比较高。
由于这些操作都用顺序扫描的方式工作，具体实现采用顺序表或链表都可以，操作效率方面没有本质区别。总之，主要缺点就是元素判断(插入、插入都需要先判断)和集合运算的效率比较低。
排序顺序表实现
如果元素上存在一种序关系，例如，整数的小于等于、字符串的字典序等，就可以在顺序表里采用排序的方式存储元素。这样，检索操作就可以在O(logn)时间完成。
要保证元素唯一性就必须扫描表中元素，设表中元素从小到大排序，插入元素时可以用下面的方式：
假设把e插入s，
用二分检索在s里查找e，
如果找到就结束，
否则就确定了插入位置，后移后面的元素并实际插入e。
显然，这个操作的复杂度与简单顺序表中的相应操作一样，但实际使用中有可能更高效(如果s里有e就不必插入元素)。
采用顺序方式存储表中元素，能够大大提高各种集合运算的效率。
1 def intersection(s, t): 2 i = 0 3 j = 0 4 r = [] 5 while i < len(s) and j < len(t): 6 if t[j] == s[i]: 7 r.append(s[i]) 8 j += 1 9 i += 1 10 elif t[j] < s[i]: 11 j += 1 12 else: 13 i += 1 14 print(r)
复杂度分析，主循环的每次迭代总能处理掉两个集合里的至少一个元素，所以，这个操作的时间复杂度是O(m+n)，与简单顺序表的O(m*n)相比有质的提高。类似技术也可以用于实现并集/差集操作，将它们的复杂度也变为O(m+n)。
散列表实现
1）一个集合就是一个散列表。
2）插入/删除元素对应于散列表中插入/删除关键码。
3）集合元素判断对应于关键码搜索。
4）各种集合运算都基于上面几个散列表操作，采用建立新散列表的方式实现，没有实质性的困难。
这样，各种集合操作的效率就完全由散列表的性质确定，具有概率性。最佳情况下，各种操作都很高效：插入/删除和元素判断操作的代价几乎是常量；求交集/并集/差集具有近乎O(m+n)复杂度。为实现这些操作，需要有一种遍历散列表的方法，不难实现。
(反过来说，基于散列表导致没有确定性的效率保证，不适合用于对效率有严格要求的环境。另外，散列表中不存在遍历元素的明确顺序。)
8.4.3 特殊实现方法：位向量实现
一个元素是否属于一个集合，是一种二值判断。基于这一认识，人们提出了一种专门的集合实现技术：集合的位向量表示。如果在程序里需要使用的一批集合对象有一个(不太大的)公共超集U，就可以考虑用位向量技术实现这些集合。具体实现方法是：
1）假定U包含n个元素，给每个元素确定一个编号作为该元素的下标。
2）对任何一个要考虑的集合S，用一个n位的二进制序列(位向量)vs表示，方法是：对任何属于U的元素e，如果e也属于S，就令vs里对应e的那个二进制位取值为1，否则取值为0。
显然，要检查一个元素e是否属于集合S，只需检查vs里对应e的那个位是否为1；将元素e加入集合S实现为将vs里对应e的位设置为1；从S里删除e实现为将vs里对应e的位设置为0；S的元素个数实现为统计vs里值为1的二进制位的个数；全0的n位二进制序列对应空集；全1的n位二进制序列对应U。集合运算可以通过逐位操作实现。
采用位向量表示，操作的代价都需要基于集合U的大小度量，而不能基于被操作集合的实际元素个数度量。因此，无论被操作集合的元素多么少，即使为空集，它的表示也与其他集合一样大，扫描其元素也需扫描整个位向量。
8.5 python的标准字典类dict和set
python中，字典和两个集合(set、frozenset)都是基于散列表技术实现的数据结构，采用内消极技术解决冲突。下面介绍一些细节，以dict为例：
1）在创建空字典或很小的字典时，初始分配的存储区可容纳8个元素。
2）dict对象在负载因子超过2/3时自动更换更大的存储区，并把已经保存的内容重新散列到新存储区。如果当前字典对象不太大，就按当时字典中实际元素的4倍分配新存储区；当元素超过50000时，改为按实际元素个数的2倍分配存储区。
python中的hash函数：
1）对一个对象调用hash函数，它或者返回一个整数，或者抛出一个参数异常，表示本函数对该对象无定义。这里无定义的对象指的是可变对象。对python内置的不变类型(str、tuple、frozenset)，hash函数都有定义。
2）当a == b时，两个对象的hash值相同。
3）当程序调用标准函数hash时，python解释器就会到参数所属类里去找__hash__方法。
4）如果希望自定义类的对象也能作为dict或set等的关键码，就应该为这个类定义一个__hash__方法。
8.6 二叉排序树和字典
前面讨论了用线性表和散列表两种结构实现字典。这两种结构都把字典存储在一个连续存储块里，难以用于实现非常巨大的字典。
为了更好地支持存储内容的动态变化，应该考虑采用链接结构。基于链接结构，也很容易用大量的小存储块构造出大规模的容器，比如巨型字典。
进一步就会想到树形结构，因为：
1）用链接方式实现，因此比较容易处理元素的动态插入/删除。
2）在树形结构里，从根到任意结点的平均路径的长度可以小到结点个数的对数，因此可能实现高效操作。
下面讨论基于二叉树的字典实现技术。
树结构最重要的特点：
1）如果树结构“良好”，其中最长路径的长度与树中结点个数呈对数关系。
2）如果树结构“畸形”，其中最长路径的长度可能与结点个数呈线性关系。
8.6.1 二叉排序树
定义和性质
二叉排序树是一种在结点里存储数据的二叉树。一棵非空二叉排序树具有以下性质：
1）其根结点保存着一个数据项(及其关键码)。
2）如果左子树非空，那么其左子树的所有结点里保存的(关键码)值均小于(或不大于)根结点保存的(关键码)值。(具有递归性质)。进一步说其右子树的任一结点都大于左子树的任一结点。
3）如果右子树非空，那么其右子树的所有结点里保存的(关键码)值均大于(或不小于)根结点保存的(关键码)值。(具有递归性质)
4）非空左子树或右子树也是二叉排序树。(是一种递归结构)
根据二叉排序树中数据的存储方式，如果对一棵二叉排序树做中根序遍历，将得到一个按关键码排序的递增序列。如果树中存在重复关键码，虽然其数据项的前后顺序不能确定，但这些项必定位于中序遍历序列的相邻位置。
同一集数据对应的二叉排序树不唯一。例如[36, 65, 18, 7, 60, 89, 43, 57, 96, 52, 74]的二叉排序树：
二叉排序树上的检索
二叉排序树上的检索算法：由于在根中保存的数据总把树中的数据划分为较小和较大的两组，用检索关键码与之比较，就能知道下一步应该到哪棵子树去检索(递归过程)。
1 def bt_search(btree, key): 2 bt = btree 3 while not bt: 4 entry = bt.data 5 if key < entry.key: 6 bt = bt.left 7 elif key > entry.key: 8 bt = bt.right 9 else: 10 return entry.value 11 return None
二叉排序树(字典)类
这个类的接口应该参考前面给出的字典抽象数据类型，其基础元素是前面定义的二叉树结点类和关联类。
创建空树，判断是否为空，检索：
1 class DictBinTree: 2 def __init__(self): 3 self._root = None 4 5 def is_empty(self): 6 return self._root == None 7 8 def search(self, key): # 检索 9 bt = self._root 10 while bt: 11 entry = bt.data 12 if key < entry.key: 13 bt = bt.left 14 elif key > entry.key: 15 bt = bt.right 16 else: 17 return entry.value 18 return None
插入和删除操作通常都要修改树的结构。不仅要保证二叉树的结构完整，还要保持树中结点数据的正确顺序。
字典插入遇到的一个问题：当遇到与检索关键码相同的数据项时怎么办？报错、什么都不做、允许关键码重复、替换已有关联值。
基于检索插入数据的基本算法如下：
1）如果二叉树为空，就直接建立一个包括新关键码和关联值的根结点。
2）否则搜索新结点的插入位置，沿子结点关系向下：
1. 遇到应该走向左子树而左子树为空，或者应该走右子树而右子树为空时，就找到了新字典项的插入位置。
2. 遇到结点里的关键码等于被检索关键码，直接替换关联值并结束。
实例为insert方法。
遍历二叉排序树(只要关联数据)：给字典定义一个迭代器，生成其中所有值的序列，以便可以通过for循环或其他方式使用字典里的数据。实例为values方法。
遍历二叉排序树(关键码、关联数据都要)：最简单的方式是yield语句直接返回t.data，但是这样做极不安全，因为t.data是一个Assoc对象。该对象不仅保存着一个关键码--值关联，其中的关键码还是整个二叉排序树数据完整性的一部分。如果用户得到这个关联对象，有意或无意地修改了key值，整个字典可能就破坏了，不再是一个二叉排序树了。修改实例为entries方法。这样只要关键码本身是不变对象，用户就不能破坏字典的完整性。
删除具有给定关键码的元素：这是二叉排序树中最复杂的操作。实例为delete方法。
实现方法有多种，例如遍历这棵树，用树中的项另做一棵二叉排序树，构造中丢掉要删除的项。剩下的项可以做多棵不同的树。这种方法的缺点是代价高，需要耗费与树中结点成比例的时间。要降低操作代价，就应尽量利用原有结构，只做局部修改和调整。基本想法是先找到要删除的树结点，将其删除；如果删除破坏了二叉排序树的结构，就在被删除结点周围做尽可能小的局部调整。二叉排序树的性质：中根序遍历将得到关键码的递增序列。这一性质可以用来检验算法的正确性。
假定要删除的结点为q，它是其父结点p的左子结点(为p的右子结点情况类似)，这时有两种情况：
1）q是叶子结点，这时只需将其父结点p到q的引用设置为None，树中剩余结点仍构成一棵二叉排序树。
2）q不是叶子结点，这时删除q结点之后，还需要把q的子树连接到删除q之后的树中，而且要保证关键码的顺序。又分两种情况：
1. 如果q没有左子结点，这时只需把q的右子树直接改作其父结点p的左子树。
(这时如果q的右子结点比p大，那就不是二叉排序树了？ 这是个陷阱，因为如果q的右子结点比p大，删除q之前就不是二叉排序树，如下图)。
2. q有左子树(可能没有右子树，可以统一处理)，这时先找到q的左子树的最右结点r，显然它没有右子树。用q的左子树结点代替q作为p的左子结点，并将q的右子树(如果有的话)作为r 的右子树。
按照二叉排序树的性质，r是一定小于k的，因为r小于p，而p又小于k，所以r小于k。
q不是叶子结点的两种情况如下图：
3）q是根结点。(这个在是否有左子树中分别讨论)
最后定义一个函数，它不是二叉排序树类的一部分，而是一个独立函数，基于一系列数据项建立起一棵二叉排序树。
1 #!coding:utf8 2 3 class Assoc: 4 def __init__(self, key, value): 5 self.key = key 6 self.value = value 7 8 def __lt__(self, other): # python解释器遇到'<'就会去找类里定义的__lt__方法 9 return self.key < other.key 10 11 def __le__(self, other): 12 return self.key <= other.key 13 14 def __str__(self): 15 return 'Assoc({0}, {1})'.format(self.key, self.value) 16 17 class BinTNode: 18 def __init__(self, data, left=None, right=None): 19 self.data = data 20 self.left = left 21 self.right = right 22 23 class StackUnderflow(ValueError): 24 pass 25 26 # 遍历二叉树时会用到 27 class SStack(): 28 def __init__(self): 29 self._elems = [] 30 31 def is_empty(self): 32 return self._elems == [] 33 34 def top(self): 35 if self.is_empty(): 36 raise StackUnderflow("in SStack.top()") 37 return self._elems[-1] 38 39 def push(self, elem): 40 self._elems.append(elem) 41 42 def pop(self): 43 # if self._elems == []: 44 if self.is_empty(): 45 raise StackUnderflow("in SStack.top()") 46 return self._elems.pop() 47 48 class DictBinTree: 49 def __init__(self): 50 self._root = None 51 52 def is_empty(self): 53 return self._root == None 54 55 def search(self, key): 56 bt = self._root 57 while bt: 58 entry = bt.data 59 if key < entry.key: 60 bt = bt.left 61 elif key > entry.key: 62 bt = bt.right 63 else: 64 return entry.value 65 return None 66 67 def insert(self, key, value): 68 bt = self._root # bt是结点对象(BinTNode) 69 if not bt: 70 self._root = BinTNode(Assoc(key, value)) 71 return 72 while True: 73 entry = bt.data # entry是关联对象(Assoc) 74 if key < entry.key: 75 if not bt.left: 76 bt.left = BinTNode(Assoc(key, value)) 77 bt = bt.left 78 elif key > entry.key: 79 if not bt.right: 80 bt.right = BinTNode(Assoc(key, value)) 81 bt = bt.right 82 else: 83 entry.value = value 84 return 85 86 # 中序遍历二叉树，需要一个栈保存临时数据 87 def values(self): 88 t, s = self._root, SStack() 89 while t or not s.is_empty(): # 因为是中根序遍历，所以当右子树为空时表明一个小局部已遍历完，就要从栈中取上一层结点。 90 while t: 91 s.push(t) 92 t = t.left 93 t = s.pop() 94 yield t.data.value 95 t = t.right 96 97 def entries(self): 98 t, s = self._root, SStack() 99 while t or not s.is_empty(): # 因为是中根序遍历，所以当右子树为空时表明一个小局部已遍历完，就要从栈中取上一层结点。 100 while t: 101 s.push(t) 102 t = t.left 103 t = s.pop() 104 yield t.data.key, t.data.value 105 t = t.right 106 107 def delete(self, key): 108 p, q = None, self._root 109 while q and q.data.key != key: 110 p = q 111 if key < q.data.key: 112 q = q.left 113 else: 114 q = q.right 115 if not q: 116 return # 没找到 117 118 # q没有左子树 119 if not q.left: 120 if not p: # q是根结点 121 self._root = q.right # q没有左子树 122 elif q is p.left: # q是p的左子结点 123 p.left = q.right 124 else: # q是p的右子结点 125 p.right = q.right 126 return 127 128 # q有左子树 129 # 找q的左子树的最右边结点 130 r = q.left 131 while r.right: 132 r = r.right 133 r.right = q.right 134 if not p: # q是根结点 135 self._root = q.left 136 elif q is p.left: 137 p.left = q.left 138 else: 139 p.right = q.left 140 141 def prints(self): 142 for k, v in self.entries(): 143 print(k, v) 144 145 146 def build_dictBinTree(entries): 147 bt = DictBinTree() 148 for k, v in entries: 149 bt.insert(k, v) 150 return bt 151 152 li = [('name', 'yangxl'), ('gender', 'male'), ('age', 28)] 153 build_dictBinTree(li)
性质分析
遍历操作已在第6章已讨论过，不再赘述。主要考虑检索、插入和删除操作。
检索是三个操作中共有的部分，插入和删除都需要先做检索。在插入操作中，检索完成后在实际插入结点的动作是局部的，常量时间就能完成。在删除操作中，找到要删除的结点之后，还要再做一次检索(检索要删除结点的左子树的最右边结点)，两次检索在同一条路径上，先到达被删除结点，再继续到达其左子树的最右结点。因此在删除操作中需要检查的结点总数不超过树中最长路径的长度。所以决定操作开销的那部分动作都是沿着二叉排序树中的一条路径下行。因此这些操作的效率依赖于被操作树的结构，每做一次比较下行一层，最大开销受囿于树中最长路径的长度，也就是二叉树的高度。最好情况是O(logn)，最坏情况是O(n)。函数build_dictBinTree中的实参序列，如果关键码递增或递减，就能得到一个高度等于结点个数的二叉排序树。
研究表明，n个结点的所有可能二叉树的平均高度为O(logn)，基于这个事实，可以认为在二叉排序树中做检索，平均复杂度为O(logn)。
空间复杂度为O(1)。
8.6.2 最佳二叉排序树
此处的最佳是基于检索效率
平均检索长度
在一棵二叉排序树的实际检索中，可能使用树中存在的关键码，也可能使用树中不存在的关键码。在考虑检索效率时，应该综合考虑这些情况，基于所有可能及其出现频率，做出某种平均检索长度，用于评价这棵二叉排序树的优劣。
首先，用树中存在的关键码检索，能找到存储着相应数据项的结点；如果用树中不存在的关键码检索，最终将到达一个结点，这个结点在树的外部。这种关系可以用扩充二叉树表示。
矩形结点表示树的外部结点，用(m, n)表示这个开区间，用这个开区间里的值作为检索关键码，最终将达到这个外部结点。
按照中根序遍历扩充二叉树，得到的将是原树内部结点和外部结点交叉排列的结点序列(即外、内、外、内...)。这个结点序列称为扩充二叉排序树的对称序列。对一个排序的关键码序列，存在多棵不同的二叉排序树。这些二叉排序树的中根遍历序列都是一样的，它们的扩充二叉排序树的对称序列也完全一样。？？
在这种扩充二叉排序树里，关键码的平均检索长度由下面公式给出：
最佳二叉排序树就是使检索的平均比较次数最少，即E(n)值最小。然后下面的问题就是，如果给定了一组关键码，以及一组分布pi 和qi，如何构造出相应的最佳二叉排序树？
简单情况：检索效率相同
最低的树最好。
构造最低树的算法：左右子树的结点数均分。算法如下：
显然，以关键码个数为n，基于已经按关键码排序的序列构造最佳二叉排序树，上述构造算法的复杂度为O(n)。另外，从排序算法的有关研究可知，对于n个关键码序列，最高效的排序算法的复杂度为O(n*logn)。由此，如果从任一一组关键码出发，整个构造过程的复杂度为O(n*logn)。？？
构造函数的参数可以是任何序列，但要求其中的元素可以比较大小，这样才能使用python内置的sort函数排序，得到一个排序的表。在递归调用中需要用到原表中的片段，在算法实现中没有真做切片，而是直接传递整个表和一对表示范围的下标，这样做可以避免实际做出很多表片段的拷贝。
1 class DictOptBinTree(DictBinTree): 2 def __init__(self, seq): 3 DictBinTree.__init__(self) 4 data = sorted(seq) 5 self._root = DictOptBinTree.buildOBT(data, 0, len(data)-1) # 这里不能改为普通类方法。 6 7 @staticmethod 8 def buildOBT(data, start, end): 9 if start > end: # 递归结束条件 10 return 11 mid = (start+end) // 2 12 left = DictOptBinTree.buildOBT(data, start, mid-1) 13 right = DictOptBinTree.buildOBT(data, mid+1, end) 14 return BinTNode(Assoc(*data[mid]), left, right) # '*'用来匹配参数 15 16 li = [(65, 650), (36, 360), (60, 600), (18, 180), (7, 70), (89, 890), (96, 960), (43, 430), (57, 570), (74, 740), (52, 520)] 17 opbt = DictOptBinTree(li) 18 opbt.prints()
注意：插入和删除操作只能保证二叉排序树的结构完整，保证字典的基本功能。但不能保证二叉排序树的最佳性质，反复做插入和删除的动态操作，通常会导致字典的性能逐渐变差。
8.6.3 一般情况的最佳二叉排序树
不再假设访问概率相同。虽然从实际角度看，这种构造的意义不大，但下面算法设计中的思想却值得学习，这种想法称为动态规划。
问题与性质
E(0, n)是包含n个内部节点和n+1个外部节点的树的带权路径长度。
最佳二叉排序树由一个重要性质：它的任何子树也是最佳二叉排序树。这个性质说明一棵最佳二叉排序树是两棵较小的最佳二叉排序树的组合。如果存在多种可能的组合，都能得到包含同样内部结点(和外部结点)的二叉排序树，就应该选择其中的最佳组合。
首先应看到，由于存在检索频度的差异，层数最小的树未必最佳。左图二叉排序树最低，搜索路径长度之和为3*1+(2+7+2+1+4+9)*2=53。右图二叉排序树为(7+9)*1+(3+4)*2+(2+2+1)*3=45。
构造方法
当问题比较复杂时，可能无法直接得到所需的结果。针对这种情况，人们提出的一种技术是逐步推进，在每步计算中根据已知的信息做一些选择，得到一些局部结果，这样积累了信息，也为下一步计算做好准备。这种工作方式称为动态规划。Dijkstra算法就是一个典型应用。
步骤
一般步骤m > 1：
计算带权路径长度
在构造一棵二叉排序树时，其带权路径长度可以基于其两棵子树的带权路径长度计算出来。
带权问题还没有搞清楚。。？？
8.7 平衡二叉树
最佳二叉排序树，可以保证最佳的检索效率，但其缺点也很明显。构造这种结构需要掌握所有元素的分布情况。而且，这种树只适合作为静态字典的表示，不能很好地支持动态操作而产生的动态变化。
由于“最佳”是一种全局性质，无法从局部把握和检查，一旦破坏，也难以通过局部调整恢复。实际应用中希望既能维持高效检索，又能支持动态操作，于是只能摒弃对最佳的追求，设法在操作中维持某种“较佳”的结构，换取动态操作中较容易进行局部维护。平衡二叉树就是这样一种方法。
8.7.1 定义和性质
平衡二叉排序树是一类特殊的二叉排序树，它或者为空树，或者其左右子树都是平衡二叉排序树(递归结构)，而且其左右子树的高度之差的绝对值不超过1。
易见，平衡是一种局部性质，有可能通过局部信息描述。整棵树的平衡由各结点的平衡情况刻画，各结点的平衡可以用一个简单的平衡因子(Balance Factor, BF)描述。BF定义为该结点的左子树高度减去右子树高度之差，可能取值为-1、0、1。在平衡二叉树的结点里并不记录其左右子树的高度，只记录BF的值。
显然，完全二叉树和等概率情况的最佳二叉排序树都是平衡二叉树。
现在考虑各种高度最高的“临界”平衡二叉树。
可以看出，这些树结构都是递归的。i > 1(i从0开始)时树Bi 总是以Bi-1和Bi-2作为子树，再加上一个根结点构成。有如下递推公式：
很像斐波那契数列的递推公式，
通过归纳法得到#Bi = Fi+3 - 1。由于
这个没推出来？？
也就是说，与最佳二叉排序树相比，最长路径的长度仅差一个常量因子。
8.7.2 AVL树类
二叉排序树上的检索，时间代价的最坏情况受限于树中最长路径的长度。如果能够维持平衡二叉树的结构，检索操作就能在O(logn)时间内完成。
剩下的问题就是如何让树结构在动态变化中维持平衡。在插入和删除时，不但要保持树的结构和树中结点关键码的正确排序，还需要维持树的平衡。要保证操作的时间代价为O(logn)，结构调整必须是局部的，只在一条路径上调整。
8.7.3 插入操作
插入后的失衡和调整
如果在检索插入位置的过程中，所有途径结点的BF值均为0，那么实际插入结点不会导致这些结点失衡，只是它们(所有途径结点)的BF值应修改为1或-1。
如果不是所有途径结点的BF值均为0，那么一定存在一棵包含新结点插入点的最小平衡子树(其根结点的BF值非0的最小子树)。如果插入新结点后这棵子树仍保持平衡，而且其高度不变，那么整棵二叉排序树也将保持平衡(由于该子树的高度不变，在它外面的树结点BF值都保持不变)。进一步说，如果插入新结点后的结构调整和BF值修改都能在该子树内部的一条路径上完成，插入操作的复杂度将不超过O(logn)。
假设插入结点所在的最小非平衡子树的根结点为a，其左子树较高。
1）如果插入点在a的右子树(较低的子树)，插入结点后只需调整结点a之下直至插入点的路径上的所有结点的BF值(除结点a外，其他结点的bf值都为0，最小非平衡子树就是这么选择的)，并将a的bf值修改为0。由于以a为根的子树高度不变，插入和调整对其他部分没有影响，整个树保持平衡，插入操作完成。
2）如果新结点应插入在a的左子树(较高子树)，就会破坏a的平衡，这种情况下必须设法恢复结点a的平衡。从较高子树调整结点到另一子树，降低其高度，就能恢复a的平衡。分四种情况处理：
RR对应LL，RL对应LR，分别插入在a的子树的外侧和内侧。下面讨论只需关心以a为根的子树，整棵树的其他部分没有任何变化。
外侧，LL为顺时针旋转，RR为逆时针旋转
内侧，
这里有一个特殊情况，即插入前b为叶子结点，c就是新插入的结点。这种情况也是将c作为结果子树的根，b和a作为其左右子结点。
LR代码，
RL代码，
插入操作示例
总结和分析
发现失衡后只需在最小不“平衡”子树的根结点附近做局部调整，就能把该子树根的平衡因子变成0，而且保证这棵子树的高度与插入前相同(即对子树之外的其他部分没有影响)。另外，所做的调整不会改变树中数据的排序序列。
插入算法的操作分成几个阶段：首先找到插入位置并实际插入新结点，然后可能需要修改一些结点的平衡因子，发现失衡时做些局部调整。这里所有操作都是在树中的同一条路径上进行的，所以AVL树插入操作的代价为O(logn)。
插入操作的实现
。。。
8.8 动态多分支排序树
8.8.1 多分支排序树
现在考虑用一般树实现字典。为了保证高效率的检索，必须采用某种排序树结构，使检索能沿着树中路径进行。这里还有一个问题：在一般树结构中结点的度数没有限制，不利于计算机实现。为了实现方便，采用统一规模的结点，而一旦确定了结点规模，也就决定了树结点的最大分支数。
在多分支排序树中，一个结点里可能存储多个关键码，需要维持这些关键码和相应子树关键码的排序关系。图8.20描绘了一个包含四棵子树的根结点，为了保证检索效率，结点里的关键码必须能为检索导航。图中结点包含3个关键码，它们将可能关键码空间划分为4段，各子树里的关键码应分别在这4段里取值。这样，比较检索关键码与结点里的关键码，就可以决定进入哪棵子树继续检索。
从全局的角度看，树中检索同样沿着从根开始的一条路径进行，但在每个结点里还需要做一次顺序表检索，找出正确的下行分支。
控制多分枝排序树结构的一种重要技术是控制结点的分支数，限制它们只能在一定范围内变动。多分支排序树通常采用统一大小的结点，例如确定结点最大分支数为m>2。为保证结点中存储空间的利用率，还需要规定结点的最小分支数m' >= 2。允许具体结点的分支数(子树个数)在这两个值的范围内变化。
采用多分支排序树实现字典，同样需要控制最长路径的长度。二叉树中分支结点的度数只能为1或2。多分支树中允许更多分支，灵活性更强，存在更多控制树中路径长度的方法。
与二叉排序树相比，调整多分支排序树结构的手段更多。例如：
多分树结构的共性特征是在动态操作中，始终保持从根到所有叶子结点的路径长度完全相同。这样，只要保证每个分支节点至少有两个分支，在n个结点的树里，路径长度就不会超过O(logn)，因此可以保证检索的效率。
还有B树和B+树。。。