İkili arama ağacının uygulanması

2024 Yazar: Angel Austin | [email protected]. Son düzenleme: 2023-12-17 05:44

İkili arama ağacı - düğümleri, sağ ve sol diğer düğümlere iki bağlantı içeren yapılandırılmış bir veritabanı. Düğümler, veri içeren sınıfın bir nesnesidir ve NULL, ağacın sonunu gösteren işarettir.

Genellikle özel bir özelliği olan BST olarak anılır: kökten daha büyük düğümler kök kökün sağında ve daha küçük olanlar solunda bulunur.

Genel teori ve terminoloji

İkili arama ağacında, kök hariç her düğüm, ebeveyn olarak adlandırılan bir düğümden diğerine yönlendirilmiş bir kenarla bağlanır. Her biri, çocuk adı verilen rastgele sayıda düğüme bağlanabilir. "Alt" olmayan düğümlere yaprak (dış düğümler) denir. Yaprak olmayan elemanlara iç denir. Aynı ebeveyne sahip düğümler kardeştir. En üstteki düğüme kök denir. BST'de, her bir düğüme bir eleman atayın ve onlar için özel bir özellik setine sahip olduklarından emin olun.

Ağaç terminolojisi:

Bir düğümün derinliği, kökten ona kadar tanımlanan kenarların sayısıdır.
Bir düğümün yüksekliği, ondan en derin yaprağa kadar tanımlanan kenarların sayısıdır.
Ağacın yüksekliği kökün yüksekliğine göre belirlenir.
İkili arama ağacı özel bir tasarımdır, en iyi yükseklik ve düğüm sayısı oranını sağlar.
En fazla O (log N) N düğümlü h yüksekliği.

En büyük sayıyı içerdiğini varsayarak, kökten başlayarak her seviyedeki düğümleri sayarak bunu kolayca kanıtlayabilirsiniz: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Bunu h için çözmek h=O (log n) verir.

Ahşabın faydaları:

Verilerin yapısal ilişkilerini yansıtın.
Hiyerarşileri temsil etmek için kullanılır.
Etkili kurulum ve arama sağlayın.
Ağaçlar çok esnek verilerdir ve alt ağaçları minimum çabayla taşımanıza olanak tanır.

Arama yöntemi

Genel olarak, bir değerin BST'de olup olmadığını belirlemek için kökünde bir ikili arama ağacı başlatın ve gereksinimleri karşılayıp karşılamadığını belirleyin:

kökte ol;
kökün sol alt ağacında olun;
kökün sağ alt ağacında.

Hiçbir temel kayıt sağlanmazsa, karşılık gelen alt ağaçta özyinelemeli bir arama gerçekleştirilir. Aslında iki temel seçenek var:

Ağaç boş - false döndür.
Değer kök düğümde - true döndür.

Gelişmiş bir şemaya sahip bir ikili arama ağacının her zaman kökten yaprağa giden yol boyunca aramaya başladığına dikkat edilmelidir. En kötü durumda, yaprağa kadar gider. Bu nedenle, en kötü zaman, ağacın yüksekliği olan kökten yaprağa kadar olan en uzun yolun uzunluğu ile orantılıdır. Genel olarak, bu, ağaçta depolanan değerlerin sayısının bir fonksiyonu olarak aramanın ne kadar sürdüğünü bilmeniz gereken zamandır.

Başka bir deyişle, bir BST'deki düğüm sayısı ile ağacın yüksekliği arasında "şekline" bağlı olarak bir ilişki vardır. En kötü durumda, düğümlerin yalnızca bir çocuğu vardır ve dengeli bir ikili arama ağacı esasen bağlantılı bir listedir. Örneğin:

Bu ağacın 5 düğümü vardır ve yüksekliği=5. 16-19 ve 21-29 aralığındaki değerlerin bulunması kökten yaprağa (20 değerini içeren düğüm) yani aşağıdaki yolu gerektirecektir., düğüm sayısıyla orantılı olarak zaman alacaktır. En iyi ihtimalle hepsinin 2 çocuğu olur ve yapraklar aynı derinlikte bulunur.

