在二叉搜索树中查找有效序列

Question

假设1到1000之间的整数按二叉查找树排列，希望找到363这个数，下面的一些序列，哪个不是遍历的节点序列？

a) 2, 252, 401, 398, 330, 344, 397, 363 ;

b) 924, 220, 911, 244, 898, 258, 362, 363 ;

c) 925, 202, 911, 240, 912, 245, 363 ;

d) 2, 399, 387, 219, 266, 382, 381, 278, 363 ;

e) 935, 278, 347, 621, 299, 392, 358, 363.

有必要做图案吗？以最小形式写属性以检查。谢谢。

Answer 1

转到此处：https://www.cs.usfca.edu/~galles/visualization/BST.html 在左上角 'insert' 旁边一次输入每个数字，然后单击 'insert'。当您输入数字时，它将构建一个二叉树。

对每个序列执行此操作并比较它们的外观。

这是经过"a)"的路线：

这是一个单链。这是通过 "c)":

的尝试路线

它不是从上到下的单一路径，它有一个 wrong-turn 分支。如果 363 在树上，你就不会走错路，你直接去。

在 c) 中，911 在 240 上向左拆分，在 912 上向右拆分。

在 e) 中，347 在 621 上向右拆分，在 299 上向左拆分。

不可能是去363途中遍历的序列，因为每个链表中的一个节点不是去363的途中

[截图自https://www.cs.usfca.edu/~galles/visualization/BST.html]

Answer 2

范围 [min,max] - 初始化为 [1,1000]

key - 要搜索的目标键

seq[1,N] - 二叉搜索树中的数字序列

想法是跟踪有效范围 [min,max]。最初，从 1 到 1000 的所有数字都在范围内。如果你遇到一个键为 2 的节点，你的目标是 363，你会右转。当您右转时，您将在此子树中遇到的任何键都应大于 2。因此您将最小范围更新为 2。现在您的范围是 [3,1000]。遇到252，范围就变成了[253,1000]。在 401，你左转所以子树中的所有键都必须小于 401。所以你将最大值设置为 400，它变成 [253,400]。

现在在序列中的任何一点，您都需要检查值是否在范围内。如果不是，则存在违规行为。如果密钥匹配，则它必须是序列中的最后一个数字。

这是伪代码

boolean validate(seq[1,N],key,range)
    for i from 1 to N
        if(seq[i] < range.min || seq[i] > range.max)
            return false
        if(key < seq[i])
            range.max := key-1
        else if(key > seq[i])
            range.min := key+1
        else
            return i=N
    return true

Answer 3

直觉：

如果 sequence[i] > sequence[i+1] ，路径已经在左子树中搜索过，序列中的下一个元素必须不超过 sequence[i]

否则，路径包含右子树的元素，序列中的下一个元素必须不少于sequence[i]

我们可以使用上述逻辑编写一个蛮力解决方案，其结果的时间复杂度为 O(n^2)

# checks if any elements in the sequence is greater than val
def any_element_greater(sequence, val):
  for e in sequence:
    if e > val:
      return True
  return False

# checks if any elements in the sequence is lesser than val
def any_element_lesser(sequence, val):
  for e in sequence:
    if e < val:
      return True
  return False

# checks if the sequence is valid
def is_valid_seq(sequence):
  if len(sequence) < 2:
    return True
  
  prev = sequence[0]
  for idx, val in enumerate(sequence):
    if prev > val:
            # checks if the rest of the sequence is valid based on direction
      if any_element_greater(sequence[idx:], prev):
        return False
    elif prev < val:
            # checks if the rest of the sequence is valid based on direction
      if any_element_lesser(sequence[idx:], prev): 
        return False
    prev = val

  return True

优化：

我们可以使用 max 和 min 变量来继承有效范围 - memoization

def valid_sequence(sequence, i=0, m_min=1, m_max=1000):
  '''
  Checks if the Sequence is a correct path in BST
  Parameters:
    sequence: path to the data in the BST
    i: current data we are validating in the path
    m_min: data should be more than m_min
    m_max: data should be less than m_max
  Returns:
    Boolean: If the sequence is a valid path in BST
  '''
    if len(sequence) == 0:
        return True

  data = sequence[i]

  # check if data is in valid range
  if not (m_min <= data <= m_max):
    return False

  # Base case, return if we reached the end
  if i == len(sequence) - 1:
    return True

  '''
  Adjust min, max for the next data elements
  depends on the next element in the sequence
  '''
  next = sequence[i+1]
  if next > data:
    m_min = max(m_min, data)
  else:
    m_max = min(m_max, data)

  return valid_sequence(sequence, i+1, m_min, m_max)

测试：

options = {
    'a': [2, 252, 401, 398, 330, 344, 397, 363],
    'b': [924, 220, 911, 244, 898, 258, 362, 363],
    'c': [925, 202, 911, 240, 912, 245, 363],
    'd': [2, 399, 387, 219, 266, 382, 381, 278, 363],
    'e': [935, 278, 347, 621, 299, 292, 358, 363]
}

for option in options:
  print(f'{valid_sequence(options[option])} \t - {option}. {options[option]}')

结果：

True     - a. [2, 252, 401, 398, 330, 344, 397, 363]
True     - b. [924, 220, 911, 244, 898, 258, 362, 363]
False    - c. [925, 202, 911, 240, 912, 245, 363]
True     - d. [2, 399, 387, 219, 266, 382, 381, 278, 363]
False    - e. [935, 278, 347, 621, 299, 292, 358, 363]

推理：

在选项c中，912大于911，而我们在240处进入左子树。所以它是无效的

在选项e中，我们从347开始，但我们在序列中遇到了299和292。所以无效

在二叉搜索树中查找有效序列

Find valid sequences in Binary search trees

algorithm

sequences

binary-search-tree