Вилучення з дерева елемента коли в нього не більше одного сина

Вилучення з дерева елемента коли в нього два сина

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

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

356.00K

Категория:

Программирование

Похожие презентации:

Дерева бінарного пошуку

Бінарні дерева

Рекурсія

Абстрактні типи даних

Об’єктно-зорієнтоване програмування на С#

Графи. Частина 2

Абстрактні типи даних. (Розділ 3)

Рекурсія. Активізація та запис оперативної пам'яті. Лекция 19

Лінійні списки. Методи зберігання. Операції

Масиви

Дерева (1)

1. Дерева бінарного пошуку

2. Дерева бінарного пошуку

Дерево бінарного пошуку - бінарне дерево,
кожний вузол якого v відмічений значенням l(v)
так що:
l(u) < l(v) для кожного вузла u з лівого
піддерева вузла v;
l(u) > l(v) для кожного вузла u з правого
піддерева вузла v.
Властивість: відмітки вузлів бінарного
дерева, що взяті в симетричному порядку
утворюють впорядковану послідовність.

3. Дерево бінарного пошуку

h
c
a
d
b
g
e
<a, b, c, d, e, f, g, h>
f

4. Дерево бінарного пошуку

Розглянемо основні дії з деревом бінарного
пошуку:
вставка вузла у дерево бінарного пошуку;
пошук вузла за ключовим значенням;
обхід дерева з ліва на право;
обхід дерева з верху в низ;
обхід дерева з низу в верх;
вилучення вузла з дерева бінарного пошуку;
пошук найменшого значення;

5.

Дерево бінарного пошуку
Реалізація
Tree
з
операціями
структури
основними
struct Tree
{
private:
struct Node
{
int value; // The value in the node
Node * left; // Pointer to left child node
Node * right; // Pointer to right child
node
};
Node * root; // Pointer to the root node
// Private member functions
void insert(Node*&, Node*&);
void destroySubTree(Node*);
void deleteNode(int, Node*&);
void makeDeletion(Node*&);
void displayInOrder(Node*);
void displayPreOrder(Node*);
void displayPostOrder(Node*);
int FindMin(Node*);
public:
// Constructor
Tree()
{ root = nullptr; }
// Destructor
~Tree()
{ destroySubTree(root);}
// Binary tree operations
void insertNode(int);
bool searchNode(int);
void remove(int);
void displayInOrder()
{ displayInOrder(root); }
void displayPreOrder()
{ displayPreOrder(root); }
void displayPostOrder()
{ displayPostOrder(root); }
int Min();
};

6. Вставка в дерево бінарного пошуку

Вхід: дерево Т й значення v.
Задача: додати вузол із значенням v в дерево Т
(якщо такий вузол відсутній).
Алгоритм:
Якщо дерево порожньо, замінити його на дерево з
одним кореневим вузлом.
Інакше порівняти v із значенням вузла x.
Якщо v<x, рекурсивно додати v в ліве піддерево Т.
Якщо v>=x, рекурсивно додати v в праве піддерево Т.

7. Вставка в дерево бінарного пошуку

8. Вставка в дерево бінарного пошуку

void Tree::insertNode(int num)
{
Node * newNode = nullptr; // Pointer to a new node.
// Create a new node and store num in it.
newNode = new Node;
newNode->value = num;
newNode->left = newNode->right = nullptr;
// Insert the node.
insert(root, newNode);
}
void Tree::insert(Node*& nodePtr, Node*& newNode)
{
if (nodePtr == nullptr)
nodePtr = newNode; // Insert the node.
else if (newNode->value < nodePtr->value)
insert(nodePtr->left, newNode); // Search the left branch.
else
insert(nodePtr->right, newNode); // Search the right branch.
}

9. Обхід дерева з ліва на право

Вивід (обхід) дерева на екран реалізовано рекурсивно в функції displayInOrder.
Принцип такий: Спочатку виводиться ліве піддерево, потім його корінь, а потім праве піддерево
void displayInOrder()
{
displayInOrder(root);
}
void Tree::displayInOrder(Node * nodePtr)
{
if (nodePtr)
{
displayInOrder(nodePtr->left);
cout << nodePtr->value << endl;
displayInOrder(nodePtr->right);
}
}

10. Обхід дерева з ліва на право

Використання обходу дерева в основній програмі:
int main()
{
Tree tree;
// Insert some nodes.
cout << "Inserting nodes.\n";
tree.insertNode(5);
tree.insertNode(8);
tree.insertNode(3);
tree.insertNode(12);
tree.insertNode(9);
tree.displayInOrder();
}

11. Обхід дерева з верху в низ

Вивід (обхід) дерева на екран реалізовано рекурсивно в функції displayPreOrder
Принцип такий: Спочатку виводиться корінь, потім його ліве піддерево, а потім праве піддерево
void displayPreOrder()
{
displayPreOrder(root);
}
void Tree::displayPreOrder(Node * nodePtr)
{
if (nodePtr)
{
cout << nodePtr->value << endl;
displayPreOrder(nodePtr->left);
displayPreOrder(nodePtr->right);
}
}

12. Обхід дерева з верху в низ

13. Обхід дерева з низу в верх

Вивід (обхід) дерева на екран реалізовано рекурсивно в функції displayPostOrder.
Принцип такий: Спочатку виводиться ліве піддерево, потім праве піддерево, а потім їх корінь
void displayPostOrder()
{
displayPostOrder(root);
}
void Tree::displayPostOrder(Node * nodePtr)
{
if (nodePtr)
{
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout << nodePtr->value << endl;
}
}

14. Обхід дерева з низу в верх

15. Пошук у дереві бінарного пошуку

