AVL Ağaçları: Döndürme, Ekleme, Silme C++ Örnek E-posta
Sarah Chen
AVL Ağaçları nedir?
AVL ağaçları sol ve sağ alt ağacın yükseklik farkının -1, 0 veya +1 olduğu ikili arama ağaçlarıdır.
AVL ağaçlarına aynı zamanda kendi kendini dengeleyen ikili arama ağacı da denir. Bu ağaçlar logaritmik arama süresinin korunmasına yardımcı olur. Adını mucitleri (AVL) Adelson, Velsky ve Landis'ten almıştır.
AVL Ağacı nasıl çalışır?
AVL ağaçlarına olan ihtiyacı daha iyi anlamak için basit ikili arama ağaçlarının bazı dezavantajlarına bakalım.
Aşağıdaki anahtarların ikili arama ağacına verilen sırayla eklendiğini düşünün.
Anahtarları değerlerine göre artan sırada yerleştirdiğimizde ağacın yüksekliği doğrusal olarak büyür. Bu nedenle, arama işlemi en kötü ihtimalle O(n) alır.
Bir öğeyi aramak doğrusal zaman alır; dolayısıyla kullanmanın bir faydası yok İkili Arama Ağacı yapı. Öte yandan, ağacın yüksekliği dengeliyse, daha iyi arama süresi elde ederiz.
Şimdi aynı tuşlara farklı bir sırayla eklenmiş olarak bakalım.
Burada tuşlar aynıdır ancak farklı sırayla yerleştirildikleri için farklı konumlar alırlar ve ağacın yüksekliği dengede kalır. Bu nedenle ağacın herhangi bir elemanı için arama O(log n) değerinden daha fazla zaman almayacaktır. Artık yerleştirme doğru yapılırsa ağacın yüksekliğinin dengede tutulabileceği açıktır.
AVL ağaçlarında ekleme işlemi sırasında ağacın yüksekliğini kontrol ediyoruz. İkili Arama Ağacının temel özelliklerini ihlal etmeden dengeli yüksekliği korumak için değişiklikler yapılır.
AVL Ağaçlarında Denge Faktörü
Denge faktörü (BF), AVL ağaçlarındaki her düğümün, ağacın yüksekliğini izlemeye yardımcı olan temel bir özelliğidir.
Denge Faktörünün Özellikleri
- Denge faktörü, sol alt ağacın ve sağ alt ağacın yüksekliği arasındaki fark olarak bilinir.
- Denge faktörü(düğüm) = yükseklik(düğüm->sol) – yükseklik(düğüm->sağ)
- İzin verilen BF değerleri –1, 0 ve +1'dir.
- –1 değeri, sağ alt ağacın bir ekstra içerdiğini, yani ağacın sağ ağır olduğunu gösterir.
- +1 değeri, sol alt ağacın bir fazlalık içerdiğini, yani ağacın ağır bırakıldığını gösterir.
- 0 değeri, ağacın her iki tarafında eşit düğümler içerdiğini, yani ağacın mükemmel şekilde dengelendiğini gösterir.
AVL Rotasyonları
AVL Ağacının kendisini dengelemesi için ağaca bir düğüm eklenirken veya ağaca bir düğüm silinirken rotasyonlar gerçekleştirilir.
Aşağıdaki LL rotasyonu, RR rotasyonu, LR rotasyonu ve RL rotasyonunu gerçekleştiriyoruz.
- Sol – Sola Dönüş
- Sağ – Sağ Döndürme
- Sağa – Sola Dönüş
- Sol – Sağa Döndürme
Sol – Sola Dönüş
Bu döndürme, sol alt ağacın sol çocuğuna yeni bir düğüm eklendiğinde gerçekleştirilir.
Tek sağa dönüş gerçekleştirilir. Bu tür bir döndürme, bir düğümün denge faktörü +2 ve sol çocuğunun denge faktörü +1 olduğunda tanımlanır.
Sağ – Sağ Döndürme
Bu döndürme, sağ alt ağacın sağ çocuğuna yeni bir düğüm eklendiğinde gerçekleştirilir.
Tek bir sola dönüş gerçekleştirilir. Bu tür bir döndürme, bir düğümün dengeli faktörü -2 olduğunda ve sağ çocuğunun denge faktörü -1 olduğunda tanımlanır.
Sağa – Sola Dönüş
Bu döndürme, sol alt ağacın sağ çocuğuna yeni bir düğüm eklendiğinde gerçekleştirilir.
Bu döndürme, bir düğümün denge faktörü –2 olduğunda ve sağ çocuğunun denge faktörü +1 olduğunda gerçekleştirilir.
Sol – Sağa Döndürme
Bu döndürme, sağ alt ağacın sol çocuğuna yeni bir düğüm eklendiğinde gerçekleştirilir.
Bu döndürme, bir düğümün denge faktörü +2 ve sol çocuğunun denge faktörü -1 olduğunda gerçekleştirilir.
AVL Ağaçlarına Ekleme
Ekleme işlemi basit ikili arama ağaçlarındakiyle hemen hemen aynıdır. Her eklemeden sonra ağacın yüksekliğini dengeliyoruz. Ekleme işlemi O(log n) en kötü zaman karmaşıklığına sahiptir.
1. Adım: BST'nin aynı ekleme algoritmasını kullanarak düğümü AVL ağacına ekleyin. Yukarıdaki örnekte 160 girin.
2. Adım: Düğüm eklendiğinde her düğümün denge faktörü güncellenir. 160 eklendikten sonra her düğümün denge faktörü güncellenir.
3. Adım: Şimdi herhangi bir düğümün denge faktörünün aralığını ihlal edip etmediğini kontrol edin, eğer denge faktörü ihlal edilirse, ardından aşağıdaki durumu kullanarak rotasyonlar gerçekleştirin. Yukarıdaki örnekte 350 olan denge faktörü ihlal edilmiş ve burada 1. durum geçerli hale gelmiş, LL rotasyonu gerçekleştirmiş oluyoruz ve ağaç yeniden dengelenmiş oluyor.
- BF(düğüm) = +2 ve BF(düğüm -> sol-çocuk) = +1 ise, LL döndürmeyi gerçekleştirin.
- BF(düğüm) = -2 ve BF(düğüm -> sağ-çocuk) = 1 ise, RR rotasyonu gerçekleştirin.
- BF(düğüm) = -2 ve BF(düğüm -> sağ-çocuk) = +1 ise, RL döndürmeyi gerçekleştirin.
- BF(düğüm) = +2 ve BF(düğüm -> sol-çocuk) = -1 ise, LR döndürmeyi gerçekleştirin.
AVL Ağaçlarında Silme
Silme işlemi de oldukça basittir. Basit ikili arama ağaçlarındaki mantığın aynısını kullanarak sileriz. Silme işleminden sonra gerekirse dengeli yüksekliğini korumak için ağacı yeniden yapılandırırız.
1 Adım: Ağaçtaki öğeyi bulun.
2 Adım: BST Silme işlemine göre düğümü silin.
3 Adım: İki durum mümkündür: -
Olgu 1: Sağ alt ağaçtan silme.
- 1 A. BF(düğüm) = +2 ve BF(düğüm -> sol-çocuk) = +1 ise, LL döndürmeyi gerçekleştirin.
- 1B. BF(düğüm) = +2 ve BF(düğüm -> sol-çocuk) = -1 ise, LR döndürmeyi gerçekleştirin.
- 1C. BF(düğüm) = +2 ve BF(düğüm -> sol-çocuk) = 0 ise, LL döndürmeyi gerçekleştirin.
vaka 2: Sol alt ağaçtan siliniyor.
- 2A. BF(düğüm) = -2 ve BF(düğüm -> sağ-çocuk) = -1 ise, RR rotasyonu gerçekleştirin.
- 2B. BF(düğüm) = -2 ve BF(düğüm -> sağ-çocuk) = +1 ise, RL döndürmeyi gerçekleştirin.
- 2C. BF(düğüm) = -2 ve BF(düğüm -> sağ-çocuk) = 0 ise, RR döndürmeyi gerçekleştirin.
C++ AVL Ağaçları Örneği
Aşağıda C++ AVL ağaçlarını uygulayan:
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct node {
struct node *left;
int data;
int height;
struct node *right;
};
class AVL
{
private:
public:
struct node * root;
AVL(){
this->root = NULL;
}
int calheight(struct node *p){
if(p->left && p->right){
if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;
}
int bf(struct node *n){
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}
struct node * llrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->left;
p->left = tp->right;
tp->right = p;
return tp;
}
struct node * rrrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->right;
p->right = tp->left;
tp->left = p;
return tp;
}
struct node * rlrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;
p -> right = tp2->left;
tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;
return tp2;
}
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
return tp2;
}
struct node* insert(struct node *r,int data){
if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}
r->height = calheight(r);
if(bf(r)==2 && bf(r->left)==1){
r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}
return r;
}
void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;
if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}
}
}
struct node * deleteNode(struct node *p,int data){
if(p->left == NULL && p->right == NULL){
if(p==this->root)
this->root = NULL;
delete p;
return NULL;
}
struct node *t;
struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}
if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }
return p;
}
struct node* inpre(struct node* p){
while(p->right!=NULL)
p = p->right;
return p;
}
struct node* insuc(struct node* p){
while(p->left!=NULL)
p = p->left;
return p;
}
~AVL(){
}
};
int main(){
AVL b;
int c,x;
do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";
cin>>c;
switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;
case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;
case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
case 0:
break;
}
} while(c!=0);
}
Yukarıdaki kodun çalışan örneği:
- Yukarıdaki kodu kopyalayıp “avl.cpp” içerisine yapıştırın.
- Kodu derleyin:
g++ avl.cpp -o run
- Kodu çalıştırın.
./run
AVL Ağaçlarının Avantajları
- AVL ağacının yüksekliği her zaman dengelidir. Yükseklik asla log N'nin ötesine geçmez; burada N, ağaçtaki toplam düğüm sayısıdır.
- Basit İkili Arama ağaçlarına kıyasla daha iyi arama zamanı karmaşıklığı sağlar.
- AVL ağaçlarının kendi kendini dengeleme yetenekleri vardır.
ÖZET
- AVL ağaçları kendi kendini dengeleyen ikili arama ağaçlarıdır.
- Denge faktörü AVL ağaçlarının temel özelliğidir
- Bir düğümün denge faktörü, o düğümün sol ve sağ alt ağaçlarının yüksekliği arasındaki fark olarak tanımlanır.
- Denge faktörünün geçerli değerleri -1, 0 ve +1'dir.
- Ekleme ve silme işlemi, denge faktörü ihlal edildikten sonra rotasyonların gerçekleştirilmesini gerektirir.
- Ekleme, silme ve arama işlemlerinin zaman karmaşıklığı O(log N)'dir.
- AVL ağaçları İkili Arama Ağaçlarının tüm özelliklerini takip eder.
- Sol alt ağaçta kök düğümden daha küçük düğümler bulunur. Sağ alt ağaçta her zaman kök düğümden daha büyük düğümler bulunur.
- AVL ağaçları, arama işleminin ekleme ve silme işlemlerine göre daha sık olduğu yerlerde kullanılır.
