İkili Arama Ağacı Nedir?

İkili arama ağacı nedir?

İkili arama ağacı, sıralı veriyi hızlı aramak için tasarlanmış bir ağaç veri yapısıdır. Her düğümün en fazla iki çocuğu vardır. Kural şudur: bir düğümün sol tarafındaki tüm değerler ondan küçük, sağ tarafındakiler ondan büyüktür. Bu kural ağacın her seviyesinde geçerlidir.

Arama nasıl yapılır?

Kökte 50 olan bir ağaç düşünün. Sol tarafında 30, sağ tarafında 70 bulunsun. 30'un çocukları 20 ve 40, 70'in çocukları 60 ve 80 olsun. 60 değerini aradığınızda önce kökteki 50'ye bakarsınız. 60 daha büyük olduğu için sağa, 70'e geçersiniz. Bu kez 60 daha küçüktür, sola inersiniz ve değeri bulursunuz.

Her adımda kalan ağacın yaklaşık yarısı elenir. Dengeli bir ağaçta bir milyon elemanın içinde arama yaklaşık 20 adımda biter. Yeni bir değer eklemek de aynı yolu izler: değer, aramanın bittiği boş yere yerleştirilir.

Dengesiz ağaç sorunu

Değerler ağaca zaten sıralı gelirse sorun çıkar. 10, 20, 30, 40 sırasıyla eklenen değerler hep sağa yerleşir ve ağaç uzun bir zincire döner. Bu durumda arama, ikili arama hızını kaybeder ve listeyi baştan sona gezmekle aynı hâle gelir.

Çözüm, kendini dengeleyen ağaçlardır. AVL ve kırmızı-siyah ağaçlar her ekleme ve silmeden sonra düğümleri döndürerek yüksekliği düşük tutar. Java'daki TreeMap ve C++'taki std::map gibi hazır yapılar arka planda bu tür ağaçları kullanır. Kendi projenizde çoğu zaman bu hazır yapıları tercih etmeniz yeterlidir.