Tüm node’ların alt ağaçları dengeli olan ağaçlardır. Dengenin sağlanabilmesi için node’a ait sol alt ağacın yüksekliği ile sağ alt ağacın yüksekliği arasında fark 0 veya 1 olmalıdır. Birçok balanced search tree algoritması vardır. Bunlardan bazıları:
- AVL Tree
- Splay Tree
- B Tree
dir.
AVL Tree
Dengeli arama ağacı olan AVL ağacı, aynı zamanda bir ikili arama ağacıdır. Sol alt ağacın yüksekliği – sağ alt ağacın yüksekliğine denge faktörü (balance factor) denilmektedir. AVL ağacında her node için denge faktörü -1, 0 veya 1 olmalıdır.
AVL Tree Rotation
Bir AVL ağacına node eklendiğinde veya silindiğinde denge bozulabilir. Bu durumda ağacı tekrar dengelemek için rotation (döndürme) işlemi uygulanır. Rotation, left rotation, right rotation ve double rotation şeklinde üç farklı şekilde gerçekleştirilebilir.
Aşağıdaki ağaçta A node’unda dengesizlik meydana gelmektedir. A node’unun sağında bulunan C node’u sola döndürülerek A node’unun yerini alır. A node’u, C node’unun left’i haline gelir. C’nin döndürülmeden önceki left’i olan D node’u ise A node’unun right’ı olur.
Aşağıdaki ağaçta A node’unda dengesizlik meydana gelmektedir. A node’unun solunda bulunan B node’u sağa döndürülerek A node’unun yerini alır. A node’u, B node’unun right’ı haline gelir. B’nin döndürülmeden önceki right’ı olan E node’u ise A node’unun left’i olur.
Aşağıdaki ağaçta A node’unda dengesizlik meydana gelmektedir. Öncelikle C node’u sağa döndürülerek D node’unun rigt’ı haline gelir. D node’u ise A node’unun right’ı olur. Dengesizlik hala devam ettiği için tekrar bir döndürme işlemi uygulanır. D node’u döndürülerek A node’unun yerini alır. A node’u D node’unun rigt’ı haline gelir. A node’unun right’ı ise F node’u olur.
Splay Tree
Dengeli arama ağacı olan Splay ağacı, aynı zamanda bir ikili arama ağacıdır. Splay ağacında her zaman denge durumu gözlenmez. Bir node eklendiğinde, arandığında ya da silinmek istendiğinde o node, sezgisel bir algoritmayla köke taşınır.
Aşağıdaki ağaçta “12″ için arama işlemi yapılmış ve bulunduğunda döndürme işlemleriyle köke taşınmıştır.
B Tree
En bilinen örmeği 2-3 ağacı olan B ağaçları derece faktörlü ağaçlardır. Her node, maksimum m çocuğa ve m-1 key’e sahiptir. 2-3 Ağacı için, her bir node’un maksimum 3 çocuğu ve 2 key’i vardır. B Ağaçlarında her bir node’daki key’ler sıralı olmalıdır.
B Tree Insertion
Eleman her zaman ağacın yaprağına eklenir. Eklendiğinde eğer node, maksimum değerinden fazla key olursa ortadaki key yukarı taşınır ve node’lar düzenlenir. Aşağıdaki 2-3 ağacına sırasıyla 4, 6 ve 14 key’leri eklenmiştir.
