Space Cowboy

生死去来 棚头傀儡 一线断时 落落磊磊

0%

好耶!是 BST

关于 BST

BST 算是 leetcode 关于树的考察的一个重点了。不过这并不意味着它是一个可以广泛运用的数据结构。主要原因就在于其查找、插入、删除操作的时间复杂度均与树高度成正比,换句话说,就是 O(logn) 。这意味着在很多情况下,时间消耗都比较大。所以我们会转而使用平衡树。比如红黑树,B+,B-等等(不过这些还没学会,就不说了

回到 BST,它有一个重要的特性,就是:

  • 左低右高:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
  • 左右子树也均为 BST

这也就意味着,它中序遍历的结果是一个递增数列。

另外还有两个关于 BST 的概念。这两个概念是依附于 BST 本身的性质而提出的,并不是独立的概念。

  • 前驱节点(predecessor):比当前节点小的最大节点
  • 后继节点(successor):比当前节点大的最小节点

BST 的前驱节点与后继节点

下面有两个不严谨的算法,用来求 BST 中某个节点的 predecessorsuccessor

  • predecessor 比当前节点小的最大节点
  • successor 比当前节点大的最小节点
1
2
3
4
5
6
7
8
9
10
11
def predecessor(node):
node = node.left
while node.right:
node = node.right
return node

def successor(node):
node = node.right
while node.left:
node = node.left
return node

注意到我们直接取了 node.leftnode.right 。但该节点的左右子树具体存在与否是不一定的,所以在调用函数前,需要判断左右子树的存在性。

BeforeEach

预先对 BST 的数据类型做一下约定,后不赘述:

1
2
3
4
5
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

构建:108 将有序数组转换为二叉搜索树

二叉搜索树的中序遍历是升序数组,这个特性无需赘述了。另外二叉树的中序遍历确实没啥好说的。
不过将一个升序数组转换为平衡二叉搜索树还是很有用的,可以大幅度提高查找、插入、删除的速度。所以就来说一下这道 leetcode 题目。

题目

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

分析

一个数组是中序遍历的结果,意味着如果我们找到了树的根节点,那么就可以根据这个根节点将数组一分为二。左半部分是左子树,右半部分是右子树。
对于一个数列,找一个数字当根节点是没啥限制的。但这道题要求是平衡二叉树。换句话说,我们必须从数列中间选数字,才能保证平衡。
而数列个数可能为奇数或偶数。当为奇数时,存在中位数。当为偶数时,不存在中位数,不过我们可以在中间俩数中随便选一个。
解法不一定是最好的。

代码

1
2
3
4
5
6
7
8
9
10
11
def sortedArrayToBST(nums: List[int]) -> TreeNode:
if not nums: return None

idx = len(nums) // 2
mid = nums[idx]

node = TreeNode(mid)
node.left = sortedArrayToBST(nums[:idx])
node.right = sortedArrayToBST(nums[idx+1:])

return node

注意到 idx = len(nums) // 2 这句代码,是整数除。你也可以选择右边的数字,都一样的。

搜索:700 二叉搜索树中的搜索

名字里就带着搜索,怎么能少了搜索呢?
事实上因为 BST 的高低肩左低右高的特性,我们在遍历树查找时,并不需要访问到所有的节点,而是根据当前节点的大小关系,找到一条直通目标数的路径即可。
更进一步的说,所花时间与树的高度成正比,即 O(logn)

题目

给定二叉搜索树(BST)的根节点和一个值。 你需要在 BST 中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

分析

既然是树,那么我们会先从根节点访问。根节点如果存在,且不是目标数的话,它和目标数就会有大小关系。
而 BST 左低右高,所以一个确定下一个访问的节点是左子树还是右子树。
如果访问到叶子节点,或者是不存在的节点了。还没有找到数,那就说明数根本就不存在,纯粹是在累傻小子。

代码

1
2
3
4
def searchBST(root: TreeNode, val: int) -> TreeNode:
if not root or root.val == val:
return root
return searchBST(root.left, val) if root.val > val else searchBST(root.right, val)

逻辑非常简单,根据 root.valval 的大小关系,选择前进的方向。
当节点不存在,或者找到节点了,那就返回这个子树。
注意访问到不存在的节点不一定是叶子节点。因为左低右高,如果你发现 valroot.val 小,但是当前 root 却没有左子树,也就是没有比它更小的节点了, 那么也就是找不到了。

插入:701 二叉搜索树中的插入操作

题目

给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

分析

注意到插入值与原 BST 中任意节点值都不一样。所以我们一定可以知道当前节点和要插入的值的大小关系。
也就是说,我们通过比较 root.valval 的值,就可以知道应该往左子树走还是右子树走。

代码

1
2
3
4
5
6
7
8
9
10
def insertIntoBST(root: TreeNode, val: int) -> TreeNode:
if not root:
return TreeNode(val)

if root.val < val:
root.right = insertIntoBST(root.right, val)
if root.val > val:
root.left = insertIntoBST(root.left, val)

return root

当然了,你可以用迭代来写,但其实一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def insertIntoBST(root: TreeNode, val: int) -> TreeNode:
node = TreeNode(val)
if not root: return node

cur = root
while True:
if cur.val < val:
if cur.right:
cur = cur.right
else:
cur.right = node
break

if cur.val > val:
if cur.left:
cur = cur.left
else:
cur.left = node
break

return root

迭代就是找了个指针来遍历 BST,其实跟遍历链表是一样的,只不过对于每个节点都有两种可能性。

删除:删除二叉搜索树中的节点

题目

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
说明: 要求算法时间复杂度为 O(h),h 为树的高度。

分析

如何找到要删除的节点?我们在之前讨论 BST 的搜索时就已经完整阐述过了。
删除节点很容易,只要将其变成 None 就行。但问题是,我们需要在删除节点后,还要保证新树依旧是 BST。
从另一个角度来看,BST 的中序遍历是递增数列,也就是说,我们要在递增数列中删除一个值,然后还得保证新数列是递增数列。
那么,我们如何删除一个数组中的数字?按照以下两步:

  1. 我们有一个原始数组:
    [1, 2, 3, 4, 5]

  2. 要删除 3,那么就用 4 覆盖 3:
    [1, 2, 4, 4, 5]

  3. 删除冗余的 4
    [1, 2, 4, 5]

在有序数列中,找到比某一个数大或小的数很容易,但如何在 BST 中找?
答案就是利用 BST 左低右高的性质,寻找其前驱节点与后继节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def deleteNode(root: TreeNode, key: int) -> TreeNode:

def predecessor(node):
node = node.left
while node.right:
node = node.right
return node.val

def successor(node):
node = node.right
while node.left:
node = node.left
return node.val

if not root: return None
if root.val > key:
root.left = deleteNode(root.left, key)
elif root.val < key:
root.right = deleteNode(root.right, key)
else:
if not root.left and not root.right:
root = None
elif root.left:
root.val = predecessor(root)
root.left = deleteNode(root.left, root.val)
elif root.right:
root.val = successor(root)
root.right = deleteNode(root.right, root.val)

return root

主逻辑很简单,分为两层。

  • 第一层:找到要删除的节点
  • 第二层:删除节点
    • 第一节:若是叶子节点,直接删除
    • 第二节:若不是叶子节点,有左子树,用前驱节点覆盖,然后递归删除前驱节点
    • 第三节:若不是叶子节点,有右子树,用后继节点覆盖,然后递归删除后继节点