1. Серія контенту:
2. Цей контент є частиною серії: Робота зі структурами даних в мовах Сі та Python
3. Бінарні пошукові дерева
4. Малюнок 1. Два варіанти подання бінарного пошукового дерева
5. Лістинг 1. Визначення структур для представлення дерева і його вузлів
6. Лістинг 2. Функція для створення дерева
7. Вставка вузла в бінарне пошукове дерево
8. Лістинг 3. Функція для пошуку вузла в дереві
9. Лістинг 4. Функція для вставки вузла в бінарне пошукове дерево
10. Видалення вузла з бінарного пошукового дерева
11. Малюнок 2. Три варіанти видалення елемента з бінарного пошукового дерева
12. Лістинг 5. Функція для видалення вузла з бінарного пошукового дерева
13. Прохід по дереву
14. Лістинг 6. Функції для виведення вмісту дерева
15. Лістинг 8. нерекурсівние реалізація обходу дерева
16. видалення дерева
17. Лістинг 9. Функції для видалення дерева
18. Знаходження мінімуму і максимуму в бінарному пошуковому дереві
19. Лістинг 10. Функції для пошуку мінімального і максимальних значень
20. Визначення типу двійкового дерева
21. Лістинг 11. Визначення типу двійкового дерева
22. Практична реалізація алгоритмів
23. висновок
24. Ресурси для скачування

Робота зі структурами даних в мовах Сі та Python

Серія контенту:

Цей контент є частиною # з серії # статей: Робота зі структурами даних в мовах Сі та Python

https://www.ibm.com/developerworks/ru/library/?series_title_by=**auto**

Слідкуйте за виходом нових статей цієї серії.

Цей контент є частиною серії: Робота зі структурами даних в мовах Сі та Python

Слідкуйте за виходом нових статей цієї серії.

Ця стаття присвячена одній з різновидів довічних дерев: бінарним пошуковим деревам. Як завжди будуть розглянуті теоретичні алгоритми для виконання різних операцій: вставка і видалення вузла, пошук максимуму / мінімуму і практичні реалізації даних алгоритмів на мовах Сі та Python.

Бінарні пошукові дерева

Бінарні пошукові дерева (англ. Binary search tree або скорочено BST) - це різновид двійкового дерева, що володіє наступними відмітними властивостями:

1. для кожного вузла X (якщо X НЕ дорівнює NULL) всі вузли в його лівому поддереве містять значення, які ЗАВЖДИ менше значення вузла X.
2. всі вузли в правому піддереві вузла Х містять значення, які відповідно ЗАВЖДИ більше значення вузла X.
3. кожен вузол в такому дереві є батьком для своїх піддерев.

Перевага довічного пошукового дерева в тому, що всі значення розташовуються в ньому в відсортованому порядку. У загальному випадку вузли необов'язково повинні піддаватися сортування перед вставкою в бінарне пошукове дерево. Вузли можуть вставлятися в таке дерево в довільному порядку, а сама сортування може відбуватися в процесі вставки.

Результат вставки вузлів в бінарне пошукове дерево може виявитися непередбачуваним. Якщо вставляти в таке дерево вузли, які вже були попередньо відсортовані, то це призведе до виродження дерева. На малюнку 1 показані дві однакові за змістом реалізації пошукового дерева, але з різними кореневими вузлами.

Малюнок 1. Два варіанти подання бінарного пошукового дерева

У лістингу 1 наведено оголошення структур для вузла бінарного дерева і самого дерева на мові Сі.

Лістинг 1. Визначення структур для представлення дерева і його вузлів

