53446

Операции над бинарными деревьями

Доклад

Информатика, кибернетика и программирование

Бинарное (Двоичное дерево поиска (англ. binary search tree, BST)) дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества

Русский

2014-04-01

22.87 KB

28 чел.

Операции над бинарными деревьями.

Бинарное (Двоичное дерево поиска (англ. binary search tree, BST)) дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются правым и левым поддеревьями исходного дерева.

На рисунке показан наиболее часто встречающийся способ представления бинарного дерева. Оно состоит из девяти узлов. Корнем дерева является узел А. Левое поддерево имеет корень В, а правое поддерево - корень С. Они соединяются соответствующими ветвями, исходящими из А. Отсутствие ветви означает пустое поддерево. Например, у поддерева с корнем С нет левого поддерева, оно пусто. Пусто и правое поддерево с корнем Е. Бинарные поддеревья с корнями D, G, H и I имеют пустые левые и правые поддеревья. Узел, имеющий пустые правое и левое поддеревья, называется листом. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правое и левое поддеревья, то дерево называется строго бинарным. Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку. Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева.

Номер корня всегда равен 1, левый потомок получает номер 2, правый - номер 3. Левый потомок узла 2 должен получить номер 4, а правый - 5, левый потомок узла 3 получит номер 6, правый - 7 и т.д. Несуществующие узлы не нумеруются, что, однако, не нарушает указанного порядка, так как их номера не используются. При такой системе нумерации в дереве каждый узел получает уникальный номер.

Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые правое и левое поддеревья.

Почти полное бинарное дерево определяется как бинарное дерево, для которого существует неотрицательное целое k такое, что:

1) каждый лист в дереве имеет уровень k или k+1;

2) если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.Итак, какие же основные операции определены над деревом? Их несколько:

Поиск узла с заданным ключом. Добавление нового узла. Удаление узла (поддерева). Обход дерева в определенном порядке: Нисходящий обход.

Восходящий обход. Смешанный обход. Поиск глубины.

Бинарное дерево поиска предусматривает операции поиска, вставки и удаления элементов по ключу. Используя эти операции можно построить любое бинарное дерево. Операции вставки, удаления и поиска элементов для бинарного дерева используют правило двоичного поиска при доступе к элементу с заданным значением ключа. Необходимо отметить структурную зависимость бинарного дерева от порядка поступления и удаления элементов. Например, при последовательных вставках элементов со строго возрастающими ключами, структура бинарного дерева выродится в линейный список правых сыновей. Важной операцией для бинарного дерева является перебор его элементов в определенном порядке для выполнения какой–либо операции. Также для BST - дерева используются ряд вспомогательных операций, позволяющих воспроизводить операции, характерные для упорядоченных таблиц поиска: доступ к k - му элементу, поиск следующего или предыдущего по ключу элемента, разбиение таблицы на две части, объединение двух таблиц в одну и другие.

Наиболее часто к бинарным деревьям применяют следующие операции (функции). Если Р указатель на узел U, то: Info(P) - возвращает содержимое узла с указателем Р;

Left(P) - возвращает указатель на левого сына узла с указателем Р;

Right(P) - возвращает указатель на правого сына;

Father(P) - возвращает указатель на отца узла с указателем Р;

Brother(P) - возвращает указатель на брата узла с указателем Р;

IsLeft(P) - возвращает true, если узел с указателем Р - левый сын;

IsRight(P) - возвращает true, если узел с указателем Р - правый сын.

HasChildren (P) - возвращает true, если у узла с указателем P есть потомки;

При создании бинарных деревьев используют функции: MakeTree(X) - создает новое бинарное дерево, состоящее из одного узла с информационным полем Х и возвращает указатель этого узла.

SetLeft(P, X) - где Р - указатель узла U, не имеющего левого сына. Создает новый левый сын узла U с информационным полем Х.

SetRight(P, X) - для правого узла, по аналогии с SetLeft.


 

А также другие работы, которые могут Вас заинтересовать

22793. Напад Німеччини на СРСР та окупація України 30.5 KB
  ОУН. Виникають 2 фракції: ОУНМ А. Мельник; ОУНБ С. ОУН з радістю зустріли німців бо вважали що німці допоможуть створити незалежну У.
22794. Німецько-фашистський окупаційний режим в Україні 37 KB
  На землях південної України між Дністром і Південним Бугом із центром в Одесі утворено Трансністрію яку разом із Північними Буковиною та Бессарабією передано Румунії. Найбільші підприємства України були поділені між німецькими промисловими магнатами. Жодних законів на захист населення окупованої України не існувало. Керівник рейхс комісаріату Україна Еріх Кох заявив своїм підлеглим у вересні 1941 року: Наше завдання полягає в тому щоб вилучити з України все до чого дійдуть наші руки і в цьому ми не звертатимемо жодної уваги на...
22795. Окупаційний режим та Рух Опору в Україні 30.5 KB
  польські організації; сили ОУН . До початку війни ОУН співробітничала з гітлерівцями у німецькій армії був створений Легіон укр. Прагнення ОУН знайти рівновагу між власними інтересами і цілями фашистів не дали результату. ОУНБ починає формувати армію до якої були включені сили ОУНМ та всі розрізнені загони.
22796. Звільнення України від німецько-фашистських загарбників. Політичні наслідки Другої світової війни та українське питання 25.5 KB
  Гітлерівське командування втратило 73 тис. солдатів і офіцерів у тому числі 182 тис. Фашисти втратили 100 тис. солдатів і офіцерів; 615 тис.
22797. Курс на перебудову: плани та реальності його здійснення в Україні 37 KB
  Перш ніж горбачовські реформи дійшли до України тут сталася катастрофа глобального значення: 26 квітня 1986 р. Величезна радіоактивна хмара покрила багато районів України Росії Білорусії а згодом поширилася на землі Польщі та Скандинавії. Постали Українська республіканська партія Демократична партія України партія зелених та ін. На діаметрально протилежних позиціях стояла Комуністична партія України.
22798. Разработка заказной спецификации на аппаратные средства ЭВМ 30.85 KB
  Наличие хорошего сетевого адаптера, встроенного или внешнего; Наличие мощного процессора и видеоадаптера, необходимого для обработки трехмерной графической информации, а так же достаточная емкость ОЗУ.
22799. Визнання Української держави світовим співтовариством. Міжнародне співробітництво незалежної України 31 KB
  Міжнародне співробітництво незалежної України. Важливим кроком в цьому відношенні став робочий візит міністра закордонних справ України Б. Визначною подією в двосторонніх відносинах України з Канадою став офіційний візит до Києва прем’єрміністра Канади Ж. Важливим кроком на шляху підтвердження вірності України європейському вибору поглиблення її відносин з Францією стало проведення 1 березня 1999р.
22800. Походження назви «Україна» та «українці» 41.5 KB
  Походження назви Україна та українці Назва Україна щодо українських земель вперше зустрічається в Київському літописі 1187 р. За тих часів назва Україна поширювалася на Київщину Переяславщину Чернігівщину. Про походження назви Україна існує кілька припущень. Надєждін пояснив значення слова Україна.
22801. Ранній залізний вік на території України 63 KB
  Протягом тисячолітнього існування в Північному Причорномор'ї античні містадержави справили значний вплив на розвиток місцевих племен: скіфів сарматів слов'ян. Етногенез слов’ян. Перші писемні згадки про слов’ян. Існує кілька концепцій походження слов’ян з яких найпоширеніша така: витоки слов'янської історії сягають щонайменше II тис.