Šta je binarno stablo?

Binerno drvo je struktura podataka u obliku stabla u kojoj svaki čvor ima najviše dva potomka: levog i desnog.

Osobine:

• Korijen (Root): Najviši čvor stabla.
• Čvor (Node): Element stabla koji sadrži podatke i veze na njegove potomke.
• Dete (Child): Čvor koji se nalazi direktno ispod drugog čvora (roditelja).
• Roditelj (Parent): Čvor koji ima jedan ili više potomaka direktno ispod sebe.
• List (Leaf): Čvor bez potomaka.
• Grana (Branch): Put od korijena do lista.
• Podstablo (Subtree): Drvo sastavljeno od čvora i svih njegovih potomaka.

Različite vrste binarnih stabala:

• Puno binarno stablo (Full Binary Tree): Svaki čvor ima ili 0 ili 2 potomka.
• Savršeno binarno stablo (Perfect Binary Tree): Svi nivoi, osim poslednjeg, su potpuno popunjeni, a na poslednjem nivou svi čvorovi su što je moguće više levo.
• Izbalansirano binarno stablo (Balanced Binary Tree): Visina levog i desnog podstabla bilo kog čvora razlikuje se najviše za 1. Primer: AVL stablo, crveno-crno stablo.
• Degenerisano (izduženo) binarno stablo (Degenerate Binary Tree): Svaki čvor ima najviše jednog potomka. U suštini, to je povezani spisak.

Koristi se u raznim algoritmima i strukturama podataka, kao što su binarni stabla pretraživanja, hrpe, sintaksička stabla.