İkili arama ağacı özelliği

İkili Arama Ağaçlarında İşlemler

• Dolaşma (Traversal)
• Arama (Search)
• Minimum
• Maximum
• Successor
• Predessor
• Ekleme (Insertion)
• Silme (Deletion)

1-) Dolaşma (Traversal)

• Ağaç yapısı üzerinde herhangi bir düğüme erişme
• sürecimize ağacı gezmek (traverse) denir. Bir ağacı
• en çok bilinen üçdeğişik yöntemle gezebiliriz :
• i) Sıralı (Inorder) ya da kök ortada
• ii) Kök sonda (Postorder)
• iii) Kök başta (Preorder)

Inorder-tree walk

• Bu dolaşma yönteminde önce sol alt ağaç sonra alt ağacın kökü ve en sonda ise sağ alt ağaç dolaşılır.

Preorder-tree walk

• Bu dolaşma yönteminde alt ağaçlardan önce kök dolaşılır.

Postorder-tree walk

• Bu dolaşma yönteminde ise alt ağaçlardan sonra kök dolaşılır.

• 6

• 3

• 7

• 2

• 5

• 8

• Inorder-tree walk

2-Arama

• 15

• 6

• 18

• 3

• 2

• 4

• 7

• 17

• 13

• 20

• 9

• 13’ü ara

• 2-Arama (Özyinelemeli)

• 2-Arama (İteratif)

3- Minimum Bulma

• 15

• 6

• 18

• 3

• 2

• 4

• 7

• 17

• 13

• 20

• 9

• Minimum

• En küçük elemanı içeren düğüm en soldaki düğümde bulunur.
• Kökten başlayarak devamlı sola gidilerek bulunur

• 3- Minimum Bulma

4- Maksimum Bulma

• 15

• 6

• 18

• 3

• 2

• 4

• 7

• 17

• 13

• 20

• 9

• Maximum

• En büyük elemanı içeren düğüm en sağdaki düğümde bulunur.
• Kökten başlayarak devamlı sağa gidilerek bulunur

• 4- Maksimum Bulma

5- Successor (sonra gelen en küçük)

• Bir x düğümünün successor’u key[x] değerinden büyük en
• küçük değerli düğümdür.

• 15

• 6

• 18

• 3

• 2

• 4

• 7

• 17

• 13

• 20

• 9

• 15’in Successor’ı

• Durum 1: x düğümünün sağ alt ağacı boş değilse

• 5- Successor (sonra gelen en küçük)

• 15

• 6

• 18

• 3

• 2

• 4

• 7

• 17

• 13

• 20

• 9

• 13’ün successor’ı

• Durum 2: x düğümünün sağ alt ağacı boş ise

• 5- Successor (sonra gelen en küçük)

• 5- Successor (sonra gelen en küçük)

• 15

• 6

• 18

• 3

• 2

• 4

• 7

• 17

• 13

• 20

• 9

6-Ekleme

• 12

• 5

• 18

• 2

• 13

• 17

• 9

• 15

• 19

• 13 elemanını ekleme

• 6-Ekleme

6-Ekleme

• 12

• 5

• 18

• 2

• 13

• 17

• 9

• 15

• 19

7-Silme

• 15

• 5

• 16

• 2

• 18

• 12

• 23

• 20

• 13 elemanını silme (z’nin çocuğu olmadığı durum)

• 10

• 13 z

• 5

• 3

• 6

• 7

7-Silme

• 15

• 5

• 16

• 2

• 18

• 12

• 23

• 20

• 10

• 5

• 3

• 6

• 7

• 13 elemanını silme (z’nin çocuğu olmadığı durum)

• 15

• 5

• 16 z

• 2

• 18

• 12

• 23

• 20

• 10

• 13

• 5

• 3

• 6

• 7

• 16 elemanını silme (z’nin bir çocuğu olduğu durum)

• 7-Silme

• 15

• 5

• 2

• 12

• 10

• 13

• 5

• 3

• 18

• 23

• 20

• 6

• 7

• 16 elemanını silme (z’nin bir çocuğu olduğu durum)

• 7-Silme

• 15

• 5

• 16

• 2

• 18

• 12

• 23

• 20

• 10

• z 5

• 3

• 6 y

• 7

• 13

• 7-Silme

• 5 elemanını silme (5’in successor’u 6) (z’nin ikiçocuğu olduğu durum)

• 15

• 5

• 16

• 2

• 18

• 12

• 23

• 20

• 10

• z 5

• 3

• 6 y

• 7

• 13

• 7-Silme

• 5 elemanını silme (z’nin ikiçocuğu olduğu durum)

• 15

• 5

• 16

• 2

• 18

• 12

• 23

• 20

• 10

• 6

• 3

• 7

• 13

• 7-Silme

• 5 elemanını silme (z’nin ikiçocuğu olduğu durum)

7-Silme

İkili Arama ağacı Uygulamaları

• İkili arama ağacı harita, sözlük gibi birçok uygulamada kullanılır.
• İkili arama ağacı (anahtar, değer) çifti şeklinde kullanılacak sistemler için uygundur.
• Ö.g.: Şehir Bilgi Sistemi
• Posta kodu veriliyor , şehir ismi döndürülüyor. (posta kodu/ Şehir ismi)
• Ö.g.: telefon rehberi
• İsim veriliyor telefon numarası veya adres döndürülüyor. (isim, Adres/Telefon)
• Ö.g.: Sözlük
• Kelime veriliyor anlamı döndürülüyor. (kelime, anlam)

İkili Arama Ağacı – Sonuç

• İki arama ağaç işlemlerinin karmaşıklığı O(h)
• Fakat h ağacın derinliğine bağlı.
• Örnek: 1 2 3 4 5 6 sayılarını sıralı bir şekilde ekleyelim.

• 1

• 2

• 3

• 4

• 5

• 6

• kök

• Daha iyisi yapılabilir mi? Ağacımızı dengeli yaparsak evet?
• AVL-ağaçları
• Splay ağaçları
• Red-Black ağaçları
• B ağaçları, B+ agaçları

• Ortaya çıkan ağaç bağlantılı listeye benzemektedir. Dolayısıyla karmaşıklık O(n) şeklinde olacaktır.