Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






ДЕРЕВО ПОИСКА. ОСНОВНЫЕ ОПЕРАЦИИ, ВЫЧИСЛЕНИЕ СРЕДНЕЙ ДЛИНЫ ПУТИ.




 

Дерево поиска – все вершины в правом поддереве > x (вершина), все вершины в левом поддереве < x.

В дереве поиска можно найти любой ключ, стартуя с корня и спускаясь в левое или правое поддерево в зависимости только от ключа в текущем узле. Если дерево идеально сбалансировано, то поиск среди n элементов можно выполнить за О(logn). Этим деревья поиска выгодно отличаются от линейных списков.

Операции:

Обход дерева

Обход дерева можно совершать тремя способами:

1. A,L,R(префиксный обход)

2. L,A,R (инфиксный обход)

3. L,R,A (постфиксный обход)

 

(подробно см. пункт 12)

Поиск вершины

Использование двоичного дерева поиска позволит найти искомую вершину за О(logn), причем высота дерева составляет log2n.

Добавление

Данная операция соотносится с операцией поиска и они объединяются в одну – поиска-включения. При этом минимальной время – O(log2n), максимальное - O(n). Аналогом по быстродействию является быстрая сортировка и поиск медианы в ней.

Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.

Иначе сравнить K с ключом корневого узла X.

§ Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.

§ Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.

Удаление

Если дерево T пусто, остановиться;

В остальном различают 3 случая:

· Отсутствует компонента с ключом, равным х.

· У компоненты с ключом х не более 1 потомка.

· У компоненты с ключом х 2 потомка. В этой ситуации элемент должен быть заменен либо на самый правый элемент левого поддерева, либо на самый левый элемент правого поддерева.

Вычисление средней длины пути в дереве поиска:

Пусть вершины пронумерованы от 1 до n

– средняя длина пути

             
     
 
   
n-i вершин  
 
 

 


– левое поддерево, правое поддерево, корень

а) Преобразуем

б) сумму считаем до (n-1)

(1)

(2) умнож. на

Подставляем (2) в (1)

Тогда

По индукции можно доказать следующее

- при больших n последнее слагаемое опускаем

В среднем случае длина пути случайного дерева отличается от длины пути в идеально сбалансированном на 38%, в большинстве случаев это не критично, но если задача связана с максимально быстрым поиском, то нужно строить идеально сбалансированное.

 

 




Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2019 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных