AVL Tree

2012
06.06

1. AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1

antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan

Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

 

2.searching

pencarian di AVL tree dilakukan persis seperti dalam tree pencarian binary tree. Karena keseimbangan tinggi-tree, sebuah pencarian membutuhkan O (log n) waktu. Tidak ada tindakan khusus perlu diambil, dan struktur tree tidak diubah oleh pencarian. (Hal ini berbeda dengan melebarkan pencarian tree, yang melakukan memodifikasi struktur tree mereka.) Jika setiap node tambahan mencatat ukuran subtree (termasuk dirinya sendiri dan keturunannya), maka node dapat diambil dengan indeks dalam O (log n) waktu juga. Setelah node ditemukan di tree seimbang, node berikutnya atau sebelumnya dapat dieksplorasi dalam waktu yang konstan diamortisasi. Beberapa contoh eksplorasi ini “dekat” node memerlukan melintasi hingga 2 log x (n) link (terutama ketika bergerak dari daun paling kanan dari root subtree kiri ke daun paling kiri dari root subtree kanan).

Namun, menjelajahi semua node n dari tree dengan cara ini akan menggunakan setiap link persis dua kali: satu traversal untuk memasuki subtree berakar pada simpul tersebut, dan satu lagi untuk meninggalkan subtree bahwa node setelah menjelajahinya. Dan karena ada n-1 link di tree apapun, biaya perolehan diamortisasi ditemukan menjadi 2 × (n-1) / n, atau sekitar

 

insertion

Setelah memasukkan sebuah node, perlu untuk memeriksa setiap leluhur node untuk konsistensi dengan aturan AVL. Untuk setiap node diperiksa, jika faktor keseimbangan tetap -1, 0, atau +1 maka tidak ada rotasi diperlukan. Namun, jika faktor keseimbangan menjadi kurang dari -1 atau lebih besar dari +1, subtree berakar di node ini tidak seimbang.

Jika insersi dilakukan serial, setelah insersi masing-masing, paling banyak satu dari kasus-kasus berikut perlu diselesaikan untuk mengembalikan seluruh tree dengan aturan AVL. Ada empat kasus yang perlu dipertimbangkan, yang kedua adalah simetris dengan dua lainnya. Misalkan P adalah root dari subtree tidak seimbang, dengan R dan L yang menunjukkan anak-anak kanan dan kiri dari P masing-masing.

Kanan kanan kasus dan Kanan-Kiri kasus: Jika keseimbangan faktor P adalah -2 maka melampaui subtree kanan subtree kiri dari node yang diberikan, dan faktor keseimbangan dari anak kanan (R) harus diperiksa. Rotasi kiri dengan P sebagai root diperlukan.

Jika keseimbangan faktor R adalah -1, rotasi kiri tunggal (dengan P sebagai root) yang dibutuhkan (Kanan-Kanan kasus). Jika keseimbangan faktor R adalah +1, dua rotasi yang berbeda diperlukan. Rotasi pertama adalah rotasi yang benar dengan R sebagai akar.

Yang kedua adalah rotasi kiri dengan P sebagai root (Kanan-Kiri kasus). Kiri-Kiri kasus dan Kiri-Kanan kasus: Jika keseimbangan faktor P adalah 2, maka melampaui subtree kiri kanan subtree dari node tertentu, dan faktor keseimbangan dari anak kiri (L) harus diperiksa. Rotasi yang tepat dengan P sebagai root diperlukan. Jika faktor keseimbangan L adalah +1, rotasi kanan tunggal (dengan P sebagai root) yang dibutuhkan (Kiri-Kiri kasus). Jika faktor keseimbangan L adalah -1, dua rotasi yang berbeda diperlukan. Rotasi pertama adalah rotasi kiri dengan L sebagai akar. Yang kedua adalah rotasi yang tepat dengan P sebagai akar (Kiri-Kanan kasus).

 

deletation

Jika node adalah daun atau hanya memiliki satu anak, keluarkanlah. Jika tidak, ganti dengan baik yang terbesar di subtree kiri (inorder pendahulunya) atau yang terkecil di subtree kanan (inorder pengganti), dan menghapus simpul tersebut. Simpul yang ditemukan sebagai pengganti memiliki paling banyak satu subtree. Setelah penghapusan, menelusuri kembali jalur kembali tree (induk penggantian) ke akar, menyesuaikan faktor keseimbangan yang diperlukan. Seperti semua tree biner, di-order penerus node adalah anak paling kiri hak subtree, dan node di-order pendahulunya adalah anak paling kanan dari subtree kiri. Dalam kedua kasus, node ini akan memiliki nol atau satu anak. Hapus ini menurut salah satu dari dua kasus sederhana di atas.

 

3.contoh Program

#include <iostream.h>

#include <stdlib.h>

#include <conio.h>

#define FALSE 0

#define TRUE 1

 

struct AVLNode