Cтруктура Tree має функцію-член searchNode, яка повертає true якщо значення
знайдено в дереві, або false в іншому випадку.
bool Tree::searchNode(int num)
{
Node * nodePtr = root;
while (nodePtr)
{
if (nodePtr->value == num)
return true;
else if (num < nodePtr->value)
nodePtr = nodePtr->left;
else
nodePtr = nodePtr->right;
}
return false;
}

16. Пошук у дереві бінарного пошуку

Використання бінарного дерева в основній програмі:
int main()
{
Tree tree;
// Insert some nodes.
cout << "Inserting nodes.\n";
tree.insertNode(5);
tree.insertNode(8);
tree.insertNode(3);
tree.insertNode(12);
tree.insertNode(9);
// Search for the value 3.
if (tree.searchNode(3))
cout << "3 is found in the tree.\n";
else
cout << "3 was not found in the tree.\n";
// Search for the value 100.
if (tree.searchNode(100))
cout << "100 is found in the tree.\n";
else
cout << "100 was not found in the tree.\n";
}

17. Пошук найменшого значення

int Tree::Min()
{
if(root !=nullptr)
return FindMin(root);
else
{
cout << "Free Tree.\n";
return -1;
}
}
int Tree::FindMin(Node* nodePtr)
{
if (nodePtr->left)
return FindMin(nodePtr->left);
return nodePtr->value;
}

18. Пошук найменшого значення

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

Вхід: дерево Т й ключ v.
Задача: вилучити з дерева Т вузол із значенням v.
Алгоритм:
Якщо дерево T порожнє, зупинитись;
Інакше порівняти v з значенням x кореневого вузла.
Якщо v>x, рекурсивно вилучити v з правого піддерева Т;
Якщо v<x, рекурсивно вилучити v з лівого піддерева Т;
Якщо v=x, то необхідно розглянути два випадки.
Якщо вузол має не більше одного сина його вилучаємо;
Якщо вузол має двох синів, то
Знайдемо вузол із значенням y, що йому безпосередньо
передує у симетричному обході, здійснюємо заміну v←y й
вилучаємо вузол зі значенням y.

20. Вилучення з дерева елемента коли в нього не більше одного сина

21. Вилучення з дерева елемента коли в нього не більше одного сина

22. Вилучення з дерева елемента коли в нього два сина

23. Вилучення з дерева елемента коли в нього два сина

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

void Tree::remove(int num)
{
deleteNode(num, root);
}
void Tree::deleteNode(int num, Node*&
nodePtr)
{
if (num < nodePtr->value)
deleteNode(num, nodePtr->left);
else if (num > nodePtr->value)
deleteNode(num, nodePtr->right);
else
makeDeletion(nodePtr);
}
void Tree::makeDeletion(Node*& nodePtr)
{
// Define a temporary pointer to use in reattaching
// the left subtree.
Node * tempNodePtr = nullptr;
if (nodePtr == nullptr)
cout << "Cannot delete empty node.\n";
else if (nodePtr->right == nullptr)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->left; // Reattach the left child.
delete tempNodePtr;
}
else if (nodePtr->left == nullptr)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->right; // Reattach the right
child.
delete tempNodePtr;
}
// If the node has two children.
else
{
// Move one node to the right.
tempNodePtr = nodePtr->right;
// Go to the end left node.
while (tempNodePtr->left)
tempNodePtr = tempNodePtr->left;
// Reattach the left subtree.
tempNodePtr->left = nodePtr->left;
tempNodePtr = nodePtr;
// Reattach the right subtree.
nodePtr = nodePtr->right;
delete tempNodePtr;
}
}

25. Вилучення з дерева бінарного пошуку елемента зі значенням 3

int main()
{
Tree tree;
// Insert some nodes.
cout << "Inserting nodes.\n";
tree.insertNode(5);
tree.insertNode(9);
tree.insertNode(3);
tree.insertNode(1);
tree.insertNode(4);
tree.insertNode(12);
// Display the values.
cout << "Here are the values in the tree:\n";
tree.displayInOrder();
// Delete the value 3.
cout << "Deleting 3...\n";
tree.remove(3);
// Display the values.
cout << "Now, here are the nodes:\n";
tree.displayInOrder();
}

26. Вилучення з дерева бінарного пошуку елемента зі значенням 9

int main()
{
Tree tree;
// Insert some nodes.
cout << "Inserting nodes.\n";
tree.insertNode(5);
tree.insertNode(9);
tree.insertNode(3);
tree.insertNode(1);
tree.insertNode(4);
tree.insertNode(12);
// Display the values.
cout << "Here are the values in the tree:\n";
tree.displayInOrder();
// Delete the value 9.
cout << "Deleting 9...\n";
tree.remove(9);
// Display the values.
cout << "Now, here are the nodes:\n";
tree.displayInOrder();
}

27. Реалізація деструктора

void Tree::destroySubTree(Node * nodePtr)
{
if (nodePtr)
{
if (nodePtr->left)
destroySubTree(nodePtr->left);
if (nodePtr->right)
destroySubTree(nodePtr->right);
}
delete nodePtr;
}

28. Підсумки

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

29. Домашнє завдання

Написати функції для визначення найбільшого
значення у вузлах непорожнього дерева
бінарного пошуку.
Задана послідовність цілих чисел a1, a2, …, an .
Написати програму модифікації дерева бінарного
пошуку B, спочатку порожнього, за умовами:
– якщо ai>0 , то додати ai в B;
– якщо ai<0 , то вилучити -ai з B (при відсутності
видається повідомлення);
– якщо ai=0 , то закінчити виконання програми.

English Русский Правила