struct node {int data; struct node * left; struct node * right; }; struct tree {struct node * root; // покажчик на корінь дерева int count; // кількість вузлів в дереві};

Структура, що використовується для опису вузла дерева, повністю збігається зі структурою, що використовується для опису зв'язного списку. Використовуючи ці дві структури можна підготувати функцію на мові Сі для створення дерева (див. Лістинг 2).

Лістинг 2. Функція для створення дерева

struct tree * tree_create (void) {struct tree * new_tree = malloc (sizeof * new_tree); if (new_tree == NULL) return NULL; new_tree-> root = NULL; new_tree-> count = 0; return new_tree; }

Вставка вузла в бінарне пошукове дерево

Перед вставкою нового елемента в бінарне дерево обов'язково потрібно перевірити, чи немає в ньому вже такого елемента. Для цього необхідно почати обхід дерева з кореневого вузла і перевірити, чи не перевершує чи значення кореневого вузла додається значення. Якщо кореневий вузол більше додається елемента, то необхідно переміститися в ліве дочірнє дерево. В іншому випадку - в праве. Функція пошуку певного вузла в дереві, наведена в лістингу 3, поверне 1 в разі, якщо шукане значення буде знайдено, або 0, якщо вказане значення в дереві відсутня.

Лістинг 3. Функція для пошуку вузла в дереві

int bin_search (const struct tree * search_tree, int item) {const struct node * search_node; search_node = search_tree-> root; for (;;) {if (search_node == NULL) return 0; else if (item == search_node-> data) return 1; else if (item> search_node-> data) search_node = search_node-> right; else search_node = search_node-> left; }}

Після виконання даної перевірки можна переходити до додавання вузла в бінарне дерево. Функція вставки аналогічна функції пошуку: необхідно пройти по дереву і вставити вузол в потрібне місце. Для цього слід вибрати ліве або праве піддерево кореневого вузла, а потім рекурсивно переміщатися по обраному Піддерево до тих пір, поки не буде знайдена позиція для вставки вузла, як показано в лістингу 4.

Лістинг 4. Функція для вставки вузла в бінарне пошукове дерево

int insert (struct tree * search_tree, int item) {struct node * search_node, ** new; new = & search_tree-> root; search_node = search_tree-> root; for (;;) {if (search_node == NULL) {search_node = * new = malloc (sizeof * search_node); if (search_node! = NULL) {search_node-> data = item; search_node-> left = search_node-> right = NULL; search_tree-> count ++; return 1; } Else return 0; } Else if (item == search_node-> data) return 2; else if (item> search_node-> data) {new = & search_node-> right; search_node = search_node-> right; } Else {new = & search_node-> left; search_node = search_node-> left; }}}

Елемент, доданий першим, автоматично стає коренем дерева. Функція може повернути одне з 3-х значень: 0 (при вставці сталася помилка), 1 (вузол успішно вставлений), 2 (такий елемент вже є в дереві).

Видалення вузла з бінарного пошукового дерева

Функція видалення вузла з бінарного дерева також буде повертати 0, якщо виникла помилка, або 1 в разі вдалого видалення елемента. У даній функції використовується вже знайомий алгоритм пошуку, який буде шукати елемент, позначений для видалення. Після того, як цей елемент буде виявлений, можливі 3 варіанти дій, які представлені на малюнку 2.

Малюнок 2. Три варіанти видалення елемента з бінарного пошукового дерева

У першому випадку (варіант a) вузол z має тільки лівий дочірній вузол, і при видаленні він і буде замінений ім. У другому варіанті (рисунок b) вузол z замінюється вузлом y.

У третьому варіанті (рисунок с) кореневої вузол z замінюється вузлом x, що призводить до додаткових перестроювання в правому піддереві. Вузол x стає наступником вузла z, так як в лівому поддереве вузла z все вузли менше 5, і наступника потрібно шукати в правому піддереві вузла z.

Лістинг 5. Функція для видалення вузла з бінарного пошукового дерева

int delete (struct tree * search_tree, int ** item) {struct node ** q, * z; q = & search_tree-> root; z = search_tree-> root; // пошук видаляється елемента for (;;) {if (z == NULL) return 0; else if (item == (int **) z-> data) break; else if (item> (int **) z-> data) {q = & z-> right; z = z-> right; } Else {q = & z-> left; z = z-> left; }} // безпосереднє видалення елемента if (z-> right == NULL) * q = z-> left; else {struct node * y = z-> right; if (y-> left == NULL) {y-> left = z-> left; * Qy; } Else {struct node * x = y-> left; while (x-> left! = NULL) {y = x; x = y-> left; } Y-> left = x-> right; x-> left = z-> left; x-> right = z-> right; * Q = x; }} Search_tree-> count -; free (z); return 1; }

Прохід по дереву

Для проходу по дереву можна використовувати рекурсію, так як будь-який двоичное дерево - це рекурсивна структура. Функції, наведені в лістингу 6, можуть роздрукувати дерево, починаючи з будь-якого вузла: спочатку друкується ліве піддерево, потім праве.

Лістинг 6. Функції для виведення вмісту дерева

// функція для роздруківки фрагмента дерева - з будь-якого вузла static void walk (const struct node * search_node) {if (node ​​== NDLL) return; walk (node-> left); printf ( "% d", search_node-> data); walk (node-> right); } // функція для роздруківки дерева цілком - з кореня void walk2 (const struct tree * my_tree) {walk (my_tree-> root); }

Для проходу по дереву можна обійтися і однією функцією, якщо ввести масив покажчиків на вузли, який буде заповнюватися під час проходу. У функції буде виконуватися вкладений цикл для проходу дерева від поточного вузла вліво до кінця. А додатковий масив допоможе обійти всі дерево за один прохід, так як в ньому буде зберігатися покажчик на поточний кореневий вузол.

Лістинг 8. нерекурсівние реалізація обходу дерева

void traverse (const struct tree * search_tree) {struct node * stack [32]; int count; struct node * search_node; count = 0; search_node = search_tree-> root; for (;;) {while (search_node! = NOLL) {stack [count ++] = search_node; search_node = search_node-> left; } If (count == 0) return; search_node = stack [-count]; printf ( "% d", search_node-> data); search_node = search_node-> right; }}

У лістингу 8 присутня навмисне спрощення, так як в ньому використовується спрощений статичний варіант стека, хоча в реальній ситуації пам'ять під стек обов'язково повинна виділятися динамічно.

видалення дерева

У цьому розділі наведені функції для повного видалення дерева, починаючи з листя і закінчуючи кореневих вузлом.

Лістинг 9. Функції для видалення дерева

// функція для видалення окремого вузла дерева і його нащадків static void destroy (struct node * search_node) {if (search_node == NOLL) return; destroy (search_node-> left); destroy (search_node-> right); free (search_node); } // функція для повного видалення дерева void destroy (struct tree * search_tree) {destroy (search_tree-> root); free (search_tree); }

Знаходження мінімуму і максимуму в бінарному пошуковому дереві

У лістингу 10 наведено дві функції для пошуку в дереві вузлів з мінімальним і максимальним значенням. Мінімальне значення потрібно шукати в лівому піддереві кореневого елемента, а максимальне - у правому.

Лістинг 10. Функції для пошуку мінімального і максимальних значень

struct node * tree_minimum (struct tree * search_tree) {struct node * search_node; search_node = search_tree-> root; while (search_node-> left! = NULL) search_node = search_node-> left; return search_node; } Struct node * tree_maximum (struct tree * search_tree) {struct node * search_node; search_node = search_tree-> root; while (search_node-> right! = NULL) search_node = search_node-> right; return search_node; }

Визначення типу двійкового дерева

Щоб визначити чи відноситься дана двоичное дерево до пошукових бінарним деревам, можна використовувати функцію з лістингу 11.

Лістинг 11. Визначення типу двійкового дерева

int isBST (struct node * node) {return (isBSTUtil (node, INT_MIN, INT_MAX)); } Int isBSTUtil (struct node * node, int min, int max) {if (node ​​== NULL) return (true); if (node-> data <min || node-> data> max) return (false); return (isBSTUtil (node-> left, min, node-> data) && isBSTUtil (node-> right, node-> data + 1, max)); }

Практична реалізація алгоритмів

У файлі sources.zip, прикріпленому до даної статті, знаходяться дві програми, в яких використовуються описані вище алгоритми для обробки бінарного пошукового дерева. У файлі bst_operations.с знаходиться реалізація на мові Сі, а файл bst_operations.py містить реалізацію на мові Python.

Програма на мові Сі має більшу функціональність, ніж версія на Python. У Сі-програмі спочатку створюється бінарне пошукове дію з 10 вузлів, потім вміст дерева роздруковується, і з нього видаляється один вузол. Після цього виконується ще одна роздруківка, щоб перевірити, як пройшло видалення, і дерево видаляється вже повністю зі звільненням пам'яті. В Python-програмі виконується тільки створення і роздруківка бінарного пошукового дерева з 10 вузлів. Решта алгоритми залишилися нереалізованими, але їх можна розробити самостійно, використовуючи версії на мові Сі в якості зразка.

висновок

У даній статті були розглянуті основні алгоритми, що використовуються для роботи з однією з найпопулярніших структур даних - бінарним пошуковим деревом. Крім теоретичних описів в статті були представлені і практичні реалізації даних алгоритмів на мові програмування Сі. Для кращого засвоєння матеріалу читачеві пропонується самостійно розробити реалізацію цих алгоритмів на мові Python і вирішити такі завдання:

1. якщо вставити в бінарне пошукове дерево числа в діапазоні від 1 до 64 в порядку зростання таким чином, що спочатку вставляються непарні числа, потім парні, то якою буде висота цього дерева?
2. якщо спочатку вставити 3 числа: 32, 16, 48, а потім всі інші в колишньому порядку, то якою буде висота цього дерева?

Ресурси для скачування

Схожі теми

• Робота зі структурами даних в мовах Сі та Python. Частина 1 .
• Робота зі структурами даних в мовах Сі та Python. Частина 2 .
• Робота зі структурами даних в мовах Сі та Python. частина 3 .
• Робота зі структурами даних в мовах Сі та Python. частина 4 .
• Робота зі структурами даних в мовах Сі та Python. частина 5 .
• Робота зі структурами даних в мовах Сі та Python. частина 6 .
• Робота зі структурами даних в мовах Сі та Python. частина 7 .

Підпишіть мене на повідомлення до коментарів