Является ли этот список бинарным деревом поиска?

Question

Является ли следующий список BST или нет?

list:{2,5,3,8,6}

Есть ли способ, которым я могу это определить?

Считать, что в моем списке будет 100000 элементов.

Answer 1

Быстрый ответ: нет. BST - это дерево, и у вас есть список.

Длинный ответ таков: возможно, можно кодировать дерево как список, и в этом случае будет ли ваш список декодирован в дерево или нет, будет зависеть от алгоритма кодирования. Для получения более подробной информации см. Вики-страницу BST http://en.wikipedia.org/wiki/Binary_search_tree

На самом деле ваш список может быть зашифрованной версией BST. Если вы читаете элементы слева направо, помещая их в стек, и всякий раз, когда у вас в стеке есть 3 элемента, сделайте:

parent = pop()
right = pop()
left = pop()
push new Node(parent, left, right)

тогда вы должны получить действительный BST. Но я только размышляю здесь.

Answer 2

у вас есть список, вам нужно построить BST из этого списка

BST имеет следующие свойства

1- Каждый узел имеет двух дочерних узлов или это листовой узел

2- Для каждого узла его левое поддерево меньше значения узла

3- Для каждого узла его правое поддерево больше значения узла

a BST ДОЛЖЕН БАЛАНСИРОВАТЬСЯ, т. Е. При вставке узлов в BST код должен соответствовать 3 условиям.

Поиск в BST - это операция O (log n), поскольку каждый шаг поиска делит пространство поиска на две половины и выбирает одну из половины.

В одном случае поиск займет O (N) время

Подумайте о следующем

узел = {1,2,3,4,5}

если мы сделаем BST из этого набора узлов, он будет правильно смещен, что означает, что каждый следующий узел будет на правом поддереве, здесь, если мы хотим найти элемент, нам нужно пройти по всему правому поддереву, как ссылка список.