Bu ikili arama ağacında 7 düğüm vardır ve yükseklik=3'tür. Genel olarak, bunun gibi bir ağacın (tam ağaç) yüksekliği yaklaşık olarak log 2 (N) olacaktır; burada N, ağaçtaki düğüm sayısıdır.. Log 2 (N) değeri, sıfıra ulaşılmadan önce N'nin bölünebileceği (2) sayıdır.

Özetleme: BST'de arama yapmak için gereken en kötü zaman O'dur (ağaç yüksekliği). En kötü durum "doğrusal" ağaç O(N)'dir; burada N, ağaçtaki düğüm sayısıdır. En iyi ihtimalle, "tam" bir ağaç O(log N).

BST ikili ekleme

Nerede olması gerektiğini merak etmekyeni düğüm BST'de bulunur, mantığı anlamanız gerekir, kullanıcının bulduğu yere yerleştirilmelidir. Ayrıca, kuralları hatırlamanız gerekir:

Yinelenenlere izin verilmez, yinelenen bir değer girmeye çalışmak bir istisna oluşturur.
Genel ekleme yöntemi, gerçekten eklemek için bir yardımcı özyinelemeli "yardımcı" yöntemi kullanır.
Yeni bir değer içeren bir düğüm her zaman BST'ye yaprak olarak eklenir.
Genel ekleme yöntemi void döndürür, ancak yardımcı yöntem bir BSTnode döndürür. Bunu, kendisine iletilen düğümün null olduğu durumu ele almak için yapar.

Genel olarak, yardımcı yöntem, orijinal ikili arama ağacı boşsa sonucun tek düğümlü bir ağaç olduğunu belirtir. Aksi takdirde sonuç, argüman olarak iletilen aynı düğüme bir işaretçi olacaktır.

İkili algoritmada silme

Beklediğiniz gibi, bir öğeyi silmek, kaldırılacak değeri içeren bir düğüm bulmayı içerir. Bu kodda birkaç şey var:

BST, yardımcı, aşırı yüklenmiş bir silme yöntemi kullanır. Aradığınız öğe ağaçta değilse, yardımcı yöntem sonunda n==null ile çağrılır. Bu bir hata olarak kabul edilmez, bu durumda ağaç değişmez. Silme yardımcı yöntemi bir değer döndürür - güncellenen ağaca bir işaretçi.
Bir yaprak kaldırıldığında, ikili arama ağacından kaldırma, üst öğesinin karşılık gelen alt işaretçisini null değerine veya kaldırılan yaprak kaldırılmışsa kökü null değerine ayarlar.düğüm bir köktür ve çocuğu yoktur.
Silme çağrısının şunlardan biri olması gerektiğini unutmayın: root=delete (kök, anahtar), n.setLeft (delete (n.getLeft (), anahtar)), n.setRight (delete(n. getRight(), anahtar)). Bu nedenle, her üç durumda da silme yönteminin yalnızca null döndürmesi doğrudur.
Silinecek değeri içeren düğümün aranması başarılı olduğunda, üç seçenek vardır: silinecek düğüm bir yapraktır (alt öğesi yoktur), silinecek düğümün bir çocuğu vardır, iki çocuklar.
Kaldırılan düğümün bir çocuğu olduğunda, onu bir alt öğeyle değiştirerek çocuğa bir işaretçi döndürebilirsiniz.
Silinecek düğümün sıfır veya 1 çocuğu varsa, silme yöntemi kökten o düğüme "yolu izleyecektir". Yani hem arama hem de ekleme için en kötü zaman ağacın yüksekliğiyle orantılıdır.

Kaldırılacak düğümün iki çocuğu varsa aşağıdaki adımlar uygulanır:

