二叉搜索树

我们需要学习如何利用二叉树结构提供高效的搜索。

搜索树的操作

搜索树的接口类似于 Python 字典。

Map() 新建一个空的映射。
put(key, val) 往映射中加入一个新的键–值对。如果键已经存在，就用新值替换旧值。
get(key) 返回 key 对应的值。如果 key 不存在，则返回 None。
del 通过 del map[key]这样的语句从映射中删除键–值对。
len() 返回映射中存储的键–值对的数目。
in 通过 key in map 这样的语句，在键存在时返回 True，否则返回 False。

搜索树的实现

二叉搜索树依赖于这样一个性质：小于父节点的键都在左子树中，大于父节点的键则都在右子树中。我们称这个性质为二叉搜索性，它会引导我们实现上述映射接口。

我们将采用“节点与引用”表示法实现二叉搜索树，它类似于我们在实现链表和表达式树时采用的方法。不过，由于必须创建并处理一棵空的二叉搜索树，因此我们将使用两个类。一个称作 BinarySearchTree，另一个称作 TreeNode。BinarySearchTree 类有一个引用，指向作为二叉搜索树根节点的 TreeNode 类。大多数情况下，外面这个类的方法只是检查树是否为空。如果树中有节点，请求就被发往 BinarySearchTree 类的私有方法，这个方法以根节点作为参数。当树为空，或者想删除根节点的键时，需要采取特殊措施。

BinarySearchTree 类：

class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

TreeNode 类：

