blog posts

Diziler, bağlantılı listeler , yığınlar ve kuyruklar gibi diğer veri yapıları doğrusal veri yapılarıdır ve tüm bu yapılar verileri sıralı olarak depolar ve bunun sonucunda veri boyutu arttıkça ekleme ve silme gibi işlemleri gerçekleştirmek için zaman karmaşıklığı artar. bugünün bilgi işlem dünyasında kabul edilemez. Ağaçların doğrusal olmayan yapısı, geçiş ve kontrol yöntemlerini kullanarak depolama süreçlerini, veri erişimini ve veri işlemeyi geliştirir.

Veri yapılarında yaygın ağaç terimleri

Ağaç, bir düğümler koleksiyonu olarak tanımlanan hiyerarşik bir veri yapısıdır. Bir ağaçta, düğümler değerleri temsil eder ve kenarlarla bağlanır. Aşağıdaki resim, veri yapısı ağacında kullanılan bazı ana terimleri görsel olarak göstermektedir.

Aşağıda bu terimlerin ve ağacın bileşenlerinin her biri kısaca açıklanmış ve sonunda ağacın yapıdaki ortak terimleri tablosuna erişim linki verilmiştir.

• Kök : Ağaç veri yapısında, kök düğüm ilk düğüm veya üst düğümdür. Kök düğüm, tüm ağacın kaynaklandığı düğümdür. Kök düğümün bir ebeveyni yoktur ve yalnızca alt düğümleri vardır. Yukarıdaki resimde, A düğümü ağacın kökü olarak kabul edilir.
• Ana Düğüm : Varsayılan bir düğümden hemen önce bulunan bir düğüme, varsayılan düğümün ana düğümü denir. Yukarıdaki resimde B, E ve F’nin ebeveynidir.
• Alt Düğüm : Varsayılan bir düğümden hemen sonra gelen ve onun mirasçıları olarak kabul edilen tüm düğümler, varsayılan düğümün çocuklarıdır. Yukarıdaki resimde, F ve E, B’nin çocuklarıdır.
• Yaprak : Çocuğu olmayan bir düğüme yaprak denir. Genellikle bir ağacın sınır düğümleri veya ağacın son düğümleri ağacın yaprakları olarak adlandırılır. Yukarıdaki görüntüde E, F, J, K, H, I yaprak düğümleridir.
• Kenar : Kenar, iki düğüm arasındaki bir bağlantıdır ve bu iki düğüm arasındaki bir bağlantı çizgisiyle gösterilir. n düğümlü bir ağaçta kenar sayısı n- 1 olacaktır . Yukarıdaki görüntüde, A ve B veya A ve C veya B ve F veya birbirine bağlanan diğer düğümler arasındaki bağlantı çizgisine kenar denir.
• Kardeşler : Gerçek hayatta kardeşler, aynı ebeveynlere sahip insanlar anlamına gelir, benzer şekilde ağaçlarda, ortak ebeveynlere sahip düğümler kardeş olarak kabul edilir. Yukarıdaki resimde H ve ben ikiziz.
• Yol : Yol, kaynak düğümden hedef düğüme kadar ardışık bir dizi kenardır. Yukarıdaki resimde, A, C, G, K, A düğümünden K’ye giden yoldur.
• Düğüm Yüksekliği : Bir düğümün yüksekliği, o düğüm ile bir yaprak arasındaki en uzun yolun kenar sayısını gösterir. Yukarıdaki resimde A, C, G ve K yüksekliği oluşturmaktadır. A’nın yüksekliği, A ile K arasındaki kenar sayısı 3’e eşittir. Benzer şekilde, G’nin yüksekliği bire eşittir çünkü bir sonraki yaprak düğüme yalnızca bir kenarı vardır.
• Düğüm Düzeyleri : Bir düğümün düzeyi, o düğümün üretimini gösterir. Kök düğüm sıfır seviyesindedir ve bir sonraki alt düğümü birinci seviyededir ve torunu 2. seviyededir. Yukarıdaki resimde H, I ve J’nin seviyesi 3’e ve D, E, F ve G’nin seviyesi 2’ye eşittir.
• Düğüm Derecesi : Varsayılan bir düğümün derecesi, varsayılan düğümün alt düğümlerinin sayısıdır. Yukarıdaki görselde D’nin derecesi 2’ye, C’nin derecesi de 3’e eşittir.
• Visiting : Programa göre belirli bir node’a navigasyon yapıldığında, o anki node’un değerine ulaşılması veya kontrol edilmesi ziyaret olarak adlandırılır.
• İç Düğüm : En az bir çocuğu olan bir düğüm, iç düğüm olarak bilinir. Yukarıdaki resimde, E, F, J, K, H, I dışındaki tüm düğümler dahilidir.
• Traversing : Traversing, bir düğümü belirli bir sırayla ziyaret etme işlemidir. Önceden sıralanmış, önceden sıralanmış ve sıralanmış geçişleri içeren üç tür geçiş vardır.
• Ata Düğümü : Bir düğümün ataları, kökten o düğüme önceki tüm düğümlerdir. Yani, belirli bir düğümle ilgili farklı kuşaklardaki ebeveynler, o düğümün atalarıdır. Yukarıdaki resimde A, C ve G, K ve J düğümlerinin atalarıdır.
• Descendant : Varsayılan bir düğümden hemen sonra yerleştirilen bir düğüme, varsayılan düğümün soyundan gelen denir. Yukarıdaki resimde K, G kuşağındandır.
• Alt ağaç : Bir düğümün alt öğeleri alt ağacı temsil eder. Özyinelemeli bir veri yapısı olarak bir ağaç, kendi içinde birçok alt ağaç içerebilir. Yukarıdaki görüntüde B, E, F düğümleri bir alt ağacı temsil etmektedir.

