二叉搜索树

二叉搜索树

在ADT Map的实现方案中，可以采用不同的数据结构和搜索算法来保存和查找Key，
已经实现了两个方案

• 有序表数据结构+二分搜索算法
• 散列表数据结构+散列及冲突解决算法
  用二叉查找树保存key，实现key的快速搜索
  复习一下ADT Map的操作：
• Map()：创建一个空映射
• put(key, val)：将key-val关联对加入映射中，如果key已经存在，则将val替换旧关联值；
• get(key)：给定key，返回关联的数据值，如不存在，则返回None；
• del：通过del map[key]的语句形式从映射中删除键–值对；
• len()：返回映射中key-val的数目；
• in：通过key in map的语句形式，返回key是否存在，返回布尔值

二叉搜索树的性质：比父节点小的key都出现在左子树，比父节点大的key都出现在右子树

二叉搜索树的实现

需要用到BST和TreeNode两个类，BST的root成员引用根节点TreeNode

class BinarySearchTree:

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

    def length(self):
        return self.size

    def __len__(self):
        return self.size

我们可以用for循环枚举字典中的所有key，ADT Map也应该实现这样的迭代器功能，特殊方法iter可以用来实现for迭代，BST类中的iter方法直接调用了TreeNode中的同名方法

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

put(key, val)方法：插入key构造BST，首先看BST是否为空，如果一个节点都没有，那么key成为根节点root，否则，就调用一个递归函数_put(key, val, root)来放置key

    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

_put(key, val, currentNode)的流程
如果key比currentNode小，那么_put到左子树
• 但如果没有左子树，那么key就成为左子节点
如果key比currentNode大，那么_put到右子树
• 但如果没有右子树，那么key就成为右子节点

    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, key, value):
        self.put(key, value)

get方法：在树中找到key所在的节点取到payload

    def get(self, key):
        if self.root:
            res = self._get(key, self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            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

用_get找到要删除的节点，然后调用remove来删除，找不到则提示错误

    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方法
从BST中remove一个节点，还要求仍然保持BST的性质，分以下3种情形：
1.这个节点没有子节点

    def remove(self, currentNode):
        # 没有子节点，直接删除
        if currentNode.isLeaf(): 
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None

2.这个节点有2个子节点
被删节点有2个子节点，这时无法简单地将某个子节点上移替换被删节点，但可以找到另一个合适的节点来替换被删节点，这个合适节点就是被删节点的下一个key值节点，即被删节点右子树中最小的那个，称为“后继”，可以肯定这个后继节点最多只有1个子节点（本身是叶节点，或仅有右子树），将这个后继节点摘出来（也就是删除了），替换掉被删节点。

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

3.这个节点有1个子节点
被删节点有一个子节点，解决：将这个唯一的子节点上移，替换掉被删节点的位置，被删节点的子节点是左？还是右子节点？被删节点本身是其父节点的左？还是右子节点？被删节点本身就是根节点？

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

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.leftChild and self.rightChild

    def replaceNodeDate(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
    # 摘出节点
    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:
                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

    '''
    迭代器函数中用了for迭代，实际上是递归函数
    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
if __name__ == '__main__':
    tree = BinarySearchTree()
    tree[66]='zhangsan'
    tree[33] = 'lisi'
    tree[55] = 'ddd'
    tree[18] = 'wangwu'
    tree[99] = 'hanh'

    tree.delete(33)

    for key in tree:
        print(key)

算法分析（以put为例）

其性能决定因素在于二叉搜索树的高度（最大层次），而其高度又受数据项key
插入顺序的影响。如果key的列表是随机分布的话，那么大于和小于根节点key的键值大致相等
BST的高度就是log2n（n是节点的个数），而且，这样的树就是平衡树
put方法最差性能为O(log2n)。
但key列表分布极端情况就完全不同，按照从小到大顺序插入的话，如下图
这时候put方法的性能为O(n)其它方法也是类似情况

image.png