class TreeNode:
   def __init__(self,key,val,left=None,right=None,
                                       parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self

接下来写一个帮我们构建二叉搜索树的 put 方法了。put 是 BinarySearchTree 类的一个方法。它检查树是否已经有根节点，若没有，就创建一个 TreeNode，并将其作为树的根节点；若有，就调用私有的递归辅助函数_put，并根据以下算法在树中搜索：

从根节点开始搜索二叉树，比较新键与当前节点的键。如果新键更小，搜索左子树。如果新键更大，搜索右子树。
当没有可供搜索的左（右）子节点时，就说明找到了新键的插入位置。
向树中插入一个节点，做法是创建一个 TreeNode 对象，并将其插入到前一步发现的位置上。

为二叉搜索树插入新节点：

def put(self,key,val):
    if self.root:
        self._put(key,val,self.root)
    else:
        self.root = TreeNode(key,val)
    self.size = self.size + 1

def _put(self,key,val,currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild():
               self._put(key,val,currentNode.leftChild)
        else:
               currentNode.leftChild = TreeNode(key,val,parent=currentNode)
    else:
        if currentNode.hasRightChild():
               self._put(key,val,currentNode.rightChild)
        else:
               currentNode.rightChild = TreeNode(key,val,parent=currentNode)

插入方法有个重要的问题：不能正确地处理重复的键。遇到重复的键时，它会在已有节点的右子树中创建一个具有同样键的节点。这样做的结果就是搜索时永远发现不了较新的键。

定义 put 方法后，就可以方便地通过让 __setitem__ 方法调用 put 方法来重载[]运算符。

__setitem__ 方法：

def __setitem__(self,k,v):
    self.put(k,v)

构造出树后，下一个任务就是实现为给定的键取值。 get 方法比 put 方法还要简单，因为它只是递归地搜索二叉树，直到访问到叶子节点或者找到匹配的键。在后一种情况下，它会返回节点中存储的值。

查找键对应的值：

def get(self,key):
    if self.root:
        res = self._get(key,self.root)
        if res:
               return res.payload
        else:
               return None
    else:
        return None

def _get(self,key,currentNode):
    if not currentNode:
        return None
    elif currentNode.key == key:
        return currentNode
    elif key < currentNode.key:
        return self._get(key,currentNode.leftChild)
    else:
        return self._get(key,currentNode.rightChild)

def __getitem__(self,key):
    return self.get(key)

检查树中是否有某个键：

def __contains__(self,key):
    if self._get(key,self.root):
        return True
    else:
        return False

__contains__方法重载了 in 运算符，因此我们可以写出这样的语句：
if 'Northfield' in myZipTree:
    print("oom ya ya")

接下来，我们要构造一个方法删除一个键。第一个任务是在树中搜索并找到要删除的节点。如果树中不止一个节点，使用 _get 方法搜索，找到要移除的 TreeNode。如果树中只有一个节点，则意味着要移除的是根节点，不过仍要确保根节点的键就是要删除的键。无论哪种情况，如果找不到要删除的键，delete 方法都会抛出一个异常。

def delete(self,key):
   if self.size > 1:
      nodeToRemove = self._get(key,self.root)
      if nodeToRemove:
          self.remove(nodeToRemove)
          self.size = self.size-1
      else:
          raise KeyError('Error, key not in tree')
   elif self.size == 1 and self.root.key == key:
      self.root = None
      self.size = self.size - 1
   else:
      raise KeyError('Error, key not in tree')

def __delitem__(self,key):
    self.delete(key)

接下来构造 remove 方法。一旦找到待删除键对应的节点，就必须考虑 3 种情况：

待删除节点没有子节点。
待删除节点只有一个子节点。
待删除节点有两个子节点。

情况 1：待删除节点没有子节点：

if currentNode.isLeaf():
    if currentNode == currentNode.parent.leftChild:
        currentNode.parent.leftChild = None
    else:
        currentNode.parent.rightChild = None

情况 2：待删除节点只有一个子节点：

我们需要考虑了 6 种情况。由于左右子节点的情况是对称的，因此只需要讨论当前节点有左子节点的情况。

如果当前节点是一个左子节点，只需将当前节点的左子节点对父节点的引用改为指向当前节点的父节点，然后将父节点对当前节点的引用改为指向当前节点的左子节点。
如果当前节点是一个右子节点，只需将当前节点的右子节点对父节点的引用改为指向当前节点的父节点，然后将父节点对当前节点的引用改为指向当前节点的右子节点。
如果当前节点没有父节点，那它肯定是根节点。调用 replaceNodeData 方法，替换根节点的 key、 payload、 leftChild 和 rightChild 数据。

else: # this node has one child
    if currentNode.hasLeftChild():
        if currentNode.isLeftChild():
            currentNode.leftChild.parent = currentNode.parent
            currentNode.parent.leftChild = currentNode.leftChild
        elif currentNode.isRightChild():
            currentNode.leftChild.parent = currentNode.parent
            currentNode.parent.rightChild = currentNode.leftChild
        else:
            currentNode.replaceNodeData(currentNode.leftChild.key,
                               currentNode.leftChild.payload,
                               currentNode.leftChild.leftChild,
                               currentNode.leftChild.rightChild)
    else:
        if currentNode.isLeftChild():
            currentNode.rightChild.parent = currentNode.parent
            currentNode.parent.leftChild = currentNode.rightChild
        elif currentNode.isRightChild():
            currentNode.rightChild.parent = currentNode.parent
            currentNode.parent.rightChild = currentNode.rightChild
        else:
            currentNode.replaceNodeData(currentNode.rightChild.key,
                               currentNode.rightChild.payload,
                               currentNode.rightChild.leftChild,
                               currentNode.rightChild.rightChild)

情况 3：待删除节点有两个子节点：

如果一个节点有两个子节点，那就不太可能仅靠用其中一个子节点取代它来解决问题。不过，可以搜索整棵树，找到可以替换待删除节点的节点。候选节点要能为左右子树都保持二叉搜索树的关系，也就是树中具有次大键的节点。我们将这个节点称为后继节点，有一种方法能快速找到它。后继节点的子节点必定不会多于一个，所以我们知道如何按照已实现的两种删除方法来移除它。移除后继节点后，只需直接将它放到树中待删除节点的位置上即可。

elif currentNode.hasBothChildren(): #interior
    succ = currentNode.findSuccessor()
    succ.spliceOut()
    currentNode.key = succ.key
    currentNode.payload = succ.payload

我们用辅助函数 findSuccessor 和 findMin 来寻找后继节点，并用 spliceOut 方法移除它。因为 spliceOut 方法可以直接访问待拼接的节点，并进行正确的修改。虽然也可以递归调用 delete，但那样做会浪费时间重复搜索键的节点。

寻找后继节点：

我们利用二叉搜索树属性，中序遍历从小到大打印出树节点。在查找后继节点时，要考虑以下 3 种情况：

如果节点有右子节点，那么后继节点就是右子树中最小的节点。
如果节点没有右子节点，并且其本身是父节点的左子节点，那么后继节点就是父节点。
如果节点是父节点的右子节点，并且其本身没有右子节点，那么后继节点就是除其本身外父节点的后继节点。

def findSuccessor(self):
    succ = None
    if self.hasRightChild():
        succ = self.rightChild.findMin()
    else:
        if self.parent:
            if self.isLeftChild():
                succ = self.parent
            else:
                self.parent.rightChild = None
                succ = self.parent.findSuccessor()
                self.parent.rightChild = self
    return succ

def findMin(self):
    current = self
    while current.hasLeftChild():
        current = current.leftChild
    return current

def spliceOut(self):
    if self.isLeaf():
        if self.isLeftChild():
            self.parent.leftChild = None
        else:
            self.parent.rightChild = None
    elif self.hasAnyChildren():
        if self.hasLeftChild():
            if self.isLeftChild():
                self.parent.leftChild = self.leftChild
            else:
                self.parent.rightChild = self.leftChild
            self.leftChild.parent = self.parent
        else:
            if self.isLeftChild():
                self.parent.leftChild = self.rightChild
            else:
                self.parent.rightChild = self.rightChild
            self.rightChild.parent = self.parent

findMin 方法用来查找子树中最小的键。可以确定，在任意二叉搜索树中，最小的键就是最左边的子节点。鉴于此， findMin 方法只需沿着子树中每个节点的 leftChild 引用走，直到遇到一个没有左子节点的节点。

二叉搜索树迭代器：

Python 为创建迭代器提供了一个很强大的函数，即 yield。与 return 类似， yield 每次向调用方返回一个值。除此之外， yield 还会冻结函数的状态，因此下次调用函数时，会从这次离开之处继续。创建可迭代对象的函数被称作生成器。

def __iter__(self):
   if self:
      if self.hasLeftChild():
             for elem in self.leftChiLd:
                yield elem
      yield self.key
      if self.hasRightChild():
             for elem in self.rightChild:
                yield elem

乍看之下，你可能会认为它不是递归的。但是，因为 __iter__ 重载了循环的 for x in 操作，所以它真的是递归的！由于在 TreeNode 实例上递归，因此 __iter__ 方法被定义在 TreeNode 类中。

`BinarySearchTree` 和 `TreeNodeo` 完整版本

下面是 BinarySearchTree 和 TreeNodeo 两个类的完整版本：

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def spliceOut(self):
        if self.isLeaf():
            if self.isLeftChild():
                self.parent.leftChild = None
            else:
                self.parent.rightChild = None
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                if self.isLeftChild():
                    self.parent.leftChild = self.leftChild
                else:
                    self.parent.rightChild = self.leftChild
                self.leftChild.parent = self.parent
            else:
                if self.isLeftChild():
                    self.parent.leftChild = self.rightChild
                else:
                    self.parent.rightChild = self.rightChild
                self.rightChild.parent = self.parent

    def findSuccessor(self):
        succ = None
        if self.hasRightChild():
            succ = self.rightChild.findMin()
        else:
            if self.parent:
                   if self.isLeftChild():
                       succ = self.parent
                   else:
                       self.parent.rightChild = None
                       succ = self.parent.findSuccessor()
                       self.parent.rightChild = self
        return succ

    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self


class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                   self._put(key,val,currentNode.leftChild)
            else:
                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)
        else:
            if currentNode.hasRightChild():
                   self._put(key,val,currentNode.rightChild)
            else:
                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)

    def __setitem__(self,k,v):
       self.put(k,v)

    def get(self,key):
       if self.root:
           res = self._get(key,self.root)
           if res:
                  return res.payload
           else:
                  return None
       else:
           return None

    def _get(self,key,currentNode):
       if not currentNode:
           return None
       elif currentNode.key == key:
           return currentNode
       elif key < currentNode.key:
           return self._get(key,currentNode.leftChild)
       else:
           return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
       return self.get(key)

    def __contains__(self,key):
       if self._get(key,self.root):
           return True
       else:
           return False

    def delete(self,key):
      if self.size > 1:
         nodeToRemove = self._get(key,self.root)
         if nodeToRemove:
             self.remove(nodeToRemove)
             self.size = self.size-1
         else:
             raise KeyError('Error, key not in tree')
      elif self.size == 1 and self.root.key == key:
         self.root = None
         self.size = self.size - 1
      else:
         raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
       self.delete(key)

    def remove(self,currentNode):
         if currentNode.isLeaf(): #leaf
           if currentNode == currentNode.parent.leftChild:
               currentNode.parent.leftChild = None
           else:
               currentNode.parent.rightChild = None
         elif currentNode.hasBothChildren(): #interior
           succ = currentNode.findSuccessor()
           succ.spliceOut()
           currentNode.key = succ.key
           currentNode.payload = succ.payload

         else: # this node has one child
           if currentNode.hasLeftChild():
             if currentNode.isLeftChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.leftChild
             elif currentNode.isRightChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.leftChild
             else:
                 currentNode.replaceNodeData(currentNode.leftChild.key,
                                    currentNode.leftChild.payload,
                                    currentNode.leftChild.leftChild,
                                    currentNode.leftChild.rightChild)
           else:
             if currentNode.isLeftChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.rightChild
             elif currentNode.isRightChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.rightChild
             else:
                 currentNode.replaceNodeData(currentNode.rightChild.key,
                                    currentNode.rightChild.payload,
                                    currentNode.rightChild.leftChild,
                                    currentNode.rightChild.rightChild)




