二叉搜索树

二叉搜索树BST(BinarySearchTree)

BST是一棵二叉树有着如下特点：

所有小于父节点的节点都在左子树中，大于父节点的节点都在右子树中。

bst.jpg

这里的比较是指key键之间的行为，这样就可以将BST描述成是一种ADT MAP(映射抽象数据结构)。

MAP类通用的数据类接口：

map():     创建一个映射类，Python中用构造函数__init__()来完成
put(key,value):     增加键值对
get(key):   给定key值获取到对应的value值
del:    删除某个键值对  实现 del map[key] 这样的操作
len():  返回项目数
in:     判断是否位于该映射内，返回bool值

完成这个数据结构需要两个类BST与Node，其中BST的成员属于Node类，Node类用链接来完成对某个节点的描述，接下来依次用BST完成这些接口的描述：

1. 构造BinarySearchTree类

class BinarySearchTree(object):
    """构建二叉搜索树"""
    def __init__(self):
        self.root = None   #节点属于TreeNode类
        self.size = 0

2.构建Node节点类，为了简化BST类的工作，定义很多属性与辅助方法。

class Node(object):
    """构建节点类"""
    def __init__(self, key, val, left=None, right=None, parent=None):
        self.key=key    #键
        self.val=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.leftChild or self.rightChild)

    # 是否含有子节点
    def hasAnyChild(self):
        return self.leftChild or self.rightChild

    # 是否同时含有左右子节点
    def hasBothChildren(self):
        return self.leftChild and self.rightChild

    # 替换节点数据
    def replaceNodeData(self, key, val, left, right):
        self.key = key
        self.val = val
        self.leftChild = left
        self.rightChild = right
        # 改变其左右子节点的指向链接
        if self.hasLeftChild:
            self.leftChild.parent = self
        if self.rightChild:
            self.rightChild.parent = self

3.返回BST的节点数

def length(self):
    return self.size

# 可使用内置函数len()返回节点数
def __len__(self):
    return self.size

4.将BST变成一个迭代器,可用于for循环

# 迭代器
def __iter__(self):
    return self.root.__iter__()   #从根节点开始

5.在一棵二叉搜索树中插入新节点 put(),分两种情况：

• 要插入的二叉树为空，将自己作为根节点
• 非空，调用递归函数_put()

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

6._put()函数的过程描述：

• 如果要插入的key值<当前节点的key值，那么就递归到其左子树。

  • 如果没有左子树，那么key就成为左子节点

• 如果要插入的key值>当前节点的key值，那么就递归到其右子树。

  • 如果没有右子树，那么key就成为右子节点

• 如果要插入的key值=当前节点的key值，那么就用新值替换掉旧值

根据流程描述写出代码：

def _put(self, key, val, currentNode):
        # 如果key<当前节点key值，递归到左子树
        if key < currentNode.key:
            if currentNode.hasLeftChild:
                self._put(key, val, current.leftChild)
            else:
                currentNode.leftChild = Node(key, val, parent=currentNode)
        # 如果key>当前节点key值，递归到右子树
        elif key > currentNode.key:
            if currentNode.hasRightChild:
                self._put(key, val, currentNode.rightChild)
            else:
                currentNode.rightChild = Node(key, val, parent=currentNode)
        # 如果要插入的key值=当前节点的key值，那么就用新值替换掉旧值
        else:get()方法：通过key值返回其对应的val值，分几种情况：

- 如果根节点为空，返回空（二叉树为空）
- 如果root不为空，调用递归方法`_get()`寻找
  - 如果找到，返回对应val值
  - 如果找不到，返回None或其他提示信息
            self.currentNode.val = val

7.get()方法：通过key值返回其对应的val值，分几种情况：

• 如果根节点为空，返回空（二叉树为空）
• 如果root不为空，调用递归方法_get()寻找
  • 如果找到，返回对应val值
  • 如果找不到，返回None或其他提示信息

# 查找功能
def get(self, key):
    if self.root:
        resNode = self._get(key, self.root)
        if res:
            return resNode.val
        else:
            return None
    else:
        return None

8.递归函数_get()的逻辑流程与_put()方法类似：

• 如果要比对的当前节点为空，返回None
• 如果key值=当前节点key值，返回当前节点
• 如果key值>当前节点key值，递归到右子树
• 如果key值<当前节点key值，递归到左子树

# 私有递归
def _get(self, key, currentNode):
    if not currentNode:
        return None
    elif key == currentNode.key:
        return currentNode
    elif key > currentNode.key:
        self._get(key, currentNode.rightChild)
    else:
        self._get(key, currentNode.leftChild)

9.以上已经实现二叉搜索树的“增、改、查”，还有就是最重要的“删”,比较啰嗦，大致分为以下几种情况：

• 如果BST为空，抛出一个异常
• 如果BST不为空，且只有一个节点root，删除root
• 如果BST不为空，调用_get()方法，找到符合条件的Node节点，再调用remove()方法删除

# 删除节点
def delete(self, key):
    if self.size > 1:
        resNode = self._get(key, self.root)
        if resNode:
            self.remove(resNode)
            self.size -= 1
        else:
            raise KeyError('查无此数！')
        elif self.size == 1 and key == self.root.key:
            self.root = None
            self.size -= 1
        else:
            raise KeyError("数据为空！")

10.remove()方法分为三种情况，逻辑流程如下：

1. 要删除的节点无子节点，也就是叶节点，移出父节点对其的指向即可（区分左右两种情况）

def remove(self, currentNode):
    # 1 待删除节点为叶节点，无子节点
    if self.currentNode.isLeaf():
        if currentNode == currentNode.parent.leftChild:
            currentNode.parent.leftChild = None
        else:
            currentNode.parent.rightChild = None

2.要删除的节点只有一个子节点（左或右），分三种情况：

1. 待删除节点无父节点，就是根节点了，调用repalceNodeData()方法完成置换
2. 待删除节点为左子节点：
   • 待删除节点有一个左子节点，将其左子节点上移，将待删节点的父节点指向其左子节点的父节点，将待删节点的子节点指向其父节点的左子节点，跳过待删节点。
   • 待删除节点有一个右子节点，左子节点上移，将待删节点的父节点指向其左子节点的父节点，将待删节点的左子节点指向其父节点的右子节点，跳过待删节点。
3. 待删除节点为右子节点
   • 待删除节点有一个左子节点，与上同
   • 待删除节点有一个右子节点，与上同

4.小结一下：删除哪个节点，就是将其左或右子节点的引用以及其父节点指向该节点的引用更换，跳过该节点。

# 2 待删除节点只有一个子节点
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.val, left=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.val,currentNode.rightChild.leftChild, currentNode.rightChild.rightChild)

3. 要删除的节点有两个子节点，并不是简单的将其中一个子节点上移，这样可能会破坏二叉搜索树的关系，所以必须找到一个合适的节点（后继节点successor），在原位置删除它，将其移动的要删除的节点的位置。

      # 3 待删除节点有两个子节点
      elif currentNode.hasBothChildren():
          successor=self.findSuccessor()
          successor.removeSucc()
          currentNode.key=successor.key
          currentNode.val=successor.val

1. 寻找后继节点（successor）findSuccesor()：后继节点就是待删除节点右子树中的最小节点

   # 寻找后继节点
   def findSuccessor(self):
       successor = None
       successor = self.rightChild.findMin()
       return successor
   

2. 寻找最小节点findMin():在右子树中找到最左边的节点(自己想哈）

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

3.删除后继节点removeSucc(),要删除的节点必定为左子节点！(自己想哈)，分为两种情况：

1. 要删除的节点是叶节点，没有子节点
2. 要删除的节点只有一个右节点（自己想哈）

# 删除后继节点
def removeSucc(self):
    if self.isLeaf():
        self.parent.leftChild = None
    else:
        self.parent.leftChild = self.rightChild
        self.rightChild.parent = self.parent

11.其他内置魔法方法，比较简单。

# 迭代器
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

    # 赋值方法
    def __setitem__(self, k, v):
        self._put(k, v)
    # 是否包含某个元素

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

12.BST性能分析：

• 插入put()时间复杂度取决于树的高度，如果BST是一棵平衡二叉树(AVL），时间复杂度为O(logn);如果不是，比如该树全为左子节点，时间复杂度为O(n)了。

13.BST全部参考代码：

class BinarySearchTree(object):
    """构建二叉搜索树"""

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

    # 返回节点数
    def length(self):
        return self.size

    # 可使用内置函数len()返回节点数
    def __len__(self):
        return self.size

    # 迭代器
    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

    # 赋值方法
    def __setitem__(self, k, v):
        self._put(k, v)
    # 是否包含某个元素

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

    # 插入新节点
    def put(self, key, val):
        if self.root:
            self._put(key, val, self.root)
        else:
            self.root = Node(key, val)
        self.size += 1

    #_put()函数流程
    def _put(self, key, val, currentNode):
        # 如果key>当前节点key值，递归到左子树
        if key < currentNode.key:
            if currentNode.hasLeftChild:
                self._put(key, val, current.leftChild)
            else:
                currentNode.leftChild = Node(key, val, parent=currentNode)
        # 如果key<当前节点key值，递归到右子树
        elif key > currentNode.key:
            if currentNode.hasRightChild:
                self._put(key, val, currentNode.rightChild)
            else:
                currentNode.rightChild = Node(key, val, parent=currentNode)
        # 如果要插入的key值=当前节点的key值，那么就用新值替换掉旧值
        else:
            self.currentNode.val = val
    # 查找功能

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

    # 私有递归
    def _get(self, key, currentNode):
        if not currentNode:
            return None
        elif key == currentNode.key:
            return currentNode
        elif key > currentNode.key:
            self._get(key, currentNode.rightChild)
        else:
            self._get(key, currentNode.leftChild)

    # 删除节点
    def delete(self, key):
        if self.size > 1:
            resNode = self._get(key, self.root)
            if resNode:
                self.remove(resNode)
                self.size -= 1
            else:
                raise KeyError('查无此数！')
        elif self.size == 1 and key == self.root.key:
            self.root = None
            self.size -= 1
        else:
            raise KeyError("数据为空！")

    # 寻找最小值
    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

    # 寻找后继节点
    def findSuccessor(self):
        successor = None
        successor = self.rightChild.findMin()
        return successor

    # 删除后继节点
    def removeSucc(self):
        if self.isLeaf():
            self.parent.leftChild = None
        else:
            self.parent.leftChild = self.rightChild
            self.rightChild.parent = self.parent
    # remove方法分三种情况

    def remove(self, currentNode):
        # 1 待删除节点为叶节点，无子节点
        if self.currentNode.isLeaf():
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None

        # 3 待删除节点有两个子节点
        elif currentNode.hasBothChildren():
            successor = self.findSuccessor()
            successor.removeSucc()
            currentNode.key = successor.key
            currentNode.val = successor.val

        # 2 待删除节点只有一个子节点
        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.val, left=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.val,currentNode.rightChild.leftChild, currentNode.rightChild.rightChild)