Бинарное дерево с зигзагообразным узором

Question

Как вы можете упорядочить последовательность из n различных чисел так, чтобы при вставке по одному в двоичное дерево поиска оно генерировало дерево высотой n - 1, следуя зигзагообразному шаблону, например слева, справа, слева, верно,…

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

Answer 1

Хорошо, давайте разберем пример. Первое значение, которое мы вставляем в дерево, может быть любым, поэтому я выберу 0.

 0

Теперь нам нужно что-то, чтобы мы сделали шаг вправо. Это означает, что мне нужно что-то больше 0, поэтому я выберу 137.

 0
  \
  137

Теперь мне нужно что-то, что будет левым потомком 137. Это означает, что оно должно быть между 0 и 137 - что угодно меньшее идет слева от нуля, а все большее - справа от 137. Итак, я выберу что-то в этом диапазоне, скажем, 42:

  0
   \
   137
   /
  42

Теперь мне нужно что-то, что становится правое дитя 42 лет. Это означает, что оно должно быть между 42 и 137. Все, что меньше, будет go слева от 42 (или слева от 0, равно как не в порядке) или справа от 137 (тоже не в порядке) , Итак, давайте выберем что-то между 42 и 137 - скажем, 98:

  0
   \
   137
   /
  42
   \
   98

Здесь вы можете заметить закономерность: в каждой точке значение, которое мы вставляем, должно находиться между двумя последними вставленными значениями . Вы понимаете, почему это так? Исходя из этого, можете ли вы придумать способ упорядочения значений 0, 1, 2, ..., n-1, чтобы получить зигзагообразный паттерн?

Надеюсь, это поможет!