[数据结构与算法]和二叉树相伴的美好时光~@labuladong Day5 - BST

写在前面

本篇全部集中在二叉树相关问题上，是参考东哥的思路进行的练习和思考。东哥有《labuladong 的算法小抄》以及宝藏微信公众号 labuladong，github 也有项目，自来水推荐购买和关注。

二叉树思考学习记录

Day5 二叉搜索树的增删查改

有关基本二叉树的定义不再赘述，本篇不讨论有重复元素的情况，也就是二叉搜索树中的节点值都是互不相同的。

由于二叉搜索树左小右大（而且递归到底都符合），所以可以很方便地进行增删查改，复杂度都是 log N。这种操作上的便利程度几乎秒杀一切数据结构，无奈它不太能处理重复元素的情况。“无重复元素”既成就了二叉树的极低复杂度逆天操作，也是刻在二叉搜索树 DNA 里的致命伤。但是，emmm 这不是 BST 的错，战士应该熟知每把兵器的特点，然后最漂亮地去战斗(●ˇ?ˇ●)

本篇提到的节点值，可以是平时刷题常见的数值，也可以是类似哈希表中的 key，只要是能够比较大小的、无重复的都可以作为此处的节点值。而下面所提到的任何操作，都应该保证操作之后不改变 BST 本身的固有特性，比如中序有序等等。

• 查：首先要解决的是查找，因为查找是一切的基础。你想删除得先找到这个节点，想增加节点得先确定在哪儿增加，想修改节点值也同理。查找又可以查找指定值或者最大最小值。
• 改：应该是查找之后最简单的操作，也就是修改节点值；
• 增：增加节点也相对比较简单，顺着 BST 一路左拐或右拐下去，找到目标空指针往那儿嗯放就完事儿了；
• 删：你可以想象成二叉搜索树本身是条绳子，上面穿了很多珠子，然后被扭来扭去折起来了。绳子的延伸决定了中序遍历的顺序，每个珠子就是一个个节点。当你要删掉某个节点 M 的时候，就是要珠子 M 的位置上把绳子断掉，把珠子拿下来，再把绳子接起来就好了。
  怎么算接起来了？被拿掉的珠子前面那颗 L 和后面那颗 N 连在一起就行。那前面 L 在哪儿呢？它就是 M 节点左子树的最大值。 后面 N 又在哪儿呢？它就是 M 节点右子树的最小值。取 L 或者 N 其中一个，放在原本 M 的位置上，再将其与另外一个相连，就可以实现连接绳子的目的了。
  当然，还有一些特殊情况，比如删除的就是叶子节点，没有左右子树了，哪里去找 L 和 N 呢？首先明确一点，计算 M 没有左右子树，L 和 N 也是存在的。为了和上面统一，我们可以认为 “L” 和 “N” 分别“存在”于 M 的左右空子树中，仍然任取一个“放在”原本 M 的位置上，再和另外一个“”相连就好了。那两个空节点肯定不会相连啊，你就当它们过家家得了。其实这并不影响，因为当 M 是叶子节点的时候，如果它不是最小或者最大值的话，它的 L 和 N 应该是原本就连在一起的，所以 M 就直接退出舞台就可以了。
• floor 找到小于目标值的最大的节点 和 ceiling：找到大于目标值的最小的节点：这两个很像，放在一起说吧。其实这两个方法肯定是在“查找目标值”的时候，顺路就办了的事儿，当然这里预设条件是目标值不在 BST 中。
  你可以想象成皇上下了令要抓人，按照目标人物的特点，从皇宫出来一层层行政辖区找下来。到了某个村儿，地界儿就那么点儿大，村长溜达了一下知道没在自己的巴掌地儿，但是又百口莫辩（就是循着踪迹到的你这儿啊）。那怎么办，只能芝麻官来负荆请罪了ヽ(*。>Д<)o゜所以人没找到，村长被带回去了哈哈哈。那么这倒霉村长是谁呢？或者谁最近地确认了确实找不着这号人呢？就是你要的 floor 或者 ceiling 啦(●’?’●)，还好意思问。

那行吧，唠了这么些个了，总结一下上面，你都逐步需要哪些功能函数啊：

