Я хочу вставить 7 элементов в свое дерево -3, -2, -1, 0, 1, 2 и 3. Я получаю хорошо сбалансированное дерево высоты 3 без поворотов, когда я вставляю в следующем порядке: 0, -2, 2, -1, 1, -3, 3. Но когда я вставляю все элементы в порядке возрастания, правая часть корневого узла выполняет перебалансировку, а левая часть корневого узла - нет. Все алгоритмы перебалансировки, которые я видел, выполняют перебалансировку от вставленного узла до корневого узла, а затем останавливаются. Разве они не должны продолжаться до противоположной части корневого узла? И у меня такое чувство, что становится хуже, если я вставляю много элементов в порядке возрастания (например, от 0 до 100). В конце дерево сбалансировано, но не оптимизировано по высоте.
Ребалансировка красных черных деревьев
Ответы (1)
Ни одно из сбалансированных деревьев бинарного поиска (R/B-деревьев, AVL-деревьев и т. д.) не обеспечивает абсолютной балансировки, то есть ни одно из них не обеспечивает минимально возможную высоту. Это потому, что такую «полную» перебалансировку быстро сделать невозможно. Если мы хотим всегда поддерживать минимально возможную высоту, часто потребуется тяжелая перебалансировка для операций с деревьями, и поэтому перебалансировка не будет работать в O(log N). В результате все операции (вставка, обновление, удаление и т.д.) тоже не будут выполняться за O(log N) времени, а это разрушит всю идею сбалансированного дерева.
Что делают сбалансированные деревья, гарантируют не столь строгое требование к высоте дерева: высота дерева равна O(log N), то есть C*log N для некоторой константы C. Так что идеально сбалансированное дерево не гарантируется, но баланс всегда будет недалек от идеального.
person
Petr
schedule
28.05.2015
Я добавил 1000 элементов в порядке возрастания и получил высоту 16! Выглядит неплохо, даже если дерево не сбалансировано на 100%.
- person Kouros; 28.05.2015