{

int data ;

int balfact ;

AVLNode *left ;

AVLNode *right ;

} ;

class avltree

{

private :

AVLNode *root ;

public :

avltree( ) ;

AVLNode*  insert ( int data, int *h ) ;

static AVLNode* buildtree ( AVLNode *root, int data, int *h ) ;

void display( AVLNode *root ) ;

AVLNode* deldata ( AVLNode* root, int data, int *h ) ;

static AVLNode* del ( AVLNode *node, AVLNode* root, int *h ) ;

static AVLNode* balright ( AVLNode *root, int *h ) ;

static AVLNode* balleft ( AVLNode* root, int *h ) ;

void setroot ( AVLNode *avl ) ;

~avltree( ) ;

static void deltree ( AVLNode *root ) ;

} ;

avltree::avltree( )

{

root=NULL;

}

AVLNode* avltree::insert(int data, int *h )

{

root = buildtree ( root, data, h ) ;

return root ;

}

AVLNode* avltree :: buildtree ( AVLNode *root, int data, int *h )

{

AVLNode *node1, *node2 ;

if ( root == NULL )

{

root = new AVLNode ;

root -> data = data ;

root -> left = NULL ;

root -> right = NULL ;

root -> balfact = 0 ;

*h = TRUE ;

return ( root ) ;

}

if ( data < root -> data )

{

root -> left = buildtree ( root -> left, data, h ) ;

// If left subtree is higher

if ( *h )

{

switch ( root -> balfact )

{

case 1 :

node1 = root -> left ;

if ( node1 -> balfact == 1 )

{

cout << “\nRight rotation.\n” ;

root -> left = node1 -> right ;

node1 -> right = root ;

root -> balfact = 0 ;

root = node1 ;

}

else

{

cout << “\nDouble rotation, left then right.” ;

node2 = node1 -> right ;

node1 -> right = node2 -> left ;

node2 -> left = node1 ;

root -> left = node2 -> right ;

node2 -> right = root ;

if ( node2 -> balfact == 1 )

root -> balfact = -1 ;

else

root -> balfact = 0 ;

if ( node2 -> balfact == -1 )

node1 -> balfact = 1 ;

else

node1 -> balfact = 0 ;

root = node2 ;

}

root -> balfact = 0 ;

*h = FALSE ;

break ;

case 0 :

root -> balfact = 1 ;

break ;

case -1 :

root -> balfact = 0 ;

*h = FALSE ;

}

}

}

if ( data > root -> data )

{

root -> right = buildtree ( root -> right, data, h ) ;

if ( *h )

{

switch ( root -> balfact )

{

case 1 :

root -> balfact = 0 ;

*h = FALSE ;

break ;

case 0 :

root -> balfact = -1 ;

break ;

case -1 :

node1 = root -> right ;

if ( node1 -> balfact == -1 )

{

cout << “\nLeft rotation.\n” ;

root -> right = node1 -> left ;

node1 -> left = root ;

root -> balfact = 0 ;

root = node1 ;

}

else

{

cout << “\nDouble rotation, right then left.” ;

node2 = node1 -> left ;

node1 -> left = node2 -> right ;

node2 -> right = node1 ;

root -> right = node2 -> left ;

node2 -> left = root ;

if ( node2 -> balfact == -1 )

root -> balfact = 1 ;

else

root -> balfact = 0 ;

if ( node2 -> balfact == 1 )

node1 -> balfact = -1 ;

else

node1 -> balfact = 0 ;

root = node2 ;

}

root -> balfact = 0 ;

*h = FALSE ;

}

}

}

return ( root ) ;

}

void avltree :: display ( AVLNode* root )

{

if ( root != NULL )

{

display ( root -> left ) ;

cout << root -> data << ” ” ;

display ( root -> right ) ;

}

}

AVLNode* avltree :: deldata ( AVLNode *root, int data, int *h )

{

AVLNode *node ;

if ( root -> data == 13 )

cout << root -> data ;

if ( root == NULL )

{

cout << “\nNo such data.” ;

return ( root ) ;

}

else

{

if ( data < root -> data )

{

root -> left = deldata ( root -> left, data, h ) ;

if ( *h )

root = balright ( root, h ) ;

}

else

{

if ( data > root -> data )

{

root -> right = deldata ( root -> right, data, h ) ;

if ( *h )

root = balleft ( root, h ) ;

}

else

{

node = root ;

if ( node -> right == NULL )

{

root = node -> left ;

*h = TRUE ;

delete ( node ) ;

}

else

{

if ( node -> left == NULL )

{

root = node -> right ;

*h = TRUE ;

delete ( node ) ;

}

else

{

node -> right = del ( node -> right, node, h ) ;

if ( *h )

root = balleft ( root, h ) ;

}

}

}

}

}

return ( root ) ;

}

AVLNode* avltree :: del ( AVLNode *succ, AVLNode *node, int *h )

