Drzewa BST

Co to jest drzewo wyszukiwań binarnych - BST (ang. Binary Search Tree)

Jest to jak sama nazwa wskazuje drzewo binarne tzn. każdy węzeł (ang. node) może posiadać maksymalnie jednego rodzica (ang. parent) oraz dwa elementy potomne (ang. left, right). Początkiem drzewa jest korzeń (ang. root), który może przyjmować wartość (w przeciwieństwie do głowy w liście). Węzłem jest struktura, zawierająca element danych z których budujemy drzewo, oraz dwa lub trzy wskaźniki (zależnie od potrzeb) na lewego i prawego potomka, oraz ew. na rodzica.
Dla drzew BST charakterystyczną budową jest to, że patrząc od korzenia, w każdym jesgo poddrzewie zachodzi zasada, że elementy mniejsze od korzenia znajdują się na lewo, a elementy większe na prawo od niego. Wbrew temu co mówi Cormen w drzewie BST nie mogą występować dwa takie same elementy.

Podstawowe funkcje na BST

Poniżej znajdują się opisy i implementacje podstawowych funkcji służących do obsługo BST. (bynajmniej nie tych z STL'a :)

Tworzenie drzewa binarnego

Podstawą drzewa jest struktura:

struct node
{
   int key;
   node *parent;
   node *left;
   node *right
};
 
void create-root(int key)
{
   node root;
   root->parent = NULL;
   root->left = NULL;
   root->right = NULL;
   root.key = key;
}

Funkcja create-root tworzy nam korzeń drzewa. Teoretycznie można sie bez tego obejść, ale przy tworzeniu drzewa ze strukturą trzywskaźnikową łatwiej jest uniknąć błędu tworząc go osobno.

Dołączenie elementu do drzewa

Wstawianie elementu do drzewa, polega na odnalezieniu pozycji którą dany element powinien zajmować, a następnie wpięciu go w właściwy wskaźnik elementu parent, oraz wskaźnika parent nowego elementu na rodzica. W naszym przypadku wyglądało by to następująco:

Tu w najbliższym czasie znajdzie się kod dodawania elementów do drzewa.

Narazie to wszystko - resztę będę dodawał po kawałku w najbliższym czasie (żeby nie blokować cały czas strony).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License