6.3. Naív beszúrás

A kereséshez hasonlóan a beszúrás is a fa gyökeréből indul. Az éppen vizsgált csúcs, és a beszúrandó elem kulcsai alapján a csúcs bal- vagy jobboldali fiánál folytatjuk a vizsgálatot. Ha már megtaláltuk az elem helyét, akkor levélként beszúrjuk.

Procedure BESZÚR(T,z) 
Input: T a fa, z a beszúrandó csúcs 
Eredmény: A T fába beszúrja a z csúcsot 
1  y = Nil 
2  x = T.gyöker 
3  while x != Nil do 
4     y = x 
5     if z.kulcs ≤ x.kulcs then 
6        x = x.bal 
7     else 
8        x = x.jobb
9     endif 
10 endw 
11 z.apa = y 
12 if y == Nil then 
13    T.gyöker = z 
14 else 
15    if z.kulcs ≤ y.kulcs then 
16       y.bal = z 
17    else 
18       y.jobb = z 
19    endif
20 endif 

6.1. példa - 9. példa

Az előbbi ábrán egy üres fával kezdtünk (a). Ezután a 4 beszúrásakor y és x is Nil értéket kap, így az algoritmus végrehajtásakor be sem lépünk a ciklusba. Az új elem lesz a fa gyökere (b). A soron következő elem kulcsa (2) kisebb mint a gyökéré (4), ezért a ciklus egyszer végrehajtódik. Az y a gyökérre mutat, ez alá fűzzük az új elemet. Mivel a kulcsa kisebb a gyökér kulcsánál, a gyökér bal oldalára kerül az új elem (c). Az utolsó elem kulcsa kisebb mint a gyökérelemé, így annak baloldali részfájába kerül. Viszont ennek a részfa gyökérkulcsától nagyobb kulcsa van az új elemnek, tehát a jobb oldalra kell felfűzni (d).