Dengeli Arama Ağaçları (Balanced Search Tree) 6 .slayt

•AVL tree

•2-3 ve 2-3-4 tree

•Splay tree

•Red-Black Tree

•B- tree,

Dengeli arama ağaçları  gelişmesi tüm ağaçlara homejen olarak yansıtan ağaç şeklidir.

Yapılan istatiksel çalışmalara göre bu ağaçlarda  denge sağlanmış olup çok   az sapma gözlenmiştir .

 Yükseklik dengeli ağaçlar

->BST operasyonlarını daha kısa sürede gerçekleştirmek için pek çok BST dengeleme algoritması vardır. Bunlardan bazıları;

-Adelson-Velskii ve Landis (AVL) ağaçları (1962)
-Splay ağaçları (1978)
-B-ağacı ve diğer çok yönlü arama ağaçları (1972)
-Red-Black ağaçları (1972)
-Ayrıca Simetrik İkili B-Ağaçları(Symmetric Binary B-Trees) şeklinde de bilinir


AVL AĞAÇLARI
-AVL( G.M. Adelson-Velskii and E.M. Landis) yöntemine göre kurulan bir ikili arama ağacı, ikili AVL arama ağacı olarak adlandırılır.
-AVL ağacının özelliği, sağ alt ağaç ile sol alt ağaç arasındaki yükseklik farkının en fazla bir düğüm olmasıdır. Bu kural ağacın tüm düğümleri için geçerlidir.
-Normal ikili arama ağaçları için ekleme ve silme algoritmaları, ikili AVL ağaçları üzerinde ağacın yanlış şekil almasına, yani ağacın dengesinin bozulmasına neden olur.


AVL Ağaçları: Tanım
1.Tüm boş ağaç AVL ağacıdır.
2.Eğer T boş olmayan TL ve TR şeklinde sol ve sağ alt ağaçları olan ikili arama ağacı ise, T ancak ve ancak aşağıdaki şartları sağlarsa AVL ağacı şeklinde isimlendirilir.
1.TL ve TR AVL ağaçları ise
2.hL ve hR TL ve TR nin yükseklikleri olmak üzere |hL – hR| <= 1 olmak zorundadır.

AVL Ağaçları
-AVL ağaçları dengeli ikili arama ağaçlarıdır.
-solh= yükseklik(sol altağaç), ve sagh=yükseklik(sağ altağaç) ise
-Bir düğümdeki denge faktörü= solh - sagh
-AVL ağaçlarında balans faktörü sadece -1, 0, 1 olabilir.
-Eşit ise 0
-Sol sazla ise 1
-Sağ fazla ise -1
-Her bir düğümün sol ve sağ alt ağaçlarının yükseklikleri arasındaki fark en fazla 1 olabilir.