Röportajda sorulmaktan korkmayın! İkili ağaç algoritması envanteri | Kuvvet Projesi
Yazar | BoCong-Deng
Sorumlu Editör | Wu Xingling
Baş resmi | Visual China'dan CSDN indirmesi
Üretildi | CSDN Blogu
Ağaç yapısı programcılara, özellikle ikili ağaca yabancı olmamalıdır.Temel olarak, algoritmaya dokunduğunuz sürece kesinlikle onunla karşılaşacaksınız.Bu nedenle ikili ağaç yapısının ilgili algoritmalarını bir makale, düşünme ve Kod uygulamasının birleşimi artık ikili ağaçlardan korkmamanızı sağlar. (Ps: Ayrıca daha sonra, B-tree, B + tree gibi algoritma kağıtlarını okurken karşılaştığım bazı yeni algoritmalarla ilgili olan çoklu-çapraz sayılardan oluşan ve ağaç yapısı üzerine gelişmiş bir bölüm yazmak istiyorum. Ağaçlar için yeni algoritmalar vb.)
Ben sadece teknik blog yazılarını paylaşmak istiyorum ama şunu da söylemek istiyorum, eğer yararlı bulursanız, lütfen dikkat edin, beğenin, benim için bir rahatlama olur, sonuçta çok fazla saçımı kaybetmem gerek hehehe.
Aşağıdaki düşünceler dizisinde, bir tür sözde kodlu düşünce dizisi vereceğim ve daha sonra bir düşünce treni çerçevesi olan ilgili açıklamalar yapacağım.Bir düşünce treni çerçevesi olduğunda, onu gelecekte tamamlanması için doğrudan çerçeveye teslim edeceksiniz. Bu makale esas olarak İkili Arama Ağacı (BST olarak anılan İkili Arama Ağacı) hakkında konuşmaktadır, BST çok yaygın olarak kullanılan bir ikili ağaçtır. Tanımı şudur: bir ikili ağaçta, herhangi bir düğümün değeri, sol alt ağaçtaki tüm düğümlerin değerlerinden büyük veya bunlara eşit olmalı ve sağ alt ağaçtaki tüm düğümlerin değerlerinden küçük veya eşit olmalıdır. Aşağıdaki, tanımı karşılayan bir BST'dir:
Polytree gibi özel bir fikir yapısı ile karşılaşırsanız, bunu özellikle açıklayacağım. Öncelikle ikili ağacın düğüm tanımını veriyoruz (bu tanım size aşina olmalı, bir fırça algoritmanız varsa onunla karşılaşacaksınız).
public class TreeNode {
int val;
TreeNode kaldı;
TreeNode sağ;
TreeNode (int x) {val = x;}
}
Özyineleme
Bununla birlikte, burada dikkat edilmesi gereken bir nokta, sözde koddaki "istenen işlemi gerçekleştirme" konumunun onu yerleştirdiğim yerde olması gerekmediğidir.Özel konum farklı gerçek ihtiyaçlara göre değerlendirilmelidir. Ancak, birinci, orta ve son mertebenin geçişi nedeniyle, yinelemeli giriş zamanlaması benimki ile aynı olmalıdır.
Ön sipariş geçişi
Kök düğüm boşsa, kök düğümü çaprazlayın, geri dönün; aksi takdirde, kök düğümü çaprazlayın ve sonra önce soldaki alt ağaçtan geçin ve sonra ilk önce sağ alt ağacı çaprazlayın.
public void preorderTraverse (TreeNode kökü) { System.out.print (node.val + ""); preorderTraverse (kök.left); preorderTraverse (root.right); }Sıralı geçiş
Kök düğümü geçmek, kök düğüm boşsa, geri dönün; aksi takdirde, orta sıra soldaki alt ağaçtan, ardından kök düğümü ve ardından orta sıra, sağ alt ağaçtan geçer.
public void inorderTraverse (TreeNode kökü) { inorderTraverse (root.left); System.out.print (node.val + ""); inorderTraverse (root.right); }Sipariş sonrası geçiş
Kök düğümü geçmek, kök düğüm boşsa, geri dönün; aksi takdirde, sol alt ağaç son sırada geçilir, sağ alt ağaç son sırada geçilir ve kök düğüm son olarak geçilir.
public void postorderTraverse (TreeNode kökü) { postorderTraverse (root.left); postorderTraverse (root.right); System.out.print (node.val + ""); }
Yineleme (yinelemeli olmayan)
Yineleme fikrini kullanıyoruz, aslında yinelemeli işlemleri simüle etmek için döngüler ve yığınlar kullanıyoruz.Yukarıdaki yinelemeli işlemler aslında kendilerini ve sol ve sağ alt düğümlerini sürekli olarak itip çıkarma işlemidir. Yukarıdaki algoritmayı anlıyorsanız, Algoritmanın anlaşılması kolaydır
Ön sipariş geçişi
genel Liste < Tamsayı > preorderTraversal (TreeNode kökü) { Liste < Tamsayı > list = new ArrayList < > ; if (root ==) { iade listesi; } Yığın < TreeNode > yığın = yeni Yığın < > ; stack.push (kök); while (! stack.isEmpty) { TreeNode res = stack.pop; eğer (res.right! =) stack.push (res.right); eğer (res.left! =) stack.push (res.left); list.add (res.val); } iade listesi; }Sıralı geçiş
genel Liste < Tamsayı > inorderTraversal (TreeNode kökü) { Liste < Tamsayı > list = new ArrayList < > ; if (root ==) { iade listesi; } Yığın < TreeNode > yığın = yeni Yığın < > ; TreeNode curr = kök; while (curr! = ||! (stack.isEmpty)) { eğer (curr! =) { stack.push (curr); curr = curr.left; }Başka{ curr = stack.pop; list.add (curr.val); curr = curr.right; } } iade listesi; }Sipariş sonrası geçiş
Başka bir geçişi kolayca uygulayabiliriz: "root- > sağ- > Sol "çapraz geçiş. Bu tür bir geçişin adı olmamasına rağmen, bu, sipariş sonrası geçişin tersidir. Böylece, iki yığın kullanabilir ve sonraki çapraz geçişleri elde etmek için yığının LIFO özelliklerini kullanabiliriz.
genel Liste < Tamsayı > preorderTraversal (TreeNode kökü) { Liste < Tamsayı > list = new ArrayList < > ; if (root ==) { iade listesi; } Yığın < TreeNode > yığın = yeni Yığın < > ; stack.push (kök); while (! stack.isEmpty) { TreeNode res = stack.pop; eğer (res.left! =) stack.push (res.left); eğer (res.right! =) stack.push (res.right); list.add (res.val); } list.reserve; iade listesi; }
İlk Derinlik Arama (DFS)
Aslında, ikili ağaçların birinci dereceden çapraz geçişi, orta dereceden geçişi ve sıra sonrası geçişi, hepsi ilk derinlik aramadır. Derin arama bir fikirdir ve özellikle uygulama yöntemine atıfta bulunmaz. Bunu uygulamak için özyineleme veya yığın kullanabilirsiniz. Yukarıda bahsedilenler, sonuçta "önce derinlik" aramasının tüm uygulamalarıdır.
Burada izlenimi derinleştirmek için birkaç pratik uygulama örneğinden bahsediyorum.
Maksimum ikili ağaç derinliği
public int maxDepth (TreeNode kökü) { if (root ==) { dönüş 0; } int left = maxDepth (kök.left); int sağ = maxDepth (root.right); Dönüş Math.max (sol, sağ) +1; }İkili Ağacın Aynası
public void Mirror (TreeNode kökü) { eğer (kök! =) { eğer (root.left! = || root.right! =) { TreeNode temp = root.left; root.left = root.right; root.right = temp; } Ayna (kök.left); Ayna (kök. Sağ); } }Simetrik İkili Ağaç
boole isSymmetrical (TreeNode pRoot) { eğer (pRoot ==) doğruya dön; gerçek dönüş (pRoot.left, pRoot.right); } genel boole gerçek (TreeNode root1, TreeNode root2) { eğer (root1 == root2 ==) { doğruya dön; } eğer (root1 == || root2 ==) { yanlış dönüş; } eğer (root1.val! = root2.val) { yanlış dönüş; } dönüş gerçek (root1.left, root2.right) real (root1.right, root2.left); }Yol toplamı
public class Solution { özel DiziListesi < Tamsayı > list = new ArrayList < Tamsayı > ; özel DiziListesi < Dizi Listesi < Tamsayı > > listAll = new ArrayList < Dizi Listesi < Tamsayı > > ; public ArrayList < Dizi Listesi < Tamsayı > > FindPath (TreeNode kökü, int hedef) { eğer (kök ==) return listAll; list.add (root.val); hedef - = root.val; eğer (target == 0 root.left == root.right ==) { listAll.add (yeni ArrayList < Tamsayı > (liste)); } FindPath (kök.left, hedef); FindPath (root.right, hedef); list.remove (list.size-1); return listAll; } }İkili Ağacı Yeniden Oluştur
public TreeNode reConstructBinaryTree (int pre, int in) { reConstructBinaryTree (pre, 0, pre.length-1, in, 0, in.length-1); } public TreeNode reConstructBinaryTree (int pre, int startpre, int endpre, int in, int startin, int endin) { eğer (başlangıç > endpre || startin > endin) { dönüş; } TreeNode kökü = yeni TreeNode (ön); for (int i = startin; i < = endin; i ++) { eğer (içinde == pre) { root.left = reConstructBinaryTree (pre, startpre + 1, startpre + i-startin, in, startin, i-1); root.right = reConstructBinaryTree (pre, startpre + i-startin + 1, endpre, in, i + 1, endin); } } dönüş kökü; }İkili arama ağacının en yakın ortak atası
class Solution { public TreeNode lowerCommonAncestor (TreeNode kökü, TreeNode p, TreeNode q) { eğer (kök == || kök == p || kök == q) { dönüş kökü; } TreeNode left = bottomCommonAncestor (kök.left, p, q); TreeNode right = lowerCommonAncestor (root.right, p, q); eğer (sol! = sağ! =) { dönüş kökü; } sola dönüş! =? sol: sağ; } }İkili ağaçların serileştirilmesi ve serileştirilmesi
Serileştirme: public String serileştirme (TreeNode kökü) { if (root ==) { dönüş; } // İkili ağaç hiyerarşik geçişini kullanarak serileştirme StringBuilder res = new StringBuilder; Bağlantılı liste < TreeNode > queue = yeni LinkedList < > ; queue.add (kök); while (! queue.isEmpty) { TreeNode düğümü = queue.remove; eğer (düğüm! =) { res.append (node.val) .append (","); queue.add (node.left); queue.add (node.right); } Başka { res.append (","); } } res.toString döndür; } Seriyi kaldırma: public TreeNode serisini kaldırma (Dize verileri) { eğer (data == || data.length == 0) { dönüş; } Dize dataArr = data.split (","); // Seviye geçişi ters geri yükleme ikili ağaç int indeksi = 0; TreeNode kökü = toNode (dataArr); Bağlantılı liste < TreeNode > queue = yeni LinkedList < > ; queue.add (kök); while (dizin < dataArr.length-2! queue.isEmpty) { TreeNode cur = queue.remove; // Sol alt düğüm ekle TreeNode leftNode = toNode (dataArr); cur.left = leftNode; // Kuyruktaki düğüm, kendisine bir çocuk düğüm atamak için kullanılır, düğümün kendisi ise, // Alt düğüm yoksa, artık kuyruğa eklenmez, aşağıda aynısı geçerlidir eğer (leftNode! =) { queue.add (leftNode); } // Sağ alt düğüm ekle TreeNode rightNode = toNode (dataArr); cur.right = rightNode; eğer (rightNode! =) { queue.add (rightNode); } } dönüş kökü; } private TreeNode toNode (Dize değeri) { eğer (! "". equals (val)) { yeni TreeNode (Integer.parseInt (val)) döndür; } Başka { dönüş; } }
Kapsamlı İlk Arama (BFS)
Önce kök düğümü sıraya koyun.
Kuyruktan ilk düğümü alın ve hedef olup olmadığını kontrol edin.
Hedef bulunursa, arama sona erer ve sonuç döndürülür.
Aksi takdirde, kontrol edilmemiş tüm doğrudan alt düğümleri kuyruğa eklenir.
Kuyruk boşsa, resmin tamamı kontrol edilmiş demektir, yani resimde aranacak hedef yoktur. Aramayı sonlandırın ve "hedef bulunamadı" döndür.
2. adımı tekrarlayın.
Morris geçişi (Morris)
Genellikle ikili ağaçtan geçerken, yinelemeli geçiş veya yığın tabanlı geçiş kullanırız.Bu yöntemlerin her ikisi de O (n) 'nin en kötü uzay karmaşıklığına sahiptir (yinelemeli yöntemler yinelemeli çağrılarda daha fazla zaman harcar), Ve O (n) zaman karmaşıklığı. Zaman karmaşıklığı için, her bir elemanın bir kez geçilmesi gerektiğinden, O (n) zaten en uygun durumdur. Bu yalnızca alanı optimize edebilir. Morris geçişi nasıl yapıyor? İlk olarak, özyineleme ve yığın tabanlı geçişin neden O (n) boşluğuna sahip olduğunu analiz etmemiz gerekir. Aşağıdaki şekil, örnek olarak bu basit ikili ağaç geçişini göstermektedir:
Örneğin, 1'den başlayarak sıralı geçiş (LDR):
-
1, çocuk 2'yi bıraktı, yığına 1 koy ve düğüm 2'ye geç;
-
2, çocuk 4'ü bıraktı, 2'yi yığına koydu ve düğüm 4'e geçti;
-
4 Soldaki çocuk boş ve 4. düğüm çıktı Bu zamanda, 4. düğümün sağ çocuğu da boştur ve yığın 2. düğüme geri döner;
-
Çıkış düğümü 2, düğüm 2'nin sağ çocuğu vardır, düğüm 5'e geçin;
-
5 Soldaki çocuk boş ve düğüm 5 çıktı Bu sırada, düğüm 5'in sağ çocuğu da boştur ve yığın düğüm 1'e geri döner;
Yukarıdaki analizden, geleneksel geçişin tüm işlemleri gerçekleştirmeyen üst düğümleri depolamak için boşluk kullandığı anlaşılabilir.Örneğin, bir düğüm için, L işlemi başlangıçta gerçekleştirilir ve D ve R işlemleri gerçekleştirilmez, bu nedenle depolanması gerekir. Bu sorunu çözmek için, Morris algoritması, belirli bir geçiş dizisinin öncülüne veya ardıl düğümüne işaret etmek için yaprak düğümlerinin sol ve sağ boş işaretçilerini kullanan bir "işaret ikili ağaç" kavramını kullanır. Sıralı geçiş süreci Morris algoritması:
-
1. düğümü Geçerli düğüm olarak ayarlayın;
-
Geçerli düğüm boş değildir ve bir sol çocuğu vardır, bu nedenle düğüm 1'in sol alt ağacında, yani düğüm 5'de en sağdaki düğümü bulun ve sağ alt işaretçiyi kendisine, yani bağlantı1'e işaret edin;
-
Geçerli düğüm, sol alt düğüm 2'ye hareket eder ve ana düğümün sol işaretçisini, onu işaret etmesi için siler, yani silme1'i;
-
Düğüm 2 boş değildir ve bir sol çocuğu vardır, bu nedenle düğüm 2'nin sol alt ağacında, yani düğüm 4'te en sağdaki düğümü bulun ve sağ alt göstericinin kendisine, yani bağlantı2'ye işaret etmesini sağlayın;
-
Geçerli düğüm, sol alt düğüm 4'e hareket eder ve ana düğümün sol işaretçisini siler, yani silme 2'yi işaret eder;
-
4. düğümün sol çocuğu boştur, 4. çıkış düğümüdür ve sağ alt düğüm 2'ye hareket eder;
-
Düğüm 2'nin sol alt öğesi (gösterici) yoktur, çıkış düğümü 2'dir ve sağ alt düğüme 5 hareket eder;
-
Düğüm 5'in sol çocuğu yoktur, çıkış düğümü 5 ve sağ alt düğüm 1'e hareket eder;
-
Düğüm 2'nin sol çocuğu yoktur (işaretçi ile gösterilir), çıkış düğümü 1 ve sağ alt düğüm 3'e hareket eder;
-
Kod:
void Morris_inorderTraversal (TreeNode kökü) { TreeNode curr = kök; TreeNode pre; while (curr! =) { if (curr.left ==) {// sol çocuk boş System.out.print (curr.val + ""); curr = curr.right; } else {// sol çocuk boş değil // Soldaki alt ağaçta en sağdaki düğümü bulun pre = curr.left; while (pre.right! =) { pre = pre.right; } // Döngüyü önlemek için sol çocuğu silin pre.right = curr; TreeNode sıcaklığı = akım; curr = curr.left; temp.left =; } } }
AVL ağacı
AVL ağacı dengeli bir ikili ağaçtır ve dengeli ikili ağaç, aşağıdaki gibi özyinelemeli olarak tanımlanır:
-
Sol ve sağ alt ağaçlar arasındaki yükseklik farkı 1'den küçük veya 1'e eşittir.
-
Alt ağaçlarının her biri dengeli bir ikili ağaçtır.
İkili ağacın dengesini sağlamak için, AVL ağacı, ağacın belirli bir kısmının dengesizliği bir eşiği aştığında karşılık gelen dengeleme işlemini tetikleyen sözde denetim mekanizmasını sunar. Ağacın dengesinin kabul edilebilir bir aralıkta olduğundan emin olun. Artık denetim mekanizması tanıtıldığına göre, bir denge işleminin gerekli olup olmadığına karar vermek için bir denetim endeksine ihtiyacımız var. Bu izleme göstergesine "Denge Faktörü" denir. Aşağıdaki gibi tanımlanır:
-
Denge faktörü: Sol alt ağacın yüksekliği ile belirli bir düğümün sağ alt ağacının yüksekliği arasındaki fark.
Denge faktörüne dayanarak, AVL ağacını şu şekilde tanımlayabiliriz.
-
AVL ağacı: Tüm düğümlerin denge faktörünün mutlak değeri 1'i geçmeyen ikili ağaç.
Denge faktörünü hesaplamak için, doğal olarak yükseklik özelliğini düğüme eklememiz gerekir. Burada düğümün yüksekliğini sol ve sağ alt ağaçların yüksekliğinin maksimum değeri olarak tanımlıyoruz. Bu nedenle, AVL ağacının yükseklik özniteliğine sahip düğümü aşağıdaki gibi tanımlanır:
public class TreeNode { int val; int yüksekliği; TreeNode kaldı; TreeNode sağ; TreeNode (int x) {val = x;} }Buradaki düğüm ile yukarıdaki arasındaki fark, her düğümün yüksekliğini kaydetmek için fazladan bir yükseklik eklememizdir.Her düğümün yüksekliğini nasıl elde edeceğiniz çok basittir.Yukarıda bahsedilen algoritmadaki herhangi bir fikir gerçekleştirilebilir. Burada ayrıntılara girmeyeceğim, ancak biraz daha söylemeliyim. Buna bağlı olarak, aşağıdaki işlemleri gerçekleştirdiğimizde etkilenen tüm düğümlerin yüksekliğini güncellememiz gerekiyor:
-
Bir düğüm eklerken, eklenen yol boyunca düğümün yüksekliğini güncelleyin
-
Bir düğümü silerken (sil), silinen yol boyunca düğümün yüksekliğini güncelleyin
Düğümü yükseklik özniteliğiyle yeniden tanımladıktan sonra, denge faktörünü hesaplama işlemi çok basit bir şekilde uygulanabilir, yani bir düğümün denge faktörü = sol düğümün yüksekliği - sağ düğümün yüksekliği.
Denge faktörünün mutlak değeri 1'den büyük olduğunda, ağaç düzeltme veya yeniden dengeleme işlemini tetikleyecektir.
Ağaç dengeleme işlemi
İkili ağacı dengelemek için iki temel işlem vardır: solak ve sağ el. Sola dönüş, saat yönünün tersine dönüş anlamına gelir; sağa dönüş, saat yönünde dönüş anlamına gelir. Bu dönüş, tüm dengeleme işlemi sırasında bir veya daha fazla kez gerçekleştirilebilir.Her iki işlem de dengesiz olan en küçük alt ağacın kök düğümünden (yani, ekleme düğümüne en yakın ve denge faktörü 1'i geçen üst düğümden başlar. ). Bunlar arasında sağ taraftaki işlem şeması aşağıdaki gibidir
Sağ el operasyonu denen işlem, yukarıdaki şekilde B düğümü ve C düğümü arasındaki "ebeveyn-çocuk değişimi" olarak adlandırılır. Yalnızca bu üç düğüm olduğunda, çok basittir. Ancak B düğümünde doğru çocuk olduğunda işler biraz daha karmaşık hale gelir. Her zamanki işlemimiz: sağ çocuğu atmak, onu döndürülmüş C düğümüne bağlamak ve C düğümünün sol çocuğu olmaktır. Bu şekilde ilgili kod aşağıdaki gibidir.
TreeNode treeRotateRight (TreeNode kökü) { TreeNode left = root.left; root.left = left.right; // Döndürülen kökün sol alt öğesi olarak atılacak düğümü bağlayın left.right = root; // baba ve oğul arasındaki ilişkiyi değiştir left.height = Math.max (treeHeight (left.left), treeHeight (left.right)) + 1; right.height = Math.max (treeHeight (right.left), treeHeight (right.right)) + 1; sola dön; }Sol taraftaki çalışma şeması aşağıdaki gibidir
Sol elle çalıştırma, sağ elle çalıştırmaya çok benzer, tek fark, sola ve sağa geçiş yapmanız gerektiğidir. Bu iki işlemi simetrik olarak değerlendirebiliriz. kod aşağıdaki gibi gösterilir:
TreeNode treeRotateLeft (TreeNode kökü) { TreeNode sağ = root.ight; root.right = right.left; right.left = kök; left.height = Math.max (treeHeight (left.left), treeHeight (left.right)) + 1; sağ- > yükseklik = Math.max (treeHeight (right.left), treeHeight (right.right)) + 1; sağa dön; }Dengelenmesi gereken dört durum
-
LL yazın
Sözde LL türü, yukarıdaki şeklin sol tarafındaki durumdur, yani kök düğümün sol çocuğunun sol alt ağacına yeni bir düğüm eklendiğinden, kök düğümün denge faktörü +2 olur ve ikili ağaç dengesini kaybeder. Bu durumda, sağa dönüş düğümü bir kez.
-
RR yazın
RR tipi, LL tipine tamamen simetriktir. Düzeltmek için düğümü yalnızca bir kez sola döndürmeniz gerekir.
-
LR yazın
LR, n'nin sol çocuğunun sağ alt ağacına yeni bir düğüm eklenmesinden kaynaklanan bir dengesizliktir. Şu anda ihtiyacımız olan şey i üzerinde sola dönüş ve sonra n'de sağa dönüş yapmaktır.
-
RL yazın
RL, n'nin sağ çocuğunun sol alt ağacına yeni bir düğüm eklenmesinden kaynaklanan bir dengesizliktir. Şu anda ihtiyacımız olan şey, önce i üzerinde bir sağa dönüş ve sonra n üzerinde bir sola dönüş yapmaktır.
Bu dört durumun yargılanması çok basit. Denge türünü, ağacın dengesini bozan düğüme (denge faktörünün mutlak değeri 1'den büyüktür) ve alt düğümlerinin denge faktörüne göre değerlendiririz.
Dengeleme işleminin gerçekleştirilmesi şu şekildedir:
int treeGetBalanceFactor (TreeNode kökü) { eğer (kök ==) dönüş 0; Başka return x.left.height-x.right.height; } TreeNode treeRebalance (TreeNode kökü) { int faktör = treeGetBalanceFactor (kök); eğer (faktör > 1 treeGetBalanceFactor (root.left) > 0) // LL return treeRotateRight (kök); else if (faktör > 1 treeGetBalanceFactor (root.left) < = 0) {// LR root.left = treeRotateLeft (root.left); return treeRotateRight (temp); } else if (faktör < -1 treeGetBalanceFactor (root.right) < = 0) // RR return treeRotateLeft (kök); else if ((faktör < -1 treeGetBalanceFactor (root.right) > 0) {// RL root.right = treeRotateRight (root.right); return treeRotateLeft (kök); } else {// Hiçbir şey olmadı. dönüş kökü; } }İşte dinamik bir AVL ağacına sahip bir web sitesi. AVL dinamik görselleştirme ile anlaşılabilir:
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Orijinal bağlantı: https://blog.csdn.net/DBC_121/article/details/104584060
Feragatname: Bu makale CSDN blogger'ın orijinal makalesidir ve telif hakkı yazara aittir.