• 查找某值，若存在返回该节点，若不存在返回空；
• 查找最大值/最小值；
• 改；
• 增；
• 删，除了一些 basecase，需要用到前面的查找最大或最小值。
• 还有带走村长的 floor 和 ceiling。

呵呵，作业这就来了，逐渐变态。

Day5 练习

用二叉搜索树的思路， AC 掉 706. 设计哈希映射。需要说明的是，因为要照顾这个题，所以有很多我觉得不是很灵光的函数，因为有时候你需要在节点和 key 之间转换。我觉得写的肯定还不够优雅，但是我不想改了……头晕(((φ(◎ロ◎;)φ)))，然后我也没写 floor 和 ceiling。

class MyHashMap:
    # 因为要 AC 这道哈希题，所以 Leetcode 官方的 Treenode 不太适合了
    class MyTreeNode:
        def __init__(self, val=[], left=None, right=None):
            self.val = val
            self.left = left
            self.right = right

    def __init__(self):
        """
        Initialize your data structure here.
        """
        # 这里我就是这么维护 Tree 的
        # 如果需要判断 tree 是否为空，得判断 self.BST.val，不能 self.BST
        self.BST = self.MyTreeNode([])


    def put(self, key: int, value: int) -> None:
        """
        value will always be non-negative.
        """
        cur = self.BST
        # 如果此时没有根节点
        if not cur.val: 
            cur.val = [key, value]
            return
        # 否则，按规则去放置
        while cur:
            k, v = cur.val
            if key == k:
                cur.val = [key, value]
                return
            elif key < k:
                if not cur.left:           
                    cur.left = self.MyTreeNode([key, value])
                    return
                else:
                    cur = cur.left
            else:
                if not cur.right:
                    cur.right = self.MyTreeNode([key, value])
                    return
                else:
                    cur = cur.right


    def get(self, key: int) -> int:
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        """
        cur = self.BST
        # 树为空
        if not cur.val: return -1
        # 查树
        while cur:
            k, v = cur.val
            if key == k:
                return v
            elif key < k:
                cur = cur.left
            else:
                cur = cur.right
        # 还是没查到
        return -1



    def remove(self, key: int) -> None:
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        """
        # 如果待删除的节点根本不存在，直接返回
        if self.get(key) == -1: return
        # 找到待删除的节点以及其父节点，如果待删除是 root，我这里返回两个一样的节点
        cur_node, pre_node = self.getNode(key)        
        #  待删除节点是叶子节点
        if not cur_node.left and not cur_node.right:
            # 待删除节点是 root 节点，就是说此时树里就 root 一个，那就需要重新指定 self.BST
            if cur_node == pre_node:
                self.BST = self.MyTreeNode([])
            elif cur_node == pre_node.left:
                pre_node.left = None
            else:
                pre_node.right = None
        # 待删除节点有一个右节点
        elif not cur_node.left:
            # 同理，判断是否是 root
            if cur_node == pre_node:
                self.BST = cur_node.right
            elif cur_node == pre_node.left:
                pre_node.left = cur_node.right
            else:
                pre_node.right = cur_node.right
        # 待删除节点有一个左节点
        elif not cur_node.right:
            # 同理，判断是否是 root
            if cur_node == pre_node:
                self.BST = cur_node.left
            if cur_node == pre_node.left:
                pre_node.left = cur_node.left
            else:
                pre_node.right = cur_node.left
        # 待删除有两个节点，去找左子树的最大值，断掉它和其父节点的连接，然后把它的值赋给当前待删除节点的值
        else:
            left_max_node = self.getMax(cur_node.left)
            self.remove(left_max_node.val[0])
            cur_node.val = left_max_node.val

        

    def getMax(self, root):
        # 返回的是节点
        cur = root
        while cur.right:
            cur = cur.right
        return cur
    
    def getMin(self, root):
        # 返回的是节点
        cur = root
        while cur.left:
            cur = cur.left
        return cur
    
    def getNode(self, key):
        cur = self.BST
        pre = self.BST
        if not cur.val: return None, None
        while cur:
            k, v = cur.val
            if key == k:
                return cur, pre
            elif key > k:
                pre = cur
                cur = cur.right
            else:
                pre = cur
                cur = cur.left
        return None, None

Day5 的思考和补充

不想思考，不想补充(￢︿??￢☆)