115. Двоично дърво за търсене
В двоично дърво за търсене с различни ключове всички ключове в лявото поддърво са по-малки, а тези в дясното са по-големи от ключа във възела. Всяко сравнение избира едно поддърво. Ако при изтриване възелът има едно дете, родителят се свързва с детето. При две деца можем да заместим ключа с най-малкия от дясното поддърво и да премахнем старото му срещане.
Раздел в разширената разработка.
Самостоятелна задача
Условие
Каталогът има корен 8, ляво дете 4 и дясно дете 12. Възел 4 има дясно дете 6. Други възли няма. При търсене започваме от корена. При добавяне следваме същия път и поставяме ключа на първата празна връзка. При изтриване на листо премахваме връзката от родителя. Височина h е максималният брой ребра от корена.
- Кои ключове сравняваме при търсене на 6?
- Къде ще добавим 5?
- В първоначалното дърво коя връзка премахваме при изтриване на 6?
- Колко най-много възела посещава едно търсене при височина h? Какво става при верига от n възела?
Отговори за самопроверка
Отговор 1
8, 4, 6.
Отговор 2
Като ляво дете на 6.
Отговор 3
Дясната връзка от 4.
Отговор 4
Най-много h + 1. При верига h = n − 1, така че в най-лошия случай посещаваме n възела.
Изпълним пример
Програмата извежда посетените ключове. Смени търсения ключ 14 на 15, за да видиш как търсенето приключва, когато стигне празна връзка.
#include <iostream> // Включваме библиотеката, която ни дава cout за печат на екрана.
using namespace std; // Така можем да пишем cout вместо std::cout.
struct Node { // Описваме от какво се състои един възел.
int key; // Пазим числото, по което подреждаме и търсим възлите.
Node* left; // Пазим адреса на лявото дете. Node* е указател към възел.
Node* right; // Пазим адреса на дясното дете.
}; // Край на описанието на типа.
int main() { // Оттук започва изпълнението на програмата.
Node low{3, nullptr, nullptr}; // Създаваме възел с по-малкия ключ. Той няма деца.
Node high{14, nullptr, nullptr}; // Създаваме възел с по-големия ключ. Той няма деца.
Node root{10, &low, &high}; // Задаваме корена и адресите на лявото и дясното му дете.
int key = 14; // Задаваме числото, което търсим.
Node* current = &root; // В current записваме адреса на корена, откъдето започваме търсенето.
while (current != nullptr) { // Повтаряме проверката, докато current сочи към възел.
cout << current->key << '\n'; // Печатаме ключа на възела, който проверяваме в момента.
if (current->key == key) { // С == проверяваме дали текущият ключ е същият като търсения.
cout << "Found\n"; // При съвпадение печатаме, че сме намерили ключа.
return 0; // Приключваме програмата с код 0 за нормален край.
} // Край на действията при изпълнено условие.
if (key < current->key) // Проверяваме дали търсеният ключ е по-малък от текущия.
current = current->left; // Ако е по-малък, местим указателя към лявото дете.
else // Изпълняваме следващия ред, ако проверката в if е невярна.
current = current->right; // Иначе местим указателя към дясното дете.
} // Край на цикъла.
cout << "Missing\n"; // Ако цикълът свърши без съвпадение, печатаме, че ключът липсва.
} // Край на програмата.
В речника Двоично дърво за търсене · Времева сложност.