Veri yapısındaki ağacın teknik terimler tablosunu görüntülemek için buraya tıklayın .

Veri yapısındaki tam ağaç

Tam bir ikili ağaç, mümkün olduğunca soldan sağa doğru doldurulan son seviye dışında tamamen doldurulmuş bir ağaçtır. Tam bir ikili yükseklik ağacı Bir düğümü var. bir ikili ağaçta, bir düğümün yalnızca bir çocuğu olabilir.

Tam İkili Ağaçta, bir düğümün yalnızca bir çocuğu olamaz. bir ikili ağaçta, düğümler soldan sağa doğru doldurulmalıdır.

Ağaç veri yapısının özellikleri

Bu bölümde ağacın yapıdaki önemli özellikleri veya özellikleri ele alınmıştır. Bu özellikler arasında özyineleme, düğüm sayısından kenar sayısını hesaplama imkanı ve diğer şeylerden bahsedebiliriz.

Ağaç veri yapısının yinelenmesi

Geri arama yöntemi, kendisini çağıran bir yöntemdir. Benzer şekilde özyinelemeli bir veri yapısı da kendisini içeren bir yapıdır. Bir ağaç, özyinelemeli bir veri yapısı olarak düşünülebilir çünkü her düğüm, diğer alt ağaçlar için bir kök düğüm olarak kabul edilir. Bu konuyu daha iyi anlamak için aşağıda bir örnek verilmiştir.

Veri yapısındaki ağacın özyinelemeli özelliğini daha iyi anlamak için bir örnek

Aşağıdaki şekilde, kök düğümü “A” olan 1 numaralı ağacı görüyorsunuz. Sırasıyla “C” ve “D” köklerine sahip 2 ve 3 numaralı ağaçları içeren mevcut alt ağaçlar, bağımsız ağaçlar olarak kabul edilir. Bu nedenle, bir ağaç birkaç alt ağaç içerir ve bu nedenle bir ağaç, kendi yinelemeli veri yapısını içerdiğinden yinelemeli bir veri yapısı olarak kabul edilir.

• Not : Yaprak düğümler bile kendi başlarına bir ağaçtır, yani tek başına bir yaprak düğüm, alt düğümler olmadan bir ağaç olarak kabul edilebilir.