Kökten ona giden yolu izleyerek silinecek düğümü bulun.
Yaprağa giden yol boyunca devam ederek sağ alt ağaçta v'nin en küçük değerini bulun.
v değerini yinelemeli olarak kaldırın, 2. adımdakiyle aynı yolu izleyin.
Böylece, en kötü durumda, kökten yaprağa giden yol iki kez gerçekleştirilir.

Traverslerin sırası

Geçiş, bir ağaçtaki tüm düğümleri ziyaret eden bir süreçtir. C ikili arama ağacı doğrusal olmayan bir veri yapısı olduğundan, benzersiz bir geçiş yoktur. Örneğin, bazen birkaç çapraz geçiş algoritmasıaşağıdaki iki türe ayrılmıştır:

geçiş derinliği;
ilk geçiş.

Yalnızca bir tür genişlik geçişi vardır - seviyeyi atlamak. Bu geçiş, düğümleri seviye aşağı ve sol, üst ve sağ ziyaret eder.

Üç farklı derinlik geçişi türü vardır:

Ön Siparişi Geçme - önce ebeveyni, ardından sol ve sağ çocuğu ziyaret edin.
Passing In Order - sol çocuğu, ardından ebeveyni ve sağ çocuğu ziyaret etmek.
Post Order - önce sol çocuğu, sonra sağ çocuğu, sonra ebeveyni ziyaret edin.

İkili arama ağacının dört geçişi için örnek:

ÖnSipariş - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Şekil, düğümlerin ziyaret edildiği sırayı gösterir. 1 sayısı belirli bir geçişteki ilk düğümdür ve 7 son düğümdür.

Bu genel geçişler, her düğümün üç kez ziyaret edildiğini varsayarak tek bir algoritma olarak temsil edilebilir. Euler turu, her kenarın kullanıcının geçemeyeceği bir duvar olarak ele alındığı ikili bir ağaç etrafında bir yürüyüştür. Bu yürüyüşte, her bir düğüm ya solda, ya altta ya da sağda ziyaret edilecektir. Soldaki düğümleri ziyaret eden Euler turu, edatın atlanmasına neden olur. Aşağıdaki düğümler ziyaret edildiğinde sırayla geçilir. Ve sağdaki düğümler ziyaret edildiğinde - aladım adım geçiş.

Gezinme ve Hata Ayıklama

Ağaçta gezinmeyi kolaylaştırmak için önce sol veya sağ alt öğe olup olmadığını kontrol eden işlevler oluşturun. Bir düğümün konumunu değiştirmek için, üst düğümdeki işaretçiye kolay erişim olmalıdır. Bir ağacı doğru şekilde uygulamak çok zordur, bu nedenle hata ayıklama işlemlerini bilmeniz ve uygulamanız gerekir. Bir uygulamaya sahip ikili arama ağacında genellikle seyahat yönünü gerçekten göstermeyen işaretçiler bulunur.

Bütün bunları anlamak için, ağacın doğru olup olmadığını kontrol eden ve birçok hatayı bulmaya yardımcı olan bir fonksiyon kullanılır. Örneğin, ana düğümün bir alt düğüm olup olmadığını kontrol eder. Assert(is_wellformed(root)) ile birçok hata zamanından önce yakalanabilir. Bu fonksiyon içinde verilen birkaç kesme noktası kullanarak, tam olarak hangi işaretçinin yanlış olduğunu da belirleyebilirsiniz.

İşlev Konsolenausgabe

Bu işlev, tüm ağacı konsola aktarır ve bu nedenle çok kullanışlıdır. Ağaç çıktı hedefinin yürütüldüğü sıra:

