В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год5Ветка дерева – это произвольная цепочка потомков данного элемента, каждыйследующий элемент в которой является потомком предыдущего. Максимальная длина ветокдерева называется глубиной этого дерева.Одной из основных процедур работы с деревом является процедура обхода дерева. Это– любая процедура, позволяющая побывать в каждой вершине дерева ровно 1 раз.Реализуется она, как правило, рекурсивно. Выделяют следующие виды обходов дерева:1.Обход сверху вниз. При обходе дерева в каждом элементе вначале заходим втекущий элемент, затем обходим потомков текущего элемента2.Обход снизу вверх.

В каждом элементе вначале обходим потомков, затемзаходим в текущий элементДля бинарных деревьев также различают обходы слева направо и справа налево. Припервом вначале обходится левый потомок, затем правый; при втором – наоборот, вначалеправый потомок, затем левый.Добавление элементов в дерево – очевидная операция (просто проставляютсясоответствующие указатели); операция удаления элемента дерева вызывает удаление и всехего потомков (т.е.

в дереве нет специальной операции удаления элемента, есть толькоудаление поддерева).Отдельная разновидность бинарных деревьев – упорядоченные деревья (деревьяпоиска). Бинарное дерево называется упорядоченным, если для любой его вершинывыполняется, что левый потомок «не больше» относительно некоторой операции сравнения,нежели данная вершина, а правый потомок «больше». Такая организация дерева позволяетпроизводить поиск в нем за время, пропорциональное глубине дерева – поиск начинается скорня дерева и на каждом шаге поиска текущий элемент сравнивается с искомым, взависимости от чего происходит переход к левому (если левый больше нашего) или правому(если правый меньше нашего) потомку. Обрывается поиск либо на найденном элементе,либо когда ни влево ни вправо пойти уже нельзя (левый элемент меньше нашего, правый –больше).

Добавляются же элементы в упорядоченное дерево столь же быстро и просто –проводится поиск по данному элементу, если он уже есть в дереве – то он добавляетсялевым потомком этого элемента, а бывший левый потомок найденного элемента становитсялевым потомком уже найденного элемента. Чуть сложнее осуществляется удалениеэлемента из дерева поиска – в упорядоченном дереве (в отличие от произвольногобинарного) определена такая операция. Здесь обычно вначале ищут максимальный элементподдерева левого потомка удаляемого элемента (спускаемся все время вправо, пока этовозможно) и переписывают его значение на место удаляемого элемента, после чего удаляютэтот максимальный элемент из дерева (у него только левые потомки, поэтому это удалениепроисходит очевидно, простой перестановкой ссылок на этот элемент на левого потомкаэтого элемента).Очевидно, чтобы поиск происходил максимально быстро, дерево должно иметьминимально возможную глубину.

Отсюда происходят понятия сбалансированного дерева.(Бинарное) дерево называется идеально сбалансированным, если длины любых двухего ветвей от корня различаются не более чем на 1.Очевидно, что глубина такого дерева -  log 2 N  , где N – количество элементов в дереве.Очевидно также, что поиск в множестве из N элементов не может происходить быстрее, чемlog 2 N - в силу того, что каждое сравнение позволяет разделить множество поиска на 2половинки и, соответственно, проведя h сравнений мы в лучшем случае получим 2 hразличных вариантов ответа алгоритма поиска.

А число ответов при поиске в множестве изN элементов равно N, отсюда получаем, что корректный алгоритм поиска работает за времяЛекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год6h не менее log 2 N . Т.е. поиск в сбалансированном дереве поиска, очевидно, происходитмаксимально быстро – быстрее в общем случае искать невозможно.К сожалению, с идеально сбалансированным деревом работать очень неудобно.Поэтому вводят понятие сбалансированного (бинарного) дерева, в каждой вершинекоторого длины поддеревьев различаются не более, чем на 1.Длина сбалансированного бинарного дерева из N элементов не превосходит 1.5 log 2 N .Действительно, будем строить «худший» пример сбалансированного дерева. Очевидно, еслиу нас в каждой вершине длины левого и правого поддеревьев одинаковы – то это идеальный«сбалансированный» вариант. Каждое изменение сбалансированной вершины нанесбалансированную, очевидно, не уменьшает длину дерева.