Ağaç veri yapısındaki kenar sayısı ile düğüm sayısı arasındaki ilişki düzeltildi

Eğer bir sayı ağacında$$N$$Bir düğüm varsa, kenar sayısı n-1 olacaktır. Kenar, iki düğümü birbirine bağlayan yönlü bir çizgidir.

X düğümünün derinliği, kökten x düğümüne giden yolun uzunluğu olarak tanımlanır. Her kenar, düğümün derinliğini bir birim arttırır. Bu nedenle, x düğümünün derinliği, kök düğümden x düğümüne kadar olan düğüm sayısına eşit kabul edilebilir. X düğümünün derinliği şuna eşittir:

$$DePTH=L+1$$(kökten L düzeyine kadar olan düzey sayısı artı 1)

Yukarıdaki ilişkide L seviyesi, x düğümünün bulunduğu seviyedir. İlk seviyenin sıfır ile başladığına dikkat edilmelidir.

Veri yapılarında ağaç düğümü yüksekliği

Bir düğümün yüksekliği, o düğüm ile bir yaprak arasındaki en uzun yolun kenar sayısını temsil eder. Aşağıda, veri oluşturmada ağaç uygulaması konusu ele alınmıştır; Bundan önce, ilk olarak, daha fazla öğrenme için veri oluşturma ve algoritma tasarımı eğitim kursları serisi tanıtıldı.

Ağaç veri yapısının uygulanması

Aşağıdaki resim ağacın hafızaya nasıl yerleştirildiğini göstermektedir. Buna göre, her düğüm üç alandan oluşur. Düğümün sol kısmı sol çocuğun hafıza adresini, düğümün sağ kısmı sağ çocuğun hafıza adresini ve orta kısım bu düğümde saklanan verileri içerir.

Yukarıdaki ifadeye göre, programlamada her düğüm bir sınıf olarak tanımlanabilir:

Class Node {
    public int value;
    public Node left;
    public Node right; 
}

Yukarıdaki kod parçacığında, sol  bir düğüme (nesne düğüm  ) değerinin değerinden küçük olduğunu gösterir. düğüm güncel aynı şekilde, Sağ  bir düğüme (nesne düğüm  ) değerinin şundan büyük olduğunu gösterir: düğüm  güncel Buradaki tartışma ikili ağaçla ilgilidir. Bir ikili ağacın çoğu durumda iki çocuğu vardır. Yani bir düğümün sıfır, bir veya en fazla 2 çocuğu vardır. Bir jenerik ağacın 2’den fazla çocuğu olabilir.

Veri yapısı ve algoritma tasarımı ile ilgili eğitim videolarının tanıtımı

Ağaç konusu, veri yapısı ve algoritma tasarımı eğitiminin konularından biridir. Veri yapısı ve algoritma tasarımı, bilgisayar bilimlerinin temel, önemli ve önkoşullu dersleri arasındadır. Faradars, veri yapısı ve algoritma tasarımı üzerine kapsamlı ve pratik bir koleksiyon şeklinde eğitim kursları yayınladı. Yukarıdaki resim, bu koleksiyonda sağlanan eğitimlerden yalnızca bazılarını göstermektedir.

• Veri yapısını ve algoritma tasarımını öğrenmeye başlamak ve bu koleksiyondaki tüm derslere erişmek için buraya tıklayın .

Veri yapısında ağacın uygulanması

Ağaç veri yapısı operasyonel olarak uygulanır ve gerçek dünyada kullanılır. Bu uygulamalardan bazıları aşağıda belirtilmiştir.

Ağaç gezintisi

Ağacın en önemli kullanımlarından biri, Belge Nesne Modeli’nde (DOM) gezinmedir.  boyunca “geçiş”, programcıların ilgili düğümlere erişmesine izin verir, böylece belirli bir düğümün tüm kardeşlerine erişim sağlar. Ağaç veri yapısı, HTML yorumlayıcısının tüm HTML belgesinde gezinmesi için bir yol haline gelir.

Ağaç veri yapısı ile arama

hiyerarşik bir veri yapısı olduğundan ve her düğüm bir başka düğüme bağlı olduğundan, belirli bir veri düğümüne erişim kolay ve verimli bir şekilde mümkün olacaktır. Her düğümün en fazla 2 alt düğümü olduğundan, ağacın geliştirilmiş bir versiyonu olan bir ikili arama ağacı düşünün. Yani bu veri yapısında bir sol düğüm ve bir sağ düğüm vardır. Sol düğüm, geçerli düğümün verilerinden daha küçük verileri içerir ve sağ düğüm, geçerli düğümün verilerinden daha büyük verileri içerir. Bu nedenle ikili arama ağacında belirli bir veriyi aramak kolaydır.

İkili arama ağacı optimal arama imkanı sağlamasına rağmen, ikili arama ağacını oluşturmak için daha fazla çabaya ihtiyaç duyulduğu da göz önünde bulundurulmalıdır. Bir ikili arama ağacındaki bir öğeyi aramanın zaman karmaşıklığı veya yürütme sırası O(H)’ye eşittir; burada H, ağacın yüksekliğidir. O(H) yalnızca aramayı verimli kılmakla kalmaz, aynı zamanda ağacın her düğümünde ekleme ve silmeye de izin verir. Bu nedenle, her bir düğümde verimli ekleme ve silme ile bir ağaçta veri düzenlemek de mümkündür.

Veri yapısındaki bir ağaç, her düğümün kullanıcı tarafından verilen bir kararı temsil ettiği bir yapı olarak kullanılabilir. Her düğüm bize iki seçenek sunar ve kullanıcı birini seçtiğinde ağaçta bir adım aşağı iner. Bir yaprağa ulaşarak nihai karara varıyoruz.

Dolayısıyla, herhangi bir uygulamadaki tüm akışlar, her bir akış tanımlanacak ve bir uygulamadaki akışlar (dairesel olmadıkça) sonsuz olmayacak şekilde bir ağaçta görselleştirilebilir.

Örneğin, aşağıdaki şema, kullanıcının bir film seçerken yapması gereken bazı seçimleri göstermektedir. Dolayısıyla ilgili akışlar, kullanıcının izlemek istediği filme ulaşmak için çok sınırlıdır.

Müşteri veya kullanıcı açısından bakıldığında bu yapı aynı görünmeyebilir. Ancak program veya program kodları açısından bakıldığında yukarıdaki görsele benzer bir yapıyı takip eden ağaç benzeri bir veri yapısı vardır. Bu nedenle, ağaç veri yapısı aracılığıyla, kullanıcının mevcut en iyi önerilen filmi bulabilecek şekilde film akış uygulamalarını aramasına olanak tanıyan bir algoritma elde edilir.

Fakat ilgili uygulamanın kullanıcıya önerilen en iyi filmi otomatik olarak gösterme özelliği varsa, kullanıcının o ana kadar izlemediği yeni bir film bulması mümkün mü ve kullanıcının o filmden keyif alma olasılığı maksimum oluyor mu? Bu soruyu cevaplamak için, ağaç yapısının bir başka önemli uygulaması, yani makine öğrenimi önerilmiştir ve bu daha sonra tartışılacaktır.

Makinenin kullanıcı adına otomatik olarak karar vermesi için, makinenin kullanıcının geçmiş seçimlerine uyum sağlaması için kullanıcının manuel veri seçimiyle ilgili çok sayıda geçmiş veriye ve birçok veri eğilimine ihtiyacı vardır.

Bu tür verilerin mevcut olduğu varsayılarak, makineye kendi istatistiklerine ve veri kümesine sahip olması ve böylece verilerdeki eğilimleri ve kalıpları anlaması için ağaç veri yapısına ve geçmiş veri kümesine erişim verilir (bu örnek bağlamında, karar vermenin amacı yapmak, kullanıcı filmi seçer) ve bir şekilde makinenin her düğüm için verileri belirlemesine izin verir.

Verilen veri kümesine dayalı bir sonuca ulaşmak için ağaç veri yapısını kullanarak algoritmayı çalıştıran bir program olduğunu varsayarsak (bu durumda sonuç mümkün olan en iyi filmdir). Başlangıçta, veri yapısı kendisine sağlanan verilerle başlar. Program daha sonra her veri parçasını kullanarak kendini tekrar eder ve tekrar tekrar yanlış sonuçlara ulaşır. Ancak program önemli sayıda yinelemeye ulaştığında, yanlış sonuçlara varma eğilimi azalacaktır çünkü artık kendi istatistiklerine sahip olacaktır (örneğin, kullanıcının en çok hangi kategoriyi izlediği, genellikle ne tür filmleri atladığı, ne tür filmlerden ayrıldığı gibi). bitmemiş ve….

Bu veri eğilimlerine ve istatistiklerine dayalı olarak, ağaç veri yapısı, uygulamanın doğru sonuca, bizim örneğimizde kullanıcı için en iyi filmi seçmeye yönelmesine olanak tanır. Her şey ağaç düğümlerindeki verilere bağlıdır. Program uygun veri eğilimlerini ve istatistikleri toplarsa ve veriler ağaç veri yapısının düğümlerine doğru bir şekilde uygulanırsa ve karar algoritması bir sonraki uygun çocuğun ne olduğunu doğru bir şekilde belirlerse, program çoğunlukla doğru sonucu alacaktır.

• Not : Yukarıdakiler, ağaç veri yapısını gerçek dünya durumlarıyla ilişkilendirmemize izin veren bazı açıklamalardır ve bu, ağaç veri yapısının makine öğrenimine veya karar vermeye veya dosya organizasyonuna nasıl uygulanabileceğine dair yalnızca üst düzey bir fikirdir. bir makine. yaptı

Ağaç yapısının diğer kullanımları arasında şunlar sayılabilir.

• “Yığın Ağacı”, piramit sıralama için kullanılan bir ağaç türüdür.
• Bir “önek ağacı” (Trie), modemi yönlendirici bilgilerine yönlendirmede kullanılan ağacın değiştirilmiş bir versiyonudur.
• B-ağacı bazı veri tabanı yönetim sistemlerinde kullanılır .
• Derleyiciler, program sözdizimini kontrol etmek için sözdizimi ağaçlarını kullanır .

Veri yapısındaki ağaç türleri nelerdir?

Ağaç veri yapısının uygulamalarının açıklamasında, veri yapısındaki bazı ağaç türlerinden dolaylı olarak bahsedilmiştir. Bu bölümde, her tür ağaç yapısını olabildiğince kapsamlı bir şekilde tanıtmaya çalıştık. İlk olarak, veri yapısındaki her ağaç türü aşağıda listelenmiştir.

• genel ağaç
• İkili ağaç
• İkili arama ağacı
• AVL ağacı
• kırmızı-siyah ağaç
• ağaç yaymak
• ağaç

Veri oluşturmada genel ağaç

“Genel Ağaç”, hiyerarşik yapısında düğüm sayısında herhangi bir sınırlama olmayan veri yapısındaki bir ağaç türüdür. Her düğümün sıfır ila n düğümü vardır. Genel ağaç bir kök düğümle başlar ve üst düğümün çocukları başka bir genel alt ağaç oluşturur. Bu nedenle, her kök düğüm bir alt ağaçtır, yani genel bir ağaçta n sayıda alt ağaç vardır. Tüm alt ağaçlar genel bir sırasız ağaçtadır.

Veri yapısındaki genel ağaç özellikleri

Bu ağaç türünün özellikleri aşağıda verilmiştir.

• Genel bir ağaç, bir ağaç veri yapısının tüm özelliklerini takip eder.
• Bir düğüm herhangi bir sayıda düğüme sahip olabilir.

Veri yapısında ikili ağaç

“İkili ağaç”, veri yapısındaki her düğümün maksimum 2 çocuğa (yani sıfır, bir veya 2 çocuk) sahip olabileceği bir ağaç türüdür. Sol çocuk veya sağ çocuk verilerinde herhangi bir kısıtlama yoktur.

Veri yapısındaki ikili ağacın özellikleri

Bu özellikler aşağıda listelenmiştir.

• Bu ağaç türü, ağaç veri yapısının tüm özelliklerini takip eder.
• Bir ikili ağaç en fazla iki alt düğüme sahip olabilir.
• Bu iki çocuğa sol çocuk ve sağ çocuk denir.

Veri yapısında ikili arama ağacı

Veri yapısındaki başka bir ağaç türü, ikili ağacın daha kompakt bir uzantısı olan ikili arama ağacıdır. Bir ikili arama ağacı, tıpkı bir ikili ağaç gibi en fazla 2 çocuğa sahip olabilir. Bu ağaç türü n düğüme sahip olabilir ve ayrıca her düğüm, sol çocuk ve sağ çocuktaki verileri tutan bir veri bölümü olarak tanımlanabilir. Soldaki çocuk, geçerli düğümün verilerinden daha az veri içeren düğüme bir başvuru yapar ve benzer şekilde sağdaki çocuk, geçerli düğümün verilerinden tam olarak daha büyük olan verileri içeren düğüme bir başvuru yapar.

Veri yapısındaki ikili ağacın özellikleri

İkili bir ağacın özellikleri aşağıdaki gibidir.

• Bir ikili ağaç, bir ağaç veri yapısının tüm özelliklerini de takip eder.
• İkili arama ağacının benzersiz bir özelliği vardır. Bu öznitelik, ağacın sol tarafındaki alt düğümün değerinin ağacın üst düğümünün değerinden küçük veya ona eşit olması gerektiğini ve sağdaki alt düğümün değerinin büyük veya ona eşit olması gerektiğini belirtir. ebeveynin değerine.

Veri yapısındaki AVL ağacı

AVL ağacı, veri yapısındaki diğer ağaç türlerinden biridir. Bir ikili ağaç olduğu kadar bir tür ikili arama ağacı olarak da düşünülebilir. Bu ağaç türü hem ikili ağacın özelliklerine hem de ikili arama ağacının özelliklerine sahiptir. Kendi kendini dengeleyen bir ağaçtır, yani sol alt ağaç ile sağ alt ağacın yüksekliğini dengeler.

Bu denge, dengeleme faktörü adı verilen bir şeyle karakterize edilir. Bir ağaç, ikili arama ağacının ve dengeleme faktörünün özelliklerini karşılayan bir AVL ağacı olarak kabul edilir. Sol alt ağaç ile sağ alt ağaç arasındaki yükseklik farkı AVL ağacının yüksekliği olarak kabul edilir. Bir AVL ağacındaki her düğüm için dengeleme faktörünün değeri sıfır, bir ve -1 olmalıdır.

Veri yapısındaki AVL ağaç özniteliklerinin her biri aşağıda listelenmiştir.

• AVL ayrıca ağaç veri yapısının tüm özelliklerini takip eder.
• Kendi kendini dengeliyor.
• Her düğüm, sol alt ağaç ile sağ alt ağaç arasındaki yükseklik farkı olan dengeleme faktörü adı verilen bir değer depolar.
• AVL ağacındaki tüm düğümlerin -1, 0 veya 1 değerlerine sahip bir “Denge Faktörü” vardır.

Veri binasında kırmızı-siyah ağaç

“Kırmızı-Siyah Ağaç”, her düğümün kırmızı veya siyah olduğu, kendi kendini dengeleyen bir ikili arama ağacı olan veri yapısındaki başka bir ağaç türüdür. Düğümlerin rengi, ağacın eklemeler ve silmeler sırasında kabaca dengeli kalmasını sağlamak için kullanılır.

Kırmızı-siyah ağaç ile AVL ağacı arasındaki tek fark, ağacı dengelemek için kaç dönüş gerektiğini bilmememizdir. Ancak kırmızı-siyah ağaçta, ağacı dengelemek için en fazla iki dönüş gerekir. Bu ağaç türü, ağacın dengesini sağlamak için düğümün kırmızı veya siyah rengini gösteren bir bit içerir.

• İkili ağaç veri yapısının tüm özelliklerine sahiptir.
• Kendi kendini dengeliyor.
• Her düğüm ya kırmızı ya da siyahtır.
• Kök ve yaprak düğümleri siyahtır.
• Düğüm kırmızıysa, her iki çocuk da siyahtır.
• Belirli bir düğümden düğümlerinden herhangi birine giden her yol, aynı sayıda siyah düğümden geçmelidir.

Veri yapısında ağaç göster

Gösterim ağacı, veri yapısındaki başka bir ağaç türüdür. Bir dökülme ağacı, kendi kendini dengeleyen bir ikili ağaçtır.

Veri yapısındaki ağaç özelliklerini göster

Veri yapısındaki Splay ağacının özellikleri aşağıda listelenmiştir:

• Bir ikili ağaç veri yapısının özelliklerini takip eder.
• Kendi kendini dengeliyor.
• Son erişilen öğelere yeniden erişmek daha hızlıdır.

Ekleme ve silme gibi işlemler yapıldıktan sonra Splay ağacı devreye girerek “splaying” işlemlerini gerçekleştirmeye başlar ve ağacı yeniden düzenleyerek belirli elemanların ağacın köküne yerleştirilmesini sağlar.

Veri yapısında Treap ağacı

Yolculuk, her düğüme rastgele bir sayısal öncelik atanan ve düğümlerin bu önceliklere göre bir piramit içine yerleştirildiği bir tür ikili arama ağacıdır.

Veri yapısındaki gezi ağacı özellikleri

bu yapısındaki gezi ağacının özellikleri aşağıdaki gibidir:

• Her düğümün iki değeri vardır; Bir anahtar ve bir öncelik.
• Bu ağaç türü, ikili arama ağacının özelliklerini takip eder.
• Treap ağacı önceliği, piramit özelliğini takip eder.

Veri yapılarında ağaç gezintisi

Ağaç geçişi, her bir düğümü ziyaret etme ve değerlerini yazdırma işlemidir. Ağaç veri yapısında gezinmenin üç yolu vardır:

• “Sipariş Sırasında Geçiş”
• “Ön Sipariş Geçişi”
• “Sipariş Sonrası Geçiş”

Aşağıda, ağaç yapısındaki bu 3 gezinme yönteminin her biri ayrı ayrı ele alınmıştır.

Yönteme göre ağacı sırayla geçme

“Sıra İçi Geçiş”te önce sol alt ağaç, ardından kök ve ardından sağ alt ağaç ziyaret edilir.

Ağaçta sırayla algoritma geçişi

In-Order yönteminde ağacı çaprazlama adımlarının her biri aşağıdaki gibidir:

• Adım 1 : Sol alt ağaçta yinelemeli olarak gezinir.
• Adım 2 : Kök düğüm ziyaret edilir.
• Adım 3 : Sağdaki ağacın altında yinelemeli olarak gezinilir.

Ön sipariş yönteminde ağaç geçişi

Sipariş Geçişinde, önce kök düğüm, ardından sol alt ağaç ve son olarak sağ alt ağaç ziyaret edilir.

Ön sipariş yöntemiyle ağacı çaprazlama algoritması

Sipariş yöntemiyle ağaç geçiş algoritmasını uygulama adımları aşağıda listelenmiştir:

• Adım 1 : Kök düğüm ziyaret edilir.
• Adım 2 : Sol alt ağacı yinelemeli olarak kateder.
• Adım 3 : Sağdaki ağacın altında yinelemeli olarak gezinilir.

Ağacı ters sırayla geçmek

“Post-Order Traversal” da önce sol alt ağaç, ardından sağ alt ağaç ve son olarak da kök düğüm ziyaret edilir.

Sipariş sonrası geçiş algoritması

Post-Order yöntemi ile ağacı çaprazlama adımları aşağıda verilmiştir.

• Adım 1 : Sol ağacın altında yinelemeli olarak gezinin.
• Adım 2 : Kök düğümü ziyaret edin.
• Adım 3 : Tekrarlı olarak sağ alt ağaçta gezinin.

Ağaç veri yapısı SSS

Bu bölümde, ağaç veri yapısı ile ilgili bazı sık sorulan sorular ele alınmıştır.

Bir ağaç neden doğrusal olmayan bir veri yapısı olarak kabul edilir?

Bir ağaç veri yapısı, sıralı olarak depolanmadığından doğrusal değildir.  ağaç hiyerarşik bir yapıya sahiptir, çünkü bir ağacın elemanları birkaç seviyede düzenlenmiştir. Ağaç veri yapısındaki en yüksek düğüm, kök düğüm olarak bilinir. Her düğüm veri içerir ve veriler herhangi bir türde olabilir.

Ağaç veri yapısının gerçek hayatta kullanımı nedir?

Veritabanları, indeksleme için ağaç veri yapısını kullanabilir . Etki alanı adı sunucuları (DNS) da ağaç yapılarını kullanır. BST bilgisayar grafiklerinde kullanılır.

Mükemmel ağaç nedir?

Tam bir ikili ağaç, her dahili düğümün tam olarak iki alt düğüme sahip olduğu ve tüm yaprak düğümlerin aynı seviyede olduğu bir ikili ağaç türüdür.

Veri yapısında neden ağaç kullanılır?

Doğrusal veri yapıları olan dizi ve bağlantılı listeden farklı olarak , ağaç veri yapısı hiyerarşiktir (veya doğrusal değildir). Anahtarları bir ağaçta düzenlersek, belirli bir anahtarı bağlantılı bir listeden daha hızlı ve dizilerden daha yavaş arayabiliriz.

Bir veri yapısındaki bir ağacın özellikleri nelerdir?

Bir ağaç döngüsel olmayan bir grafiktir ve köşelerinin her bir çifti arasında benzersiz bir yol vardır. N sayıda köşesi olan bir ağaç (N- 1 ) kenar içerir. Derecesi sıfır olan bir tepe noktasına ağacın kökü denir.

Ağaçta hangi işlemler yapılabilir?

Ağaçtaki yaygın işlemler, öğe ekleme ve çıkarma, arama ve çaprazlama dahil sıralı veri yapısında da bulunan işlemlerdir.

Veri yapısındaki ağaç türleri nelerdir ve kullanım alanları nelerdir?

Bir eleman kümesindeki bir elemanı aramak için bir ikili arama ağacı kullanılabilir. Piramit ağaçları, piramit sıralama için kullanılır. Modern yönlendiriciler, yönlendirme bilgilerini depolamak için Tries adı verilen bir ağaç türü kullanır. B-Tree ve T-Tree, veri depolamak için çoğunlukla ortak veritabanlarında kullanılır.

Çözüm

Bir ağaç veri yapısı, ağaç düğümleri olarak tanımlanan, bilinen nesnelerin veya varlıkların bir koleksiyonundan oluşur. Bu düğümler hiyerarşik olarak görüntülenir ve birbirleriyle ilişkilidir. Ağaç özyinelemeli bir veri yapısıdır. Bir ağaç özyinelemelidir çünkü her ağaç birkaç alt ağaç içerir, çünkü ağaçtaki her düğüm başka bir ağacın köküdür, bu da onu bir alt ağaç yapar.

Bu yazıda, ağaçların gezinme, arama, karar verme ve makine öğrenimi gibi önemli kullanımlarından bazılarına değinildi ve ayrıca veri yapılarında ağaç türlerinin önemli konusunu tartıştık. Veri yapılarında en yaygın ağaç türleri arasında ikili ağaç, ikili arama ağacı, AVL ağacı ve kırmızı-siyah ağaç bulunur.