В чем разница между массивом и бинарным деревом поиска в эффективности?

Question

Я хочу знать, что лучше: массив или бинарное дерево поиска в (вставить, удалить, найти max и min) и как я могу улучшить их оба?

Answer 1

Массив позволяет произвольный доступ к каждому элементу в нем.таким образом, вы получаете вставку, удаление и ищите определенный элемент в O(1), а max / min, удаление в O(n).[вы также можете сделать max / min O(1) и удалить O(n) вместо этого].Если вы сохраняете свой массив отсортированным, то вставка / удаление будет O(n), но вы получите O(logn) find и O(1) min / max.

A BST отсортировано по определению, и для обычного [несбалансированного] BST вы получаете O(n) поведение в худшем случае.Для сбалансированного BST вы получаете O(logn) вставка / удаление / поиск.Вы можете получить O(1) мин / макс любым способом для обоих.

Массивы также обычно быстрее итерируют [при условии, что порядок итерации не важен], поскольку вы получаете лучший кэш производительность.Кроме того, в отличие от BST - который по своей природе имеет неограниченный размер, массив требует перераспределения и копирования данных, когда ваш массив заполнен.

Улучшение BST можно сделать, сделав его сбалансированный - как AVL или красно-черные деревья .

Что лучше ?это зависит от приложения.Обычно, когда вы планируете вставлять данные и сохранять их отсортированными, предпочтение отдается BST.Если основной целью является произвольный доступ или итерация: вы обычно используете массив.

Answer 2

Сравнение производительности массивов и деревьев двоичного поиска:

                 Array                     Binary search tree
          Unsorted   Sorted           Average            Worst case
Space      O(n)       O(n)             O(n)               O(n)
Search     O(n)       O(log n) *       O(log n)           O(n)
Max/Min    O(n)       O(1)             O(1) **            O(1) **
Insert     O(1)       O(n)             O(log n)           O(n)
Delete     O(1)       O(n)             O(log n)           O(n)

* при условии бинарного поиска

** требует дополнительных указателей на min и max, в противном случае это O (log n)