115. Двоично дърво за търсене

В двоично дърво за търсене с различни ключове всички ключове в лявото поддърво са по-малки, а тези в дясното са по-големи от ключа във възела. Всяко сравнение избира едно поддърво. Ако при изтриване възелът има едно дете, родителят се свързва с детето. При две деца можем да заместим ключа с най-малкия от дясното поддърво и да премахнем старото му срещане.

Раздел в разширената разработка.

Самостоятелна задача

Условие

Каталогът има корен 8, ляво дете 4 и дясно дете 12. Възел 4 има дясно дете 6. Други възли няма. При търсене започваме от корена. При добавяне следваме същия път и поставяме ключа на първата празна връзка. При изтриване на листо премахваме връзката от родителя. Височина h е максималният брой ребра от корена.

  1. Кои ключове сравняваме при търсене на 6?
  2. Къде ще добавим 5?
  3. В първоначалното дърво коя връзка премахваме при изтриване на 6?
  4. Колко най-много възела посещава едно търсене при височина 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";               // Ако цикълът свърши без съвпадение, печатаме, че ключът липсва.
}                                      // Край на програмата.

Изтегли main.cpp.

В речника Двоично дърво за търсене · Времева сложност.