#binary-search-tree #red-black-tree
#двоичное дерево поиска #красное-черное-дерево
Вопрос:
public class Entry{
int key;
String value;
}
Если у вас есть массив записей.
Entry[]
Вы можете выполнить двоичный поиск по этому массиву, чтобы найти, вставить или удалить запись all в O(Log (n)). Я также могу выполнить поиск по диапазону в O(log (n)).
И это очень просто.
Что дает мне сравнительно сложная структура данных, такая как красно-черное сбалансированное дерево поиска, по сравнению с простым отсортированным массивом значений ключа?
Ответ №1:
Если данные неизменяемы, дерево не имеет никакой пользы.
Единственным преимуществом массива является локальность ссылок, например, данные расположены близко друг к другу, и процессор может кэшировать их.
Поскольку массив отсортирован, поиск выполняется O (log n)
Если вы добавляете / удаляете элементы, все меняется.
Для небольшого количества элементов массив лучше (быстрее), это из-за местоположения ссылки.
Для большего количества элементов красное черное дерево (или другое самобалансирующееся дерево) будет работать лучше, потому что массиву потребуется переместить элементы.
например, для вставки и удаления потребуется O (log n) огромное n / 2 для сдвига.