Home / Algoritmalar / AVL Ağacı Nedir?

AVL Ağacı Nedir?

İlk defa duyanlar için AVL Ağacı nedir sorusunu cevaplamaya çalışalım. AVL Ağacı esasında özel bir ağaç türü olmaktan ziyade bir Algoritmadır. BST (Binary Search Tree – İkili arama ağacı) üzerinde uygulanmaktadır. Temel işlevi dengeleme sağlamaktır. Bu konuyu anlayabilmek için İkili Arama Ağacı konusunu bildiğinizden emin olmalısınız. Eğer bu konuda bilginiz eksikse aşağıdaki linkten hemen konuya göz atabilirsiniz.

İkili Arama Ağacı Konu Anlatımı

İkili Arama Ağacı Simülasyonu

 

AVL Ağacı’nın temel hedefi dengeleme yapmaktır dedik. Peki neden dengeleme yapıyoruz? Eğer bir ağacın derinliği çok büyürse işlem karmaşıklığı da artar. İşlem karmaşıklığı demek big o notasyonunun yani büyüme faktörünün büyümesi demektir. En basit tabirle söylememiz gerekirse, işlem süresini uzatan bir etmendir. Binary Search Tree üzerinde dengeleme yaparsak, ağacın yüksekliğini kontrol altında tutmuş oluruz. Aşağoda Dengesiz bir ağaç örneği görüyorsunuz.

Dengesiz ağaç örneği

Yukarıdaki resimde gördüğünüz üzere ağacın yüksekliği 6 birimdir. Halbuki bu ağaçta AVL dengelemesi uygulansaydı aşağıdaki gibi bir görünüm oluşacaktı.

AVL ile dengelendirilmiş ağaç örneği

Dikkat ettiyseniz yukarı ağaç da tamamen aynı elemanları taşıyor (10-20-30-40-50-60). Ama temel farkı yüksekliği dengesiz ağaca göre çok daha az. Yalnızca 3 birim. Bu işlem karmaşıklığının azalması manasına geliyor.

AVL Ağaçları temelde Sol ve sağ alt ağaçların yüksekliği arasındaki farkı gözetir. Eğer bir parent düğümün sol ve sağ alt ağaçları arasındaki yükseklik farklı |1| ‘den büyük olursa dengeleme işlemleri devreye girer. Bu dengeleme işlemi 2 farklı döndürme işlemi ile gerçekleştirilir.

  1. Sola Döndürme (Left Rotation)
  2. Sağa Döndürme  (Right Rotation)
AVL Sağa Döndürme Örneği

Yukarıdaki örnekte bir ağaç yapısının sağa döndürünce ne olduğunu görebilirsiniz. Düğüm pozisyonlarının bir sağa gelmesi kadar, ağaç yüksekliğinin de 1 seviye azaldığına dikkat etmelisiniz.

 

AVL Sola Döndürme Örneği

Yukarıdaki iki işlemin ayrıntılarına bu yazıda girmeyeceğiz. Bundan sonraki yazımızda bu işlemleri ayrıntılı olarak anlatacağız.

Peki Dengesizlik durumlarını ne şekilde bunlara bir bakalım.

1- Sol Sol Durumu

2- Sağ Sağ Durumu

3- Sol Sağ Durumu

4- Sağ Sol Durumu

 

Bir sonraki yazımızda dengesizlik durumu nedir, dengesizlik durumlarını nasıl tespit ederiz, nasıl çözümler uygularız buna bakacağız.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir