Найти допустимые последовательности в деревьях двоичного поиска

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;

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

Нужно ли делать узоры? Напишите в свойстве минимальной формы для проверки. Спасибо.

Answer 1

Перейдите сюда: https://www.cs.usfca.edu/~galles/visualization/BST.html введите каждый номер один за раз в левом верхнем углу, рядом с «вставить» и нажмите «вставить». При вводе чисел он будет строить двоичное дерево.

Сделайте это для каждой последовательности и сравните, как они выглядят.

Это маршрут через "а)":

Это одна цепь. Это предпринятое маршрут через «с)»:

Это не единственный путь сверху вниз, то есть неправильный поворот ответвление. Вы бы не ошиблись, если бы 363 был на дереве, и вы просто пошли прямо к нему.

В C) 911 расщепляется налево на 240 и справа на 912.

В е) 347 расколов прямо на 621 и оставили на 299.

Они не могут быть последовательности, пройденный на пути к 363, потому что один из узлов в каждом списке не на пути к 363.

[Скриншоты взяты из https://www.cs.usfca.edu/~galles/visualization/BST.html]

Answer 2

диапазона [мин, макс] - инициализация [1,1000]

ключ - целевой ключ для поиска

SEQ [1, N] - последовательность чисел в двоичном дереве поиска

Идея заключается в том, чтобы следить за допустимый диапазон [мин, макс]. Первоначально все номера от 1 до 1000 находятся в зоне действия. Если вы столкнулись с узлом с ключевым словом 2, а ваша цель - 363, вы должны сделать правильный оборот. По мере того, как вы делаете правильный оборот, любой ключ, с которым вы столкнетесь в этом поддереве, должен быть больше 2. Таким образом, вы обновляете min в диапазоне до 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