Pull to refresh

AVL деревья и широта их применения

Search engines *
Решил немного описать на мой взгляд самую полезную древовидную структуру. AVL дерево это бинарное дерево (у каждой вершины не более 2 сыновей), в котором каждой вершине присвоен идентификатор (как раз его и хранит дерево), идентификаторы подчиняются следующему правилу: ID левого сына<ID родителя<ID правого сына.
Т.е. если обходить дерево рекурсивно слева направо получим отсортированный по возрастанию список ID, справа налево – по убыванию.
Причем дерево максимально сбалансировано: высота левого поддерева отличается от высоты правого максимум на 1.

Интересно в нем то, что тогда на проверку существования элемента в дереве уходит log(N) N – количество ID. Ведь надо пройти от корня вниз, а поскольку дерево максимально симметрично то его высота — log(N)+1
Хорошая новость – нам никто не запрещает прикрепить к вершине еще какие-то полезные данные и тогда выборка произвольных данных по ID будет занимать log(N) времени
Плохая новость – одинаковые ID как следует из определения в нем существовать не могут. Придется делать финт ушами, один способ сделать вместо каждой вершины список вершин с одинаковым ID, другой – изменить алгоритм балансировки.
Читать дальше →
Total votes 23: ↑18 and ↓5 +13
Views 8.4K
Comments 9

Структуры данных LinkedList и TreeMap для JavaScript

Open source *JavaScript *

Развитие языка JavaScript постепенно переносит всю тяжесть вычислений с одного сервера на сеть пользовательских компьютеров. Это супер-хорошо. Программирование на стороне сервера вынуждало очень тщательно оптимизировать код по быстродействию и занимаемой памяти, в то же время разработка клиентской части несколько отставала.

Для удобного и быстрого кодирования можно применять структуры данных. Именно так и поступают при разработке на Java:

https://habr.com/ru/post/237043/

А вот для аналогичной работы с JavaScript оптимизированных инструментов по умолчанию не предоставляется. Реализация Array(), Set() и Map() перекладывается на сторонних разработчиков браузерных движков, а их разработки на сегодняшний день далеки от оптимальности:

https://habr.com/ru/company/ruvds/blog/518032/

Зададимся вопросом — а что если требуются прямо сейчас оптимальные по производительности и памяти структуры данных. Какой минимальный набор достаточно оптимальных структур реализовать и поддерживать? Один из вариантов ответа — это сделать двунаправленный связный список и сбалансированное дерево поиска.

Что это нам даст?

Реализуя связный список LinkedList мы получаем сразу список, двунаправленную очередь и стек. И если это сделать без JavaScript Array(), а лишь используя простые ссылки на объекты, то получаем стандартную и достаточно оптимальную структуру данных.

Если же сделать бинарное сбалансированное дерево поиска TreeMap, например AVL-дерево:

https://habr.com/ru/post/150732/

тогда используя эту реализацию можно получить следующие структуры данных:

Читать далее
Total votes 5: ↑3 and ↓2 +1
Views 3.8K
Comments 13