Binarne drzewo poszukiwań — część 6

Wstawianie klucza Nowe elementy wstawiane są jako liście w odpowiednim miejscu. Do procedury przekazujemy jako argument węzeł InsertNode, w którym InsertNode->Left == NULL, InsertNode->Right == NULL oraz InsertNode->Key != NULL. Algorytm wstawiania węzła do drzewa jest bardzo podobny do algorytmu wyszukiwania węzła w drzewie i wygląda następująco: define BST_TREE_INSERT_NODE(Tree, InsertNode) y = NULL x = Tree->Root while (x != NULL) y = x if (InsertNode->Key < x->Key) x = x->left else x = x->right

InsertNode->Parent = y

if (y == NULL) //drzewo jest puste Tree->Root = InsertNode else if (InsertNode->Key < y->key) y->Left = InsertNode else y->Right = InsertNode Wstawianie rozpoczyna się przeglądaniem węzła od korzenia w celu znalezienia miejsca przyłączenia wstawianego węzła.

Usuwanie klucza Usuwanie węzła jest procedurą bardziej skomplikowaną niż jego wstawianie.