Bunu yapmak için öncelikle düğüm aracılığıyla hangi bilgilerin çıktısının alınacağını belirlemeniz gerekir.
Ayrıca, ne kadar boşluk bırakılacağını hesaplamak için ağacın ne kadar geniş ve uzun olduğunu da bilmeniz gerekir.
Aşağıdaki işlevler, ağaç ve her bir alt ağaç için bu bilgiyi hesaplar. Konsola sadece satır satır yazabileceğiniz için, ağacı satır satır yazdırmanız da gerekecektir.
Şimdi geri çekilmek için başka bir yola ihtiyacımız vartüm ağaç, sadece satır satır değil.
Döküm işlevinin yardımıyla ağacı okuyabilir ve hız açısından çıktı algoritmasını önemli ölçüde iyileştirebilirsiniz.

Ancak, bu işlevi büyük ağaçlarda kullanmak zor olacaktır.

Yapıcıyı ve yıkıcıyı kopyalayın

Ağaç önemsiz bir veri yapısı olmadığı için, bir kopya oluşturucu, bir yıkıcı ve bir atama operatörü uygulamak daha iyidir. Yıkıcının özyinelemeli olarak uygulanması kolaydır. Çok büyük ağaçlar için "yığın taşmasını" kaldırabilir. Bu durumda, iteratif olarak formüle edilir. Buradaki fikir, tüm yaprakların en küçük değerini temsil eden yaprağı çıkarmaktır, bu nedenle ağacın sol tarafındadır. İlk yaprakları kesmek yenilerini yaratır ve ağaç sonunda yok olana kadar küçülür.

Kopyalama oluşturucu özyinelemeli olarak da uygulanabilir, ancak bir istisna atılırsa dikkatli olun. Aksi takdirde, ağaç hızla kafa karıştırıcı ve hataya açık hale gelir. Bu nedenle yinelemeli sürüm tercih edilir. Buradaki fikir, eski ağaçta ve yeni ağaçta, yok edicide yaptığınız gibi, eski ağaçtaki tüm düğümleri klonlayarak, ancak yenilerini klonlamamaktır.

Bu yöntemle, ikili arama ağacı uygulaması her zaman sağlıklı durumdadır ve eksik durumda bile yıkıcı tarafından kaldırılabilir. Bir istisna oluşursa, tek yapmanız gereken yıkıcıya yarı bitmiş ağacı silmesini söylemektir. atama operatörüKopyala ve Değiştir kullanılarak kolayca uygulanabilir.

İkili arama ağacı oluşturma

Optimal ikili arama ağaçları, düzgün yönetilirse inanılmaz derecede verimlidir. İkili arama ağaçları için bazı kurallar:

Bir üst düğümde en fazla 2 alt düğüm bulunur.
Sol alt düğüm her zaman üst düğümden küçüktür.
Geçerli bir alt düğüm her zaman üst düğümden büyük veya ona eşittir.

İkili arama ağacını oluşturmak için kullanılacak dizi:

Sıralanmamış sırada yedi değerden oluşan bir temel tamsayı dizisi.
Dizideki ilk değer 10'dur, bu nedenle ağacı oluşturmanın ilk adımı burada gösterildiği gibi 10 kök düğüm oluşturmaktır.
Bir dizi kök düğüm ile diğer tüm değerler bu düğümün çocukları olacaktır. Kurallara atıfta bulunarak, ağaca 7 eklemek için atılması gereken ilk adım, onu kök düğümle karşılaştırmaktır.
7 değeri 10'dan küçükse, sol alt düğüm olur.
7 değeri 10'dan büyük veya ona eşitse, sağa hareket eder. 7'nin 10'dan küçük olduğu bilindiği için sol alt düğüm olarak belirlenir.
Her öğe için yinelemeli olarak karşılaştırmalar yapın.
Aynı kalıbı takip ederek dizideki 14. değerle aynı karşılaştırmayı yapın.
14 değerini kök düğüm 10 ile karşılaştırmak, 14'ün doğru çocuk olduğunu bilmek.
Dizi boyunca yürümek,20'ye gel.
Diziyi 10 ile (hangisi daha büyükse) karşılaştırarak başlayın. Sağa gidin ve 14 ile karşılaştırın, o 14'ün üzerinde ve sağda çocuğu yok.
Şimdi 1 değeri var. Diğer değerlerle aynı kalıbı takip ederek 1 ile 10'u karşılaştırın, sola doğru ilerleyin ve 7 ile karşılaştırın ve son olarak 7. düğümün 1 sol çocuğuyla karşılaştırın.
Değer 5 ise, 10 ile karşılaştırın. 5, 10'dan küçük olduğu için sola geçin ve 7 ile karşılaştırın.
5'in 7'den küçük olduğunu bilerek, ağaçtan aşağı doğru devam edin ve 5'i 1 değerle karşılaştırın.
1'in çocuğu yoksa ve 5, 1'den büyükse, 5, 1 düğümün geçerli bir alt öğesidir.
Son olarak ağaca 8 değerini ekleyin.
8, 10'dan küçük olduğunda, sola hareket ettirin ve 7 ile karşılaştırın, 8, 7'den büyüktür, bu yüzden onu sağa hareket ettirin ve ağacı tamamlayın, 8'i 7'nin uygun bir çocuğu yapın.