Соответственно, худшимвариантом будет тот, в котором все вершины несбалансированны.Пусть N(h) – число элементов в таком худшем дереве глубины h. Очевидно, N(0)=0, N(1)=1 – других вариантов просто быть не может. Для дерева глубины h ясно, чтоN(h) = N(h-1) + N(h-2) + 1 - число элементов равно числу элементов левого и правогоподдеревьев (которые тоже «худшие») плюс сам элемент.Будем искать общую формулу, описывающую ту же последовательность, в видеN  h   a h  1 .

Получаем1 52h1  5 1 5  1 . ОтсюдаОчевидно,не подходит, следовательно имеем N  h  2 2 легковыводится,чтоглубинасбалансированногодеревабольшеlog 2 N 11log  1 5   N 1  1.5 log 2  N 1  1.5 log 2 N 1.441  5 1 5  2 )(т.к.log 2 log 2  2  2 Сбалансированное дерево поиска получается идеальным объектом для поиска помножеству элементов, т.к.

операции добавления, поиска и удаления элементов в нем имеюттрудоемкость порядка O( log 2 N ). Правда, в этом случае приходится отказаться отвозможности хранить в дереве поиска одинаковые элементы (такие элементы образуютдлинные ветки только левых потомков, нарушая сбалансированность), но при поиске помножеству это и не требуется.Баланс элемента дерева – разность между длинами левого и правого поддеревьевДобавление элемента B в сбалансированное дерево происходит следующим образом, в 2этапа: если надо добавить элемент в пустое дерево, то просто записываем этот элемент туда;иначе вначале ищем вершину A, для левого и правого потомков AL и AR котороговыполняется AL<B<AR. В этой вершине запоминаем элемент A и записываем на его местоB, после чего если A<B, то вызываем алгоритм добавления A в поддерево AL, иначевызываем алгоритм добавления A в AR.При этом баланс по дереву может нарушиться.

Нарушение баланса произойдет внекоторой ветке корня дерева. Будем восстанавливать баланс по дереву снизу вверх: пусть унас получилась следующая структура:a h  1  a h1  1  a h  2  1  1  a h  a h 1  a h 2  a 2  a  1  0  a A (n)AR (n-3)B (n-1)BL (n-2)BR (n-3)Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год7(в скобках указана глубина соответствующего поддерева)и BL, BR и AR уже сбалансированы, то применим L1-перестройкуB (n-1)A (n-2)BL (n-2)AR (n-3)BR (n-3)уменьшающую глубину поддерева на 1 и делающего его сбалансированным. При этомменяется баланс только в вершинах той же ветки, баланс в которой изменился придобавлении элемента.

Ясно, что баланс может только восстановиться снизу вверх по этойветке, вплоть до вершины, в которой он либо не восстановится, либо «испортится» - вышецепочка изменений не пойдет. Соответственно далее восстановим баланс в этой вершине ит.д.Возможны также случаи:A (n)AR (n-3)B (n-1)BL (n-2)BR (n-2)- здесь также применяется перестройка L1B (n)A (n-1)BL (n-2)BR (n-2)AR (n-3)сохраняющая длину поддерева и снова восстанавливающую балансЛекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год8Еще один возможный случайA (n)AR (n-3)B (n-1)BL (n-3)C (n-2)CL (x)CR (y)Здесь x или y = n-3, и x или y может быть n-4В этом случае приходится применять перестройку L2:C (n-1)A (n-2)B (n-2)BL (n-3)CL (x)CR (y)AR (n-3)тоже, очевидно, восстанавливающую баланс и уменьшающую длину дерева на 1.Аналогично строятся перестановки R1 и R2.С помощью этих 4х перестановок удается восстановить баланс за время непревосходящее глубину дерева.Удаление элементов дерева производится аналогичным способом – удалениеописанным ранее для дерева поиска способом элемента дерева тоже «портит» баланс неболее чем на 1 в какой-то ветке дерева и с помощью перестроек L1-L2-R1-R2 можновосстановить этот баланс по дереву.Вместо сбалансированных деревьев поиска используются также красно-черные деревья(red-black tree).

Характеристики

Список файлов лекций