二叉查找树归纳-查找，插入，删除

二叉查找树主要的操作包括查找指定元素，插入元素，删除指定元素，以及寻找最小节点，最大节点，查找指定元素的前驱或后继节点。

对于存在重复元素的二叉查找树，对于重复元素可以有两种处理方式：
1.将重复元素用一个链表或支持动态扩容的数组进行存储
2.将重复元素视作大于节点值的元素来处理，将其放在右子节点。这会影响查找相关的动作或删除操作的查找环节。

关于时间复杂度，不管是查找，插入还是删除，都依赖于一个查找动作，而查找动作，与树的深度正相关。
极好的情况下，树是完全二叉树，深度为logn
极差的情况下，树退化为链表，深度为n
因此，最好最坏的时间复杂度分别是O(logn)和O(n)

class BinarySearchTree(object):
    def __init__(self, val = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def select(self, root, data):
        """
        BST的查找
        """
        p = root
        while p:
            if p.val < data:
                p = p.right
            elif p.val > data:
                p = p.left
            else:
                return p
        return None

    def insert(self, root, data):
        if root is None:
            root = BinarySearchTree(data)
            return True
        p = root
        while p:
            if p.val < data:
                if p.right:
                    p = p.right
                else:
                    p.right = BinarySearchTree(data)
                    return True
            elif p.val > data:
                if p.left:
                    p = p.left
                else:
                    p.left = BinarySearchTree(data)
                    return True
            else:
                return False
    
    def delete(self, root, data):
        # p是欲删除的节点，pp是待删除节点的父节点
        p = root
        pp = None

        # 首先还是需要查找到待删除节点
        while p and p.val!=data:
            if p.val > data:
                pp = p
                p = p.left
            else:
                pp = p
                p = p.right
        # 未找到节点
        if p is None:
            return root
        
        # 待删除节点有左右节点，则此时需要删除待删除节点的最小节点。
        if p.left and p.right:
            # minp为右子树的最小节点，minpp为minp的父节点
            minp = p.right
            minpp = p
            while minp.left:
                minpp = minp
                minp = minp.left
            p.data = minp.data
            p = minp
            pp = minpp
        
        # 由于原始待删除节点同时存在左右子节点时，会经历交换，然后将其右子树的最左节点设置为待删除节点，所以此时新的p，要么只有右节点，要么只有左节点(原始情况)，要么没有子节点。
        child = None
        if p.left:
            child = p.left
        elif p.right:
            child = p.right
        
        # 判断需要删除哪个节点。
        if pp is None: # 删除节点为根节点
            pp = child
        elif pp.left == p:
            pp.left = child
        else:
            pp.right = child
        del p
        return root