mytree = BinarySearchTree()
mytree[3]="red"
mytree[4]="blue"
mytree[6]="yellow"
mytree[2]="at"

print(mytree[6])
print(mytree[2])

搜索树的分析

至此，我们已经完整地实现了二叉搜索树，接下来简单地分析它的各个方法。先分析 put 方法，限制其性能的因素是二叉树的高度，而树的高度是其中节点层数的最大值。高度之所以是限制因素，是因为在搜索合适的插入位置时，每一层最多需要做一次比较。

那么，二叉树的高度是多少呢？答案取决于键的插入方式。如果键的插入顺序是随机的，那么树的高度约为 $\log_2{n}$ ，其中 $n$ 为树的节点数。这是因为，若键是随机分布的，那么小于和大于根节点的键大约各占一半。二叉树的顶层有 1 个根节点，第 1 层有 2 个节点，第 2 层有 4 个节点，依此类推。在完全平衡的二叉树中，节点总数是 $2^{h+1}-1$，其中 $h$ 代表树的高度。

在完全平衡的二叉树中，左右子树的节点数相同。最坏情况下， put 的时间复杂度是 $O(\log_2{n})$，其中 n 是树的节点数。注意，这是上一段所述运算的逆运算。所以，$\log_2{n}$ 是树的高度，代表 put 在搜索合适的插入位置时所需的最大比较次数。

不幸的是，按顺序插入键可以构造出一棵高度为 n 的搜索树！下图就是一个例子，这时 put 方法的时间复杂度为 $O(n)$。

get 在树中查找键，最坏情况就是沿着树一直搜到底也没找到。乍看之下， del 可能更复杂，因为在删除节点前可能还得找到后继节点。但是查找后继节点的最坏情况也受限于树的高度，也就是把工作量加一倍。所以，对于不平衡的树来说，最坏情况下的时间复杂度仍是 $O(n)$。

文章目录

二叉搜索树

[Python] 树 - 二叉搜索树

二叉搜索树

搜索树的操作

搜索树的实现

`BinarySearchTree` 和 `TreeNodeo` 完整版本

搜索树的分析

评论已关闭

最新文章

最近回复

分类

标签

归档

其它

[Python] 树 - 二叉搜索树

二叉搜索树

搜索树的操作

搜索树的实现

BinarySearchTree 和 TreeNodeo 完整版本

搜索树的分析

评论已关闭

最新文章

最近回复

分类

标签

归档

其它

`BinarySearchTree` 和 `TreeNodeo` 完整版本