Самостоятельная работа-2 Студент: 3 курс Группа: ки-12-20(С)(Р)

САМОСТОЯТЕЛЬНАЯ РАБОТА-2

Студент: 3 - курс
Группа: КИ-12-20(С)(Р)
Подготовил: Б.БОКИЕВ Принял: А.М.БОЙТЕМИРОВ 
Темы:


Сбалансированные бинарные деревья

Критерий идеальной сбалансированности дерева. Дерево называется идеально сбалансированным, если все его уровни, за исключением, может быть, последнего, полностью заполнены. (В бинарном дереве полностью заполненный уровень n содержит 2n узлов).

Если дерево поиска близко к сбалансированному, то даже в худшем случае за время порядка O(log2n) в нем можно:

1. 
   Найти вершину с заданным значением или выяснить, что такой вершины нет.
   
2. 
   Включить новую вершину.
   
3. 
   Исключить вершину.
   

Среднее время выполнения этих операций будет также близким к O(log2n), так как в идеально сбалансированном дереве при полностью заполненных уровнях на последнем уровне находится больше половины узлов дерева. Например, последовательность значений 4, 6, 2, 1, 5, 3, 7 дает следующее идеально сбалансированное дерево:

В этом дереве 7 узлов, на последнем уровне находится 4 узла. Если доступ к одному узлу требует 1 единицу времени, то до узла <4> можно добраться за 1 единицу времени, до <2> и <6> - за 2, до <1>, <3>, <5>, <7> - за 3. То есть в худшем случае требуется 3 единицы времени, в среднем: (1+2*2+3*4)/7 = 2.4 единицы времени.
Однако значения в последовательности могут идти и в другом порядке, что может привести к построению несбалансированного дерева. В худшем случае можно получить вырожденное дерево, подобное линейному списку. Например, последовательность значений 1, 7, 2, 6, 3, 5, 4 дает следующее вырожденное дерево:

Работа с таким вырожденным деревом потребует в худшем случае 7 единиц времени (доступ к <4>), а в среднем: (1+2+3+4+5+6+7)/7 = 4 единицы времени. То есть для вырожденного дерева затраты на доступ к узлам в худшем случае имеют порядок O(n), в среднем - O(n/2).
Разница во времени доступа будет гораздо заметнее при большем числе узлов. Например, в идеально сбалансированном дереве из 1023 узлов время доступа в худшем случае будет равно 10 единицам времени, в среднем:
единицам времени.
А в вырожденном дереве из 1023 узлов потребуется в худшем случае 1023 единицы времени, в среднем - 512 единиц времени.
Поэтому при работе с деревьями поиска больших размеров крайне желательно, чтобы они были близки к сбалансированным.
Приведение уже существующего дерева к идеально сбалансированному - процесс сложный. Проще балансировать дерево в процессе его роста (после включения каждого узла). Однако требование идеальной сбалансированности делает и этот процесс достаточно сложным, способным затрагивать все узлы дерева.