sigisMoNd Mesaj tarihi: Kasım 29, 2009 Paylaş Mesaj tarihi: Kasım 29, 2009 daha once ugrasmis veya fikri olan biri yardimci olursa cok makbule gecer. hatirlatmak amacli kisaca anlatiyim AVL Tree nedir ne degildir: kisaca anlatiyim derken wall of text oldu AVL-Tree bir cesit binary tree dir. digerlerinden farki dengeli olmasidir. agaci olustururken eklenen her node'dan sonra dengesi kontrol edilir. ekleme islemi soyle: mesela sirasiyla 3 4 2 7 degerlerine sahip node lari agaca eklicez. [1] 3u direkt koyabiliriz. zaten agacimiz bos. [2] 4 3ten buyuk. o yuzden 4, 3un sag cocugu olucak. [3] 2 3ten kucuk. o yuzden 2, 3un sol cocugu olucak. [4] 7 3ten buyuk. saga gittik. 4ten de buyuk. o yuzden 4un sag cocugu olucak. [1] [2] [3] [4] ------------------------------------- 3 3 3 3 / / --> 4 --> 2 4 --> 2 4 7 ekleme bu sekilde oluyor. eger dengesi bozuksa cevirme islemleri uygulanir. oyle ya da boyle en sonunda yine dengeli bir agacimiz olur. dengede olup olmadigini anlamak icin asagidan yukariya dogru degerler konur. bu degerler 0 1 ya da -1 ise agac dengededir(bize boyle ogretildi en azindan. -1 olayi eger sol child node dan yukari cikilirken konulan deger). ornegin: a / b c / d e yukaridakinde d ve e nin degeri 0. cunku yuksekligi 0. uste cikiyoruz b var. onun da sag ve sol dallarinin derinligi ayni. yani onun da degeri 0. diger taraftan c nin de herhangi bir alt cocugu olmadigi icin 0. a'ya bakildiginda. sag dalinin derinligi 1. sol parcasinin -2(eksi soldan geldigi icin tekrar belirtiyim). sag ve sol derinligi toplayinca -1 etti. yani dengede. dengesizlik durumlarinda 4 cesit dondurme yontemi var: ---------------------------------------------------------- [1] saga dondurme: 3 / 2 2 --> / / 1 3 1 ---------------------------------------------------------- [2] sola dondurme: 3 4 4 --> / 3 5 5 ---------------------------------------------------------- [3] sol-sag dondurus 6 6 4 / / / 3 9 4 9 3 6 / --> / --> / / 2 4 3 5 2 5 9 / 5 2 ---------------------------------------------------------- [4] sag-sol dondurus: 6 6 8 / / / 3 9 3 8 6 9 / --> / --> / 8 10 7 9 3 7 10 / 7 10 ---------------------------------------------------------- genel olarak boyleler. simdi benden istenen programin AvlTree classini yaratmak. elimde olan: package ads1ws09.pa1; public class AvlTree extends AbstractAvlTree { public AvlTree() { super(); } public void insert(int k) { if (root == null) { root = new AvlNode(k); } else { insertNode(root, null, k); } } private void insertNode(AvlNode node, AvlNode parent, int k) { if (k < node.key) { if (node.left != null) { insertNode(node.left, node, k); } else { node.left = new AvlNode(k); } node.height = Math.max(height(node.left), height(node.right))+1; if (parent == null) { // if it is root, if (!isBalanced(parent)) if (height(root.left) >= height(root.right)) { root.left = rotateToRight(node); } else{ root.left = doubleRotateLeftRight(node); } } else { if (!isBalanced(parent)) { //node = parent.left; if (height(node.left) >= height(node.right)) { parent.left = rotateToRight(node); } else{ parent.left = doubleRotateLeftRight(node); } } } } else if (k > node.key) { if (node.right != null) { insertNode(node.right, node, k); } else { node.right = new AvlNode(k); } node.height = Math.max(height(node.left), height(node.right))+1; if (parent == null) { // if it is root, if (!isBalanced(parent)) root = rotateToLeft(root); } else { if (!isBalanced(parent)) //node = parent.left; if (height(node.left) >= height(node.right)) { parent.left = rotateToLeft(node); } else{ parent.left = doubleRotateRightLeft(node); } } } parent.height = Math.max(height(parent.right), height(parent.left))+1; } public int checkAvl() { return checkNode(root); } private boolean isBalanced(AvlNode node) { if (Math.abs(height(node.right) - height(node.right)) < 2) { return true; } return false; } private int checkNode (AvlNode node) { if (node == null) return 0; if (!isBalanced(node)) return 666; if (node.left != null) { if (node.left.key >= node.key) { return 2; } int check = checkNode(node.left); if (check != 0) return check; } if (node.right != null) { if (node.right.key <= node.key) { return 2; } int check = checkNode(node.right); if (check != 0) return check; } return 0; } private int height (AvlNode node) { if (node == null) return -1; //Teilbaum ist leer else return node.height; } private AvlNode rotateToLeft(AvlNode node1) { AvlNode node2 = node1.right; node1.right = node2.left; node2.left = node1; node1.height = Math.max(height(node1.left), height(node1.right))+1; node2.height = Math.max(height(node2.right), height(node1))+1; return node2; } private AvlNode rotateToRight(AvlNode node1) { AvlNode node2 = node1.left; node1.left = node2.right; node2.right = node1; node1.height = Math.max(height(node1.left), height(node1.right))+1; node2.height = Math.max(height(node2.left), height(node1))+1; return node2; } private AvlNode doubleRotateLeftRight(AvlNode node) { node.left = rotateToLeft(node.left); return rotateToRight(node); } private AvlNode doubleRotateRightLeft(AvlNode node) { node.right = rotateToRight(node.right); return rotateToLeft(node); } } ust classindaki AbstractAvlTree'de konstruktorda Node cinsinden olan root=null; seklinde. ayrica Node left ve right olmak uzere 2 tane Node'dan, int height (yukseklikten/derinlik) ve int key(node'un degeri) den olusuyor. programin insertNode - methodunda sorunum var. dondurme metodlarini cok kez kontrol ettim, kitaptan da kontrol ettim. onlarda bir sorun oldugunu sanmioyorum. ama ornegin 1 2 3 4 5 6 7 8 9 10 diye girildiginde 4 2 1 3 8 6 5 7 9 10 sonucunu almam gerekirken yine girileni output olarak aliyorum. insertNode metodunu baska sekillerde de yazmayi denedim. ornegin: public void insert(int k) { AvlNode node = new AvlNode(k); if (root == null) { root = node; root.left = root.right = null; root.height = 0; } else { insertNode(root, node); } } private void insertNode(AvlNode parent, AvlNode node) { if (node.key < parent.key) { if (parent.left == null) { parent.left = node; } else { insertNode(parent.left, node); } if (!isBalanced(parent)) { if (height(parent.left.left)>=height(parent.left.right)) { parent = rotateToRight(parent); } else { parent = doubleRotateLeftRight(parent); } } } else { if (parent.right == null) { parent.right = node; } else { insertNode(parent.right, node); } if (!isBalanced(parent)) { if (height(parent.right.right)>=height(parent.right.left)) { parent = rotateToLeft(node); } else { parent = doubleRotateRightLeft(node); } } } parent.height = Math.max(height(parent.left), height(parent.right))+1; } public void insert(int k) { AvlNode node = new AvlNode(k); if (root == null) { root = node; root.left = root.right = null; root.height = 0; } else { insertNode(root, k); } } private AvlNode insertNode(AvlNode node, int key) { if (node == null) { node = new AvlNode(key); node.right = node.left = null; node.height = 0; } else if (key < node.key) { node.left = insertNode(node.left, key); if (height(node.left)-height(node.right) == 2) { if (key < node.left.key) { node = rotateToLeft(node); } else { node = doubleRotateRightLeft(node); } } } else if (key > node.key) { node.right = insertNode(node.right, key); if (height(node.right)-height(node.left) == 2) { if (key > node.right.key) { node = rotateToRight(node); } else { node = doubleRotateLeftRight(node); } } } else { System.out.println("Node already inserted!"); } node.height = Math.max(height(node.left), height(node.right))+1; return node; gibi. ilkinde yine brsey degistirmeden ayinisi aliyorum. ikincisinde de sadece ilk ve son node'u output olarak aliyorum. sonuncusundan pek umitli degilim zaten. hatanin/eksikligin nerede oldugunu bulamadim. soyleyebilicek pati var mi? Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
El-Barto Mesaj tarihi: Kasım 29, 2009 Paylaş Mesaj tarihi: Kasım 29, 2009 Valla kod çook çook uzun ama ilk bi bakışta şu dikkatimi çekti: if (parent == null) { // if it is root, if (!isBalanced(parent)) null objeyi veriosun isBalanced'a kafadan bi runtime error beklerdim ben orda :D Akşama bol bol inceleyip hata bulabilirsem yollarım, kolay gelsin. Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
sigisMoNd Mesaj tarihi: Kasım 29, 2009 Konuyu açan Paylaş Mesaj tarihi: Kasım 29, 2009 o sekilde de hata almiyorum ama c/p yaparken baska bir satiri kopyalamisim. if(!isBalanced(root)) olucak tabi. Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
riglous Mesaj tarihi: Kasım 29, 2009 Paylaş Mesaj tarihi: Kasım 29, 2009 isBalanced'da private boolean isBalanced(AvlNode node) { if (Math.abs(height(node.right) - height(node.right)) < 2) { return true; } return false; } boyle olmasi gerektigine emin misin? Alakasiz olacak biraz ama ufak bir tavsiyem var. Kodu mumkun oldugunca bol. Kucuk kucuk fonksiyonlar olsun ki debug etmesi kolay olsun. insertNode'un icine girip kaybolmamasi gerek insanin. Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
sigisMoNd Mesaj tarihi: Kasım 29, 2009 Konuyu açan Paylaş Mesaj tarihi: Kasım 29, 2009 tamam soyle olmasi lazim onun: private boolean isBalanced(AvlNode node) { return (Math.abs(height(node.left) - height(node.right))) < 2; } 3. spoilerda denedigim cok mantikli gelmisti aslinda yazarken. o bunun kadar karisik da degil hem ama duzgun calismadi o da. bir de oncesinde tum rotate metodlari toplayan bir tane metod yazmistim. soyleyse su rotate kullanilsin diye ama NullPointerException aldim. sonra vazgectim ondan. o daha da duzenli gozukuyordu. Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
El-Barto Mesaj tarihi: Kasım 29, 2009 Paylaş Mesaj tarihi: Kasım 29, 2009 orda demek istediği iki kere node.right'ı kontrol etmen ya :D edit: tam yazmamışım yani ordaki sonuç hep 0<2 çıkcak bölece hep balanced sancak kendini tree Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
sigisMoNd Mesaj tarihi: Kasım 29, 2009 Konuyu açan Paylaş Mesaj tarihi: Kasım 29, 2009 left right ta sacmalamisim tamam:D Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
sigisMoNd Mesaj tarihi: Kasım 29, 2009 Konuyu açan Paylaş Mesaj tarihi: Kasım 29, 2009 NullPointerException vermeye basladi tekrardan o aptal hatayi duzeltince. Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
riglous Mesaj tarihi: Kasım 29, 2009 Paylaş Mesaj tarihi: Kasım 29, 2009 E haliyle... Artik isBalanced calismaya basladi. isBalanced false dondurunce bu sefer rotateLeft vs. o fonksiyonlar calismaya basliyor. Hangi adima kadar geldigini bulmak icin aralara System.out.println koy, debug et. Muhtemelen rotate'lerde olmayan null bir objenin left veya right'ini aliyorsundur. O kadarina da biz bakmayalim artik... Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
Brigand Mesaj tarihi: Kasım 29, 2009 Paylaş Mesaj tarihi: Kasım 29, 2009 googleda avl tree C++ codes filan yazmayı deneyen oldu mu Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
sigisMoNd Mesaj tarihi: Kasım 29, 2009 Konuyu açan Paylaş Mesaj tarihi: Kasım 29, 2009 insertNode u System.out.println()lerle doldurdum. en azindan nerde oldugunu biliorum simdi hatanin. hata sacma geldi biraz ama bir ugrasiyim bu aksam. Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
Sage Mesaj tarihi: Kasım 29, 2009 Paylaş Mesaj tarihi: Kasım 29, 2009 Artık nullpointer vermiyor insan bir +rep der be sigismond dsdfg. Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
sigisMoNd Mesaj tarihi: Kasım 29, 2009 Konuyu açan Paylaş Mesaj tarihi: Kasım 29, 2009 Sage +rep sdf Link to comment Sosyal ağlarda paylaş Daha fazla paylaşım seçeneği…
Öne çıkan mesajlar