00
前言在初步了解了“树”之后，上一篇推文《Python数据结构——树(二)》又介绍了一类比较特殊的树——二叉树。延续上一篇推文的内容，本文将继续介绍二叉树，不过和上一篇推文中有所不同的是，这次介绍的二叉树的结点之间存在一定的规则，而且结点不能够插入到任意指定位置。
本文将介绍的是二叉树中的二叉搜索树(BinarySearchTree)，也称二叉排序树(BinarySortTree)，这种树构建完成后，在查找上会十分便捷，而且对其进行中序遍历的结果恰好是按结点关键字升序排列的。
01
二叉搜索树先看下百度百科的词条解释。
总结定义如下：
若左子树不为空，则左子树上所有结点的值都小于根结点的值。
若右子树不为空，则右子树上所有结点的值都大于根结点的值。
左、右子树都是二叉搜索树。
第三条与我们前面对树、二叉树的定义类似，都是采用了递归定义。
直接放一张示意图，便于理解二叉搜索树。
结点上的数字对应我们之前代码中使用的属性key，如果对上一篇推文的中序遍历示意图还有印象的话，就能发现二叉搜索树的中序遍历结果，是按照key进行升序排列的。
如果对二叉树仍有理解不到位之处，可以参考《Python数据结构——树(二)》，本文默认在上述内容已经了解的情况下介绍二叉搜索树。
02
BST代码实现二叉搜索树直接看示意图与概念就能理解，不做过多解释，直接进入代码实现部分。
代码按照惯例，先实现结点类，再实现树类。
BSTNode类代码如下：
classBSTNode(object):def__init__(self,key,value=None,parent=None,left=None,right=None):self.key=keyself.value=valueself.parent=parentself.left=leftself.right=rightdefhasLeft(self):"""检查当前结点是否有左子结点"""returnself.leftisnotNonedefhasRight(self):"""检查当前结点是否有右子结点"""returnself.rightisnotNonedefisLeft(self):"""检查当前结点是否为其双亲结点的左子结点"""returnself.parentisnotNoneandself.keyself.parent.keydefisRight(self):"""检查当前结点是否为其双亲结点的右子结点"""returnself.parentisnotNoneandself.keyself.parent.key
代码与此前实现的BinaryTreeNode类完全一致，只是改了个类名而已，代码很简单，只简单说一下几个语法的含义：None对应了其他语言中的NULL或null等；is是Python用于判断两个对象是否相同的方法，不仅比较值，还比较地址。
而且我们是按照key的大小，有规律的插入新结点的，但是结点可以存储的内容不只是key，例如创建一棵存储某班级同学考试成绩的二叉搜索树，结点key就可以是成绩，value就可以存储对应的学生姓名。
BinarySearchTree类先初始化
classBinarySearchTree(object):def__init__(self,key,value=None):self.root=BSTNode(key,value)
这样一棵树可以被称为“搜索树”的原因在于它的查找速度可以很快，最优应当是O(logN)，它的查找也和二分查找有类似之处，当然也有不同，最大的不同就是这里是在一棵树上根据关键字进行查找，而且性能不一定是最佳的，这个之后再解释。
所以就目前的了解来看，这个类的方法就应该包括了增加、删除、查找这三类，至于其他的方法，最后再补充。
前面列举的存储一个班级同学的成绩，这里有一个问题需要考虑，如果两名或多名同学的成绩分数相同，value该怎么进行存储呢？一种方法是改用列表存储多名学生的姓名。但在本文中遇到key相同时，直接将value替换成新的value，不考虑存储多个值，此时的插入方法也就兼顾了修改的功能。
插入方法代码实现如下：
definsert(self,key,value=None,cur=None):"""插入一个关键字为key值为value的结点"""ifcurisNone:#首次调用初始化当前结点为根结点cur=self.root#比较关键字ifkeycur.key:#小于，向左走ifcur.hasLeft():#有左支，继续向左走self.insert(key,value,cur.left)else:#无左支，直接作为当前结点的左支插入node=BSTNode(key,value)node.parent=curcur.left=nodeelifkeycur.key:#大于，向右走ifcur.hasRight():#有右支，继续向右走self.insert(key,value,cur.right)else:#无右支，直接作为当前结点的右支插入node=BSTNode(key,value)node.parent=curcur.right=nodeelse:#相等，更新valuecur.value=value
代码思路很简单，从根结点开始比较key，如果小于，则向左走，如果大于则向右走，最终必然走到叶子结点的位置，新结点就作为叶子结点挂在该处。若相等，则修改value的内容。
示意图如下：
在介绍删除方法之前，先介绍下查找，查找比较简单，从根结点开始比较key，小于向左走，大于向右走，直到查找成功或到达叶子结点底下的None。
代码如下：
deffindNode(self,key):"""查找并返回关键字为key的结点"""cur=self.root#未找到关键字为key的结点，且当前结点不为空whilecurisnotNoneandkey!=cur.key:ifkeycur.key:#向左走cur=cur.leftelse:#向右走cur=cur.rightifcurisNone:raiseException("未找到关键字为%s的结点"%str(key))returncur
查找每次都是只向一侧走，另外一侧完全不用再考虑，因此能够提升查找的效率。
删除方法就比较麻烦了，之前我们在二叉树中删除一个结点考虑了三种情况，分别是删除叶子结点，删除含有左/右单支的结点，删除含有左右双支的结点。在BST中也需要考虑这三种情况。
删除叶子结点：直接删除，最简单。
删除含有左/右单支的结点：将该结点的子树交由双亲结点管理。
删除含有左右双支的结点：取出右子树最小值替换掉待删除结点，删除右子树最小值结点。
只有删除含有左右双支的结点这里与前面的处理方法不同，前面是直接取右子树最后一个结点替换，但在BST中不能这样，我们需要确保删除某结点后的树仍然是BST。
这里我们选用的是取右子树中的最小值替换待删除结点，替换后，依然满足左侧所有结点的key小于子树根结点的key，右侧所有结点的key大于子树根结点的key。如果采用左子树最大值替换待删除结点也是一样的。
在删除方法之前先实现查找最大值或查找最小值的方法，便于后续调用。这里说的最小值最大值是指属性key。
deffindMin(self,node):"""查找以node结点为根结点子树中关键字最小的结点"""ifnode.hasLeft():#左侧还有更小的关键字，向左走returnself.findMin(node.left)else:returnnodedeffindMax(self,node):"""查找以node结点为根结点的子树中关键字最大的结点"""ifnode.hasRight():returnself.findMax(node.right)else:returnnode
另外，删除之前还要确认是否有这个结点，所以删除之前先调用查找方法。
直接放上代码，对照代码理解过程，不用一次性看懂所有步骤，可以将三种情况分成三部分慢慢理解。
具体删除方法的代码如下：
defremove(self,key):"""删除关键字等于key的结点"""node=self.findNode(key)#先查找关键字为key的结点，找不到会抛异常ifnode.hasLeft()andnode.hasRight():#待删除结点有左右双支minOfRight=self.findMin(node.right)#查找到右子树中关键字最小的结点self.remove(minOfRight.key)#找到的结点必然是叶子结点或者只有右单支，不会进入递归死循环node.key=minOfRight.keynode.value=minOfRight.valueelifnode.hasLeft()ornode.hasRight():#待删除结点有左/右单支ifnodeisself.root:#根结点self.root=node.leftifnode.hasLeft()elsenode.right#设置新的根结点self.root.parent=Noneelse:#普通的内部结点child=node.leftifnode.hasLeft()elsenode.right#获取该结点的子结点child.parent=node.parentifnode.isLeft():node.parent.left=childelse:node.parent.right=childnode.parent=Noneelse:#待删除结点为叶子结点ifnodeisself.root:#待删除结点为根结点self.root=Noneelse:#叶子结点直接删除ifnode.isLeft():node.parent.left=Noneelse:node.parent.right=Nonenode.parent=None
比较难理解的可能是删除含有双支的结点中再次调用了remove方法这一步，这里并不会形成无限递归的情况，因为此处删除的minOfRight这个结点是右侧的最小值结点，必然不含有左支(因为左支一定会更小)，所以这个结点只能是叶子或者只含有右单支，再次进入remove方法时不会进入到第一个if语句内，也就不存在无限递归。
另外，由于使用右侧最小值结点覆盖待删除结点，所以步骤应当如下：
使用一个变量记录下最小值结点。
从树中删除最小值结点。
使用变量中存储的最小值结点替换掉待删除结点。
第二步的删除只是从树中无法再根据存储的引用找到这个结点，这个结点实际上还是存在的，被存储在了变量中而已。而且上述三个步骤不能交换顺序，必须先删除再替换，如果先替换再删除，由于删除是根据key进行的，此时树中存在两个相同的key，会出现误删的情况。
删除含有左右双支的结点示意图如下：
增删查都已经介绍过了，修改的方法也隐含在插入方法里面了，接下来补充点新的内容——前驱和后继。
以下图为例：
key=0的结点，它的后继是比它的key值大的下一个结点，就应当是key=2的结点，至于其他结点，虽然其他结点的key也都大于0，但它们并不是“下一个结点”，即从所有结点升序的排列结果来看不是恰好为下一个。由此也可以得出key=5的结点后继应当是key=6的结点。其他也同理可得。
而前驱就应当是降序排列情况下，比它的key要小的下一个结点。
我们能够在看到这些数字之后，在大脑内快速的给它们排好序，但是我们的程序该如何去找到前驱与后继呢？先对所有结点的key进行一次排序吗？当然不用，找前驱和后继可以利用二叉查找树的特点来进行。
先看下如何找某结点的后继。
先确认这个结点在树当中。
如果该结点有右子树，后继则为右子树最小值结点。
否则向上找到某个是左支的祖先结点，返回该祖先结点的双亲结点。
确认结点存在于树中可以用查找方法，这个不难。
而在有右子树的情况下，为什么后继一定是右子树最小值结点呢？根据BST的特点，我们可以知道右子树中任意一个结点的key都是大于我们当前已知的这个子树根结点的，而从大于它的所有结点中找的最小的一个结点，必然是在升序序列中最接近我们已知结点的，即恰好为“下一个结点”。
没有右子树呢？为什么向上找到某个是左支的祖先，返回该祖先结点的双亲结点？向上找到某祖先结点为左支，即isLeft()方法返回True，如果isLeft()为False，说明其位于双亲结点右侧，必然大于其双亲结点与双亲结点的左侧，只能继续向上找，直到最终确认了是属于某子树的左分支，那么这个子树的根就是它的后继，即某个是左支的祖先结点的双亲结点，是它的后继。
查找后继结点的代码如下：
defsuccessor(self,key):"""查找并返回关键字为key的结点的后继"""node=self.findNode(key)#先确保存在这一个结点ifnode.hasRight():#有右子树，后继为右子树中关键字最小的结点returnself.findMin(node.right)else:#存在双亲结点，且当前结点为右子，向上查找whilenode.parentisnotNoneandnode.isRight():node=node.parentreturnnode.parent#返回该祖先结点的双亲结点，若返回为None，则未找到
对照代码理解比较容易，代码中用isRight()方法代替了notisLeft()这一句。
相应的，前驱结点的查找思路与代码如下：
先确认是否存在该结点
若该结点有左子树，则前驱为左子树最大值结点。
否则向上找到某个为右支的祖先结点，返回该祖先结点的双亲结点。
代码如下：
defprecursor(self,key):"""查找并返回关键字为key的结点的前驱"""node=self.findNode(key)#先确保存在这一个结点ifnode.hasLeft():returnself.findMax(node.left)else:#存在双亲结点，且当前结点为左子，向上查找whilenode.parentisnotNoneandnode.isLeft():node=node.parentreturnnode.parent#返回该祖先结点的双亲结点或None
需要注意的是，二叉搜索树中，key值最小的结点没有前驱，key值最大的结点没有后继。
关于二叉查找树的一些内容及一些基本的方法与代码实现，暂时先介绍到这里，而在最后，留下一个小的疑问，具体解答将在下一篇推文给出。
如果插入的数值本身是已经排序好的，查找的时间复杂度又回到了O(N)，并没有体现BST在查找上的优点，该如何解决这个问题呢？
在最后Lastbutnotleast
本文主要在上一篇推文的基础上介绍二叉搜索树，主要介绍二叉搜索树中的插入、删除与查找，修改方法也放到了插入方法里面，最后补充了前驱与后继的求解。总的来说都不是很难实现，但只是阅读代码的话对学习的帮助还是有限，需要多写代码，勤于练习。
文末也提出了关于二叉搜索树所有子树都只有一个分支时，查找方法的时间复杂度会退化到O(N)的问题，具体如何解决这个问题，留待下一篇推文再介绍。
往期精彩回顾Python数据结构——栈与队列例题
Python数据结构——树(一)
Python数据结构——树(二)
预览时标签不可点收录于话题#个上一篇下一篇