Optimal ikili arama ağaçlarının basit zarafetini elde etme ve değerlendirme. Programlamadaki birçok konu gibi, ikili arama ağaçlarının gücü, verileri küçük, ilgili bileşenlere çözümleme yeteneklerinden gelir. Şu andan itibaren tüm veri kümesiyle düzenli bir şekilde çalışabilirsiniz.

Potansiyel İkili Arama Sorunları

İkili arama ağaçları harikadır, ancak akılda tutulması gereken birkaç uyarı vardır. Genellikle sadece dengeli olduklarında etkilidirler. Dengeli bir ağaç, içinde bulunduğu ağaçtır.ağaçtaki herhangi bir düğümün alt ağaçlarının yükseklikleri arasındaki fark en fazla birdir. Kuralları netleştirmeye yardımcı olabilecek bir örneğe bakalım. Dizinin sıralanabilir olarak başladığını düşünelim.

Bu ağaç üzerinde bir ikili arama ağacı algoritması çalıştırmayı denerseniz, tam olarak istenen değer bulunana kadar dizi boyunca yineleniyormuş gibi çalışacaktır. İkili aramanın gücü, istenmeyen değerleri hızla filtreleyebilme yeteneğinde yatmaktadır. Bir ağaç dengeli olmadığında dengeli bir ağaçla aynı faydaları sağlamayacaktır.

İkili arama ağacı oluştururken kullanıcının üzerinde çalıştığı verileri incelemek çok önemlidir. Tamsayıları dengelemek için ikili bir arama ağacı uygulamadan önce dizi rastgeleleştirme gibi rutinleri entegre edebilirsiniz.

İkili arama hesaplama örnekleri

Aşağıdaki ikili arama ağacına 25 eklenirse ne tür bir ağacın sonuçlanacağını belirlememiz gerekiyor:

5 15

/ /

2 12 20

Henüz x içermeyen bir T ağacına x eklerken, x anahtarı her zaman yeni bir yaprağa yerleştirilir. Bununla bağlantılı olarak, yeni ağaç şöyle görünecek:

5 15

/ /

2 12 20

Aşağıdaki ikili arama ağacına 7 eklerseniz ne tür bir ağaç elde edersiniz?

5 15

/ /

2 12 20

Cevap:

5 15

/ / /

2 7 12 20

Herhangi bir nesneyi saklamak için ikili arama ağacı kullanılabilir. Bağlantılı bir liste yerine ikili arama ağacı kullanmanın avantajı, eğer ağaç makul ölçüde dengeliyse ve "doğrusal" bir ağaçtan çok "dolu" bir ağaç gibiyse, ekleme, arama ve tüm silme işlemlerinin çalıştırmak için uygulanabilmesidir. O(log N) zamanı.