{

AVLNode *temp = succ ;

if ( succ -> left != NULL )

{

succ -> left = del ( succ -> left, node, h ) ;

if ( *h )

succ = balright ( succ, h ) ;

}

else

{

temp = succ ;

node -> data = succ -> data ;

succ = succ -> right ;

delete ( temp ) ;

*h = TRUE ;

}

return ( succ ) ;

}

AVLNode* avltree :: balright ( AVLNode *root, int *h )

{

AVLNode *temp1, *temp2 ;

switch ( root -> balfact )

{

case 1 :

root -> balfact = 0 ;

break ;

case 0 :

root -> balfact = -1 ;

*h  = FALSE ;

break ;

case -1 :

temp1 = root -> right ;

if ( temp1 -> balfact <= 0 )

{

cout << “\nLeft rotation.\n”;

root -> right = temp1 -> left ;

temp1 -> left = root ;

if ( temp1 -> balfact == 0 )

{

root -> balfact = -1 ;

temp1 -> balfact = 1 ;

*h = FALSE ;

}

else

{

root -> balfact = temp1 -> balfact = 0 ;

}

root = temp1 ;

}

else

{

cout << “\nDouble rotation, right then left.” ;

temp2 = temp1 -> left ;

temp1 -> left = temp2 -> right ;

temp2 -> right = temp1 ;

root -> right = temp2 -> left ;

temp2 -> left = root ;

if ( temp2 -> balfact == -1 )

root -> balfact = 1 ;

else

root -> balfact = 0 ;

if ( temp2 -> balfact == 1 )

temp1 -> balfact = -1 ;

else

temp1 -> balfact = 0 ;

root = temp2 ;

temp2 -> balfact = 0 ;

}

}

return ( root ) ;

}

AVLNode* avltree :: balleft ( AVLNode *root, int *h )

{

AVLNode *temp1, *temp2 ;

switch ( root -> balfact )

{

case -1 :

root -> balfact = 0 ;

break ;

case 0 :

root -> balfact = 1 ;

*h = FALSE ;

break ;

case 1 :

temp1 = root -> left ;

if ( temp1 -> balfact >= 0 )

{

cout << “\nRight rotation.” ;

root -> left = temp1 -> right ;

temp1 -> right = root ;

if ( temp1 -> balfact == 0 )

{

root -> balfact = 1 ;

temp1 -> balfact = -1 ;

*h = FALSE ;

}

else

{

root -> balfact = temp1 -> balfact = 0 ;

}

root = temp1 ;

}

else

{

cout << “\nDouble rotation, left then right.” ;

temp2 = temp1 -> right ;

temp1 -> right = temp2 -> left ;

temp2 -> left = temp1 ;

root -> left = temp2 -> right ;

temp2 -> right = root ;

if ( temp2 -> balfact == 1 )

root -> balfact = -1 ;

else

root -> balfact = 0 ;

if ( temp2-> balfact == -1 )

temp1 -> balfact = 1 ;

else

temp1 -> balfact = 0 ;

root = temp2 ;

temp2 -> balfact = 0 ;

}

}

return ( root ) ;

}

void avltree :: setroot ( AVLNode *avl )

{

root = avl ;

}

avltree :: ~avltree( )

{

deltree ( root ) ;

}

void avltree :: deltree ( AVLNode *root )

{

if ( root != NULL )

{

deltree ( root -> left ) ;

deltree ( root -> right ) ;

}

delete ( root ) ;

}

int main( )

{

avltree at ;

AVLNode *avl = NULL ;

int h ;

avl = at.insert(20,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(6,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(29,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(5,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(12,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(25,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(32,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(10,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(15,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(27,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(13,&h);

at.setroot(avl);

at.display(avl);

cout<<endl<<”\nAVL tree:\n”;

at.display(avl);

avl = at.deldata(avl, 20, &h);

at.setroot(avl);

avl = at.deldata(avl, 12, &h);

at.setroot(avl);

cout<<”\n\npohon AVL setelah penghapusan 20 dan 12:\n” ;

at.display(avl);

cout<<endl;

avl = at.insert(2,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(28,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(20,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.insert(8,&h);

at.setroot(avl);

at.display(avl);

cout<<endl;

avl = at.deldata(avl, 15, &h);

at.setroot(avl);

avl = at.deldata(avl, 6, &h);

at.setroot(avl);

avl = at.deldata(avl, 5, &h);

at.setroot(avl);

avl = at.deldata(avl, 13, &h);

at.setroot(avl);

avl = at.deldata(avl, 10, &h);

at.setroot(avl);

cout<<”\n\nPohon AVL setelah penghapusan 15,6,5,13 dan 10:\n” ;

at.display(avl);

cout<<endl<<endl;

avl = at.insert(22,&h);

at.setroot(avl);

at.display(avl);

avl = at.insert(23,&h);

at.setroot(avl);

cout<<”\n\nAVL Tree Akhir:\n”;

at.display(avl);

getch();

}

Your Reply

CAPTCHA Image
*