特殊的二叉树-二叉查找树/二叉搜索树

二叉查找树（Binary Search Tree）

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的，它最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。 那么二叉查找树是如何实现快速查找、插入等操作的呢？这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树的查找操作

class Node:
    def __init__(self, val):
	self.val = val 
        self.left = None
        self.right = None

class BinarySearchTree(object):
    def find(self, root, target):
        # 如果目标值小于当前节点值，则去节点的左子树里查找；否则去节点的右子树中查找
        while root:
            if target < root.val:
                root = root.left
            elif target > root.val:
                root = root.right
            else:
                return True
        return False

二叉查找树的插入操作

def insert(self, root, target):
    # 如果当前树不存在，则插入节点为根节点
    if not root: 
        root = Node(target)
        return

    while root:
        # 如果目标值小于当前节点值，且当前节点值不存在左子树，则将新节点直接插入到左子节点位置；不为空继续遍历
        if target < root.val:
            if not root.left:
                root.left = Node(target)
                return 
            else:
                root = root.left
        # 如果目标值大于当前节点值，且当前节点值不存在右子树，则将新节点直接插入到右子节点位置；不为空继续遍历
        else:
            if not root.right:
                root.right = Node(target)
                return
            else:
                root = root.right

二叉查找树的删除操作

二叉查找树的删除操作会稍微复杂一点，针对删除的节点的子节点个数不同，需要分别处理：

1. 如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除的节点指针置为None即可
2. 如果删除的节点只有一个子节点，只需要更新父节点中，指向要删除节点的指针，让它指向删除节点的子节点即可。
3. 如果删除的节点有两个子节点。我们需要找到这个节点右子树中的最小节点，把它替换到要删除的节点上。然后再删除这个最小节点，因为最小节点肯定没有左子节点，所以可以应用第二种情况删除这个最小节点。

当然删除也有另一个非常简单方法即将删除的节点标记为已删除，但是并不真正从树种把这个节点去掉。这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但是删除操作就变得简单了很多。而且，这种处理方法也并没有增加插入、查找操作代码实现的难度。

def delete(self, root, target):
    # p 指向要删除的节点
    p = root
    # pp 指向p的父节点
    pp = None
    while p and p.val != target:
        pp = p
        if target > p.val:
            p = p.right
        else:
            p = p.left
    # 没有找到要删除的值，直接返回
    if not p: return

    # 如果p有两个子节点
    if p.left and p.right:
        minp = p.right
        # minpp是minp的父节点
        minpp = p
        # 查找右子树中最小值，替换到p中
        while minp.left:
            minpp = minp
            minp = minp.left
        p.val = minp.val
        # 接下来删除minp节点
        p = minp
        pp = minpp

    # 如果p只有一个节点，记录其子节点
    if p.left:
        child = p.left
    elif p.right:
        child = p.right
    # 如果p没有子节点，子节点为None
    else:
        child = None

    # 如果pp为None证明删除的为根节点，直接将子节点赋给根节点
    if not pp:
        root = child
    # 删除p节点
    elif pp.left == p:
        pp.left = child
    else:
        pp.right = child

二叉查找树的遍历

因为二叉查找树的特性，我们使用中序遍历即可得到一个排好序的数据序列。时间复杂度是O(n)

# 中序遍历，结果即为有序的数据序列
def inorderTraversal(self, root):
    res = []
    stack = []

    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        res.append(root.val)
        root = root.right

    return res

支持重复数据的二叉树

1. 用链表，使节点可以存储多个相同值的对象
2. 将相同值的对象视作"大于"原节点值，插入右子节点——查找时，遇到相同对象不马上停，而是一直查到叶子节点为止。

二叉查找树的时间复杂度

在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是O(n)和O(logn)，分别对应二叉树退化成链表的情况 和 完全二叉树。