Üçlü ağaç - Ternary tree

Boyu 10 ve yüksekliği 2 olan basit bir üçlü ağaç.

Gelen bilgisayar bilimleri , bir üçlü ağaç bir olan ağaç veri yapısı her bir düğüm sahip olduğu en fazla üç çocuk düğümleri genellikle "sol", “orta” ve "doğru" olarak ayırt. Çocuklu düğümler, ebeveyn düğümlerdir ve alt düğümler, ebeveynlerine referanslar içerebilir. Ağacın dışında, varsa, "kök" düğüme (tüm düğümlerin atası) bir referans vardır. Veri yapısındaki herhangi bir düğüme, kök düğümden başlayarak ve sol, orta veya sağ çocuğa yapılan referansları tekrar tekrar izleyerek ulaşılabilir.

Üçlü ağaçlar, Ternary arama ağaçlarını ve Ternary yığınlarını uygulamak için kullanılır .

Tanım

• Yönlendirilmiş Kenar - Ebeveynden çocuğa olan bağlantı.
• Kök - Üst öğesi olmayan düğüm. Köklü bir ağaçta en fazla bir kök düğüm vardır.
• Yaprak Düğümü - Çocuğu olmayan herhangi bir düğüm.
• Ana Düğüm - Yönlendirilmiş bir uçla alt veya alt öğelerine bağlı herhangi bir düğüm.
• Alt Düğüm - Bir ana düğüme yönlendirilmiş bir kenarla bağlanan herhangi bir düğüm.
• Derinlik - Kökten düğüme giden yolun uzunluğu. Belirli bir derinlikteki tüm düğümlerin kümesine bazen ağaç düzeyi denir. Kök düğüm sıfır derinliktedir.
• Yükseklik - Kökten ağaçtaki en derin düğüme kadar olan yolun uzunluğu. Yalnızca bir düğüme (kök) sahip (köklü) bir ağacın yüksekliği sıfırdır. Örnek diyagramda ağacın yüksekliği 2'dir.
• Kardeş - Aynı ana düğümü paylaşan düğümler.

- Bir düğüm p, q düğümünden köke giden yolda varsa, q düğümünün atasıdır. Düğüm q daha sonra p'nin soyundan gelir.

- Bir düğümün boyutu, kendisi dahil sahip olduğu neslin sayısıdır.

Üçlü ağaçların özellikleri

• Maksimum düğüm sayısı

- Üçlü bir ağacın yüksekliği olsun . ${\ displaystyle h}$

- h yüksekliğindeki üçlü ağaçtaki maksimum düğüm sayısı olsun ${\ displaystyle M (h)}$

- ${\ displaystyle M (h) = 1 + 3 + 9 + \ cdots + 3 ^ {h} = \ toplam _ {i = 0} ^ {h} 3 ^ {i} = {\ frac {3 ^ {h + 1} -1} {2}}}$

- Her h yüksekliğindeki ağacın en çok düğümü vardır. ${\ displaystyle {\ frac {3 ^ {h + 1} -1} {2}}}$

• Bir düğüm TREE'yi işgal ederse , Sol Çocuğu TREE'de saklanır . ${\ displaystyle N}$${\ displaystyle [k]}$${\ displaystyle [3k-1]}$
• Mid Child , TREE'de saklanır . ${\ displaystyle [3k]}$
• Sağ Çocuk , TREE'de saklanır . ${\ displaystyle [3k + 1]}$

Ortak işlemler

Yerleştirme

Düğümler, diğer üç düğüm arasındaki üçlü ağaçlara eklenebilir veya bir harici düğümden sonra eklenebilir . Üçlü ağaçlarda, eklenen bir düğüm hangi alt öğe olduğu belirtilir.

Harici düğümler

Üzerine eklenen harici düğümün A düğümü olduğunu söyleyin. A düğümünden sonra yeni bir düğüm eklemek için, A yeni düğümü alt düğümlerinden biri olarak atar ve yeni düğüm A düğümünü ebeveyn olarak atar.

İç düğümler

Dahili düğümlere ekleme, harici düğümlere göre daha karmaşıktır. Dahili düğümün A düğümü olduğunu ve B düğümünün A'nın çocuğu olduğunu söyleyin (Ekleme bir sağ çocuk eklemekse, B, A'nın sağ alt öğesi ve benzer şekilde bir sol alt ekleme veya orta çocuk ile benzer şekilde). A, alt üyesini yeni düğüme atar ve yeni düğüm ebeveynini A'ya atar. Ardından yeni düğüm, çocuğunu B'ye atar ve B, ebeveynini yeni düğüm olarak atar.

Silme

Silme, ağaçtan bir düğümün kaldırıldığı süreçtir. Üçlü ağaçtaki yalnızca belirli düğümler net bir şekilde kaldırılabilir.

Sıfır veya bir çocuklu düğüm

Silinecek düğümün A düğümü olduğunu söyleyin. Bir düğümün çocuğu yoksa ( harici düğüm ), silme işlemi, A'nın ebeveyninin alt öğesini null ve A'nın ebeveyninin null olarak ayarlanmasıyla gerçekleştirilir . Bir çocuğu varsa, A'nın çocuğunun ebeveynini A'nın ebeveynine ayarlayın ve A'nın ebeveyninin çocuğunu A'nın çocuğuna ayarlayın.

Diğer ağaçlarla karşılaştırma

Aşağıdaki resim, iki harfli 12 kelimeyi temsil eden bir ikili arama ağacıdır . Sol çocuktaki tüm düğümler daha küçük değerlere sahipken, sağ çocuktaki tüm düğümler tüm düğümler için daha büyük değerlere sahiptir. Kökten bir arama başlar. "AÇIK" kelimesini bulmak için onu "IN" ile karşılaştırıp doğru dalı alıyoruz. Her karşılaştırma, her iki kelimenin her karakterine erişebilir.

        in
      /    \
     be    of
    /  \  /  \
   as  by is  or
    \   \  \  / \
    at  he it on to 

Dijital arama, dizeleri karakter karakter saklamaya çalışır. Bir sonraki resim, aynı 12 kelime grubunu temsil eden bir ağaçtır;

         _ _ _ _ _ _ _ _ _ _ _ _ _ 
        /     /    / \       \     \
       /     /    /   \       \     \
      a     b    h     i       o     t
     / \   / \   |   / | \    /|\    |
    s  t  e   y  e  n  s  t  f n r   o
   as at be  by he in is it of on or to

her girdi sözcüğü, kendisini temsil eden düğümün altında gösterilir. Küçük harflerden oluşan kelimeleri temsil eden bir ağaçta, her düğüm 26 yönlü dallara sahiptir. Aramalar çok hızlıdır: "IS" araması kökte başlar, "I" dalını, ardından "S" dalını alır ve istenen düğümde sona erer. Her düğümde, kişi bir dizi öğesine erişir, boş değeri test eder ve bir dal alır.

                    i
              /     |    \
             /      |     \
            b       s      o
         / |  \    / \    |  \
        a  e   h  n   t   n   t
        |   \  |         / \  |
        s    y e        f  r  o
         \
          t

Yukarıdaki resim, aynı 12 kelime kümesi için dengeli bir üçlü arama ağacıdır. Alçak ve yüksek işaretçiler açılı çizgilerle gösterilirken, eşit işaretçiler dikey çizgiler olarak gösterilir. "IS" sözcüğü için bir arama kökte başlar, eşit çocuktan aşağı "S" değerine sahip düğüme ilerler ve iki karşılaştırmadan sonra orada durur. "AX" araması, kelimenin ağaçta olmadığını bildirmeden önce ilk harf "A" ile üç, ikinci harf "X" ile iki karşılaştırma yapar.

Üçlü ağaç örnekleri

• Üçlü arama ağacı
• Üçlü yığın
• İlkel Pisagor üçe ihtiva eden iki sonsuz üçlü ağaç açıklanmıştır ilkel Pisagor üçe ağaç ve Pisagor üçe üretilmesi için Formül . Her iki ağaçtaki kök düğüm üçlü [3,4,5] içerir.

Ayrıca bakınız

• İkili ağaç
• Ağaç yapısı

Referanslar