Резюме
В этом спринте вы познакомились со структурой данных дерево. Узнали, что такое бинарные деревья. У таких деревьев в узле может быть не более двух потомков. В общем случае количество потомков может быть произвольным.
Теперь вы знаете, какими свойством должно обладать дерево, чтобы в нём можно было эффективно осуществлять операции вставки, поиска, и удаления элементов. Прежде всего, дерево должно быть деревом поиска. Для этого должны выполняться требования:
- Левое и правое поддеревья, если существуют, являются двоичными деревьями поиска.
- Под произвольным узлом Х слева располагаются узлы со значениями меньше Х.
- Под произвольным узлом Х справа располагаются узлы со значениями больше Х.
Кроме того, дерево должно быть сбалансированным.
Существуют разные критерии сбалансированности. Вы узнали, что такое идеально сбалансированное дерево, АВЛ-дерево, и красно-чёрное дерево. Если дерево является сбалансированным по какому-то из критериев, операции вставки, поиска и удаления гарантированно выполняются за логарифмическое время.
Также вы узнали про абстрактную структуру данных приоритетная очередь. В ней каждый элемент имеет приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Приоритетная очередь позволяет узнать значение самого приоритетного элемента за константное время. Извлечение самого приоритетного элемента происходит за логарифмическое время, так же, как и добавление нового.
Обычно приоритетную очередь реализуют с помощью пирамиды. Другое название пирамиды — куча. Эта структура данных в памяти хранится в виде массива. Благодаря тому, что дерево является полным бинарным, нет необходимости хранить ссылки на родительские или дочерние узлы. Номера ячейки в массиве, где хранится родитель можно узнать по индексу ребенка, и наоборот, по индексу дочернего узла можно определить, где записан его родитель.