Каков компромисс производительности с BST, реализованным, используя связанный список или массив?

Question

Мне было просто интересно, каково будет соотношение производительности между бинарным деревом поиска, реализованным с использованием связанного, и бинарным деревом поиска, реализованным с использованием массива.Я просто хочу знать сравнение производительности.Я уже прочитал этот вопрос в stackoverflow.

Answer 1

Я не думаю, что вы можете реализовать двоичное дерево поиска с массивом.Бинарное дерево поиска похоже на расширенный связанный список.Фактически, если вы используете базовый BST (не балансирующий) и вводите предварительно отсортированные данные, вы в основном получаете связанный список.