Sdp28

Създаване на двоично дърво и включване на връх в в двоично дърво за търсене.

Двоично дърво

Ще използваме следната структура за елемент на дървото:

struct btree {
 int key;
 btree *left, *right;
};

Това е стандартна реализация на двоично дърво(като евентуално може да се направи по-обща с използването на шаблони). Key е поле, което се използва за сравнение на два елемента. Обикновено освен стойност key, има и стойност value, в която се пазят същинските данни в дървото.

С тази функция ще четем дървото в паметта(очевидно тя е направена за работа с хора, не машини)

void create (btree *&t)
 { int x; char ch;
   cout << “Ключ на корен: “;
   cin >> x;
   if ( (t = new btree) == NULL)
    {  cout << “Няма достатъчно памет!\n” << endl;
       exit (1);
    }
   t -> left = t -> right = NULL; t -> key = x;
   cout << “Ляво поддърво с ключ на корена “ << x
           << “ Y/N? “;
   ch = cin.get ();
   if ( (ch = cin.get ()) == ‘Y’ || ch == ‘y)
       create (t -> left);
   cout << “Дясно поддърво с ключ на корена “ << x
           << “ Y/N? “;
   ch = cin.get ();
   if ( (ch = cin.get ()) == ‘Y’ || ch == ‘y)
       create (t -> right);
 }

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

Под двоично дърво за търсене разбираме двоично дърво за всеки връх на което стойностите на всички ключове в лявото поддърво са по-малки от стойността на ключа във върха x и стойностите на всички ключове в дясното поддърво са не по-малки(>=) от стойността на ключа във върха x; такова дърво още наричаме двоично дърво за търсене с повторения, тъй като в него се допускат върхове с еднакви ключове; ако изискването за стойностите на ключовете на върховете в дясното поддърво на върха x е да са по-големи(>) от стойността на ключа във върха x, тогава двоичното дърво за търсене е без повторения;

Предимството на такова дърво е, че е възможно лесно да се отхвърля голяма част от потенциалните решения и да се съкрати времето за изпълнение. Например, ако търсим стойността с индекс 6 и сме във връх с индекс 5(да го наречем T) можем със сигурност да твърдим, че търсеният връх не е в лявото поддърво на T. Защото в лявото поддърво на T има само стойности по-малки от T.key, което е по-малко от търсения ключ.
Това дърво предоставя бързи отговори за почти всички възможни входни данни. Възможно е обаче да се получи така, че дървото да се изроди в списък. N на брой върха, всеки от които има, например, само ляв наследник. В такъв случай е възможно една проверка да разгледа всичките N върха, което би било бавно.

Съществуват оптимизации на дърветата за търсене. Те се наричат балансирани дървета за търсене. Подлежат на регулация(или саморегулация по време на вмъкване на елемент, или външна регулация със специална процедура) и предоставят по-добри времеви сложности за вмъкване, търсене и триене на елемент в средния и най-лошия случай.
Такива дървета например са Червено-черните дървета, AVL дърветата и B-дърветата.

Ще опишем функция за добавяне на връх в двоично дърво за търсене с повторения;

template < class KeyType >
struct btree {
 KeyType key;
 btree < KeyType > *left, *right;
} ;
template < class KeyType >
void insert ( KeyType x, btree < KeyType > &*t)
{
    if (t == NULL)
    {
        if ( ( t = new btree < KeyType >) == NULL)
        {
            cout << “Няма достатъчно памет!” << endl;
                 exit (1);
        }
    t -> left = t -> right = NULL;
    t -> key = x;
    return;
    }
 
    if ( x < t -> key )
        insert (x, t -> left);
    else
        insert (x, t -> right);
}

И малко код за тестване:

int main ()
{
    btree <int> *tree = NULL;
    insert (5, tree);
    insert (3, tree);
    insert (4, tree);
 
    cout<<(tree->key)<<endl;
    cout<<(tree->left->key)<<endl;
    cout<<(tree->left->right->key)<<endl;
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License