İkili arama ağacı özelliği

• İkili Arama Ağaçları
• (Binary Search Trees)
• BST

• Ders 5

İkili arama ağacı özelliği

• x ikili arama ağacında herhangi bir düğüm olsun.
• Eğer y düğümü x’in sol alt ağacında ise
• key[y] ≤ key[x]
• Eğer y düğümü x’in sağ alt ağacında ise
• key[y] ≥ key[x]

İkili arama ağacı özelliği

• x ikili arama ağacında herhangi bir düğüm olsun.
• Eğer y düğümü x’in sol alt ağacında ise key[y] ≤ key[x]
• Eğer y düğümü x’in sağ alt ağacında ise key[y] ≥ key[x]

• 5

• 3

• 7

• 8

• Kök

• 2

• 4

• <5

• >5

• SolAA

• SağAA

• 2

• Kök

• 3

• 7

• 8

• 5

• 4

• >2

• SağAA

İkili Arama Ağaçları (BST)

• İki arama ağacı bağlı veri yapısı kullanılarak gerçekleştirilebilir.
• Ağaçtaki her düğüm 3 adet pointer alanına sahip bir nesnedir.
• Sol çocuk sol ile, sağ çocuk sağ ile ebeveyn ise p ile temsil edilir.
• NIL ya da NULL herhangi bir çocuk veya ebeveyn olmadığını ifade eder.
• Kök düğümü bir İAA’da p alanı NIL’e sahip tek düğümdür.