TechCodeview

Tüm elemanların sıralı bir şekilde düzenlendiği dizi, bağlantılı liste, yığın ve kuyruk gibi doğrusal veri yapılarını okuruz. Farklı veri türleri için farklı veri yapıları kullanılır.

Veri yapısını seçerken bazı faktörler dikkate alınır:

Ne tür verilerin saklanması gerekiyor?: Belirli bir veri yapısının, bazı veri türlerine en uygun olma ihtimali olabilir.Operasyon maliyeti:En sık yapılan operasyonlarda maliyetleri minimuma indirmek istiyorsak. Örneğin, arama işlemini gerçekleştirmemiz gereken basit bir listemiz var; daha sonra, aşağıdaki işlemleri gerçekleştirmek için öğelerin sıralı olarak saklandığı bir dizi oluşturabiliriz. Ikili arama . İkili arama, arama alanını ikiye böldüğü için basit liste için çok hızlı çalışır.Hafıza kullanımı:Bazen daha az bellek kullanan bir veri yapısı isteriz.

Bir ağaç aynı zamanda hiyerarşik verileri temsil eden veri yapılarından biridir. Çalışanları ve pozisyonlarını hiyerarşik biçimde göstermek istediğimizi varsayalım, bu durumda aşağıda gösterildiği gibi temsil edilebilir:

Yukarıdaki ağaç şunları göstermektedir: organizasyon hiyerarşisi bir şirketin. Yukarıdaki yapıda, John bu CEO şirketin ve John'un şu şekilde adlandırılan iki doğrudan raporu var: Steve Ve Rohan . Steve'in üç doğrudan raporu var: Lee, Bob, Ella Neresi Steve bir yöneticidir. Bob'un iki doğrudan raporu var: Acak Ve Emma . Emma adlı iki doğrudan raporu var Tom Ve Raj . Tom'un adında bir doğrudan raporu var Fatura . Bu özel mantıksal yapıya şu ad verilir: Ağaç . Yapısı gerçek ağaca benzediği için bu adı almıştır. Ağaç . Bu yapıda, kök tepede olup, dalları aşağıya doğru hareket etmektedir. Dolayısıyla Tree veri yapısının, verileri hiyerarşik bir şekilde saklamanın etkili bir yolu olduğunu söyleyebiliriz.

Ağaç veri yapısının bazı önemli noktalarını anlayalım.

• Ağaç veri yapısı, hiyerarşiyi temsil etmek veya simüle etmek için birbirine bağlanan, düğümler olarak bilinen nesnelerin veya varlıkların bir koleksiyonu olarak tanımlanır.
• Ağaç veri yapısı, sıralı bir şekilde saklanmadığı için doğrusal olmayan bir veri yapısıdır. Ağaçtaki öğeler birden çok düzeyde düzenlendiğinden hiyerarşik bir yapıdır.
• Ağaç veri yapısında en üstteki düğüm kök düğüm olarak bilinir. Her düğüm bazı veriler içerir ve veriler herhangi bir türde olabilir. Yukarıdaki ağaç yapısında, düğüm çalışanın adını içerir, dolayısıyla veri türü bir dize olacaktır.
• Her düğüm bazı verileri ve alt olarak adlandırılabilecek diğer düğümlerin bağlantısını veya referansını içerir.

Ağaç veri yapısında kullanılan bazı temel terimler.

Aşağıda gösterilen ağaç yapısını ele alalım:

jsp

Yukarıdaki yapıda her düğüm bir sayıyla etiketlenmiştir. Yukarıdaki şekilde gösterilen her ok bir ok olarak bilinir. bağlantı iki düğüm arasında.

Kök:Kök düğüm, ağaç hiyerarşisinde en üstteki düğümdür. Başka bir deyişle kök düğüm, herhangi bir ebeveyni olmayan düğümdür. Yukarıdaki yapıda 1 numaralı düğüm ağacın kök düğümü. Bir düğüm doğrudan başka bir düğüme bağlıysa buna ebeveyn-çocuk ilişkisi adı verilir.Çocuk düğümü:Düğüm herhangi bir düğümün soyundan geliyorsa, bu düğüm alt düğüm olarak bilinir.Ebeveyn:Düğümün herhangi bir alt düğüm içermesi durumunda, bu düğümün o alt düğümün ebeveyni olduğu söylenir.Kardeş:Aynı ebeveyne sahip düğümler kardeş olarak bilinir.Yaprak düğümü:-Ağacın herhangi bir alt düğümü olmayan düğümüne yaprak düğüm adı verilir. Yaprak düğümü ağacın en alttaki düğümüdür. Genel bir ağaçta herhangi bir sayıda yaprak düğüm bulunabilir. Yaprak düğümlere dış düğümler de denilebilir.Dahili düğümler:Bir düğümün en az bir alt düğümü vardır. dahili Ata düğümü: -Bir düğümün atası, kökten o düğüme giden yol üzerindeki herhangi bir öncül düğümdür. Kök düğümün herhangi bir atası yoktur. Yukarıdaki resimde gösterilen ağaçta 1, 2 ve 5 numaralı düğümler, 10 numaralı düğümün atalarıdır.Azalan:Belirli bir düğümün doğrudan ardılı, bir düğümün soyundan gelen kişi olarak bilinir. Yukarıdaki şekilde 10, 5. düğümün soyundan gelmektedir.

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

Özyinelemeli veri yapısı:Ağaç aynı zamanda bir ağaç olarak da bilinir. yinelemeli veri yapısı . Bir ağaç yinelemeli olarak tanımlanabilir çünkü bir ağaç veri yapısındaki ayırt edici düğüm bir ağaç olarak bilinir. kök düğüm . Ağacın kök düğümü, alt ağaçlarının tüm köklerine bir bağlantı içerir. Aşağıdaki şekilde sol alt ağaç sarı renkte, sağ alt ağaç ise kırmızı renkte gösterilmiştir. Sol alt ağaç ayrıca üç farklı renkte gösterilen alt ağaçlara bölünebilir. Özyineleme, bir şeyin kendine benzer şekilde azaltılması anlamına gelir. Dolayısıyla ağaç veri yapısının bu özyinelemeli özelliği çeşitli uygulamalarda uygulanmaktadır.
Kenar sayısı:Eğer n düğüm varsa n-1 kenar olacaktır. Yapıdaki her ok, bağlantıyı veya yolu temsil eder. Kök düğüm dışındaki her düğüm, kenar olarak bilinen en az bir gelen bağlantıya sahip olacaktır. Ebeveyn-çocuk ilişkisi için tek bir bağlantı olacaktır.Düğüm derinliği x:X düğümünün derinliği, kökten x düğümüne kadar olan yolun uzunluğu olarak tanımlanabilir. Bir kenar yola bir birim uzunluğa katkıda bulunur. Dolayısıyla x düğümünün derinliği, kök düğüm ile x düğümü arasındaki kenar sayısı olarak da tanımlanabilir. Kök düğümün derinliği 0'dır.x düğümünün yüksekliği:X düğümünün yüksekliği, x düğümünden yaprak düğüme kadar olan en uzun yol olarak tanımlanabilir.

Ağaç veri yapısının özelliklerine göre ağaçlar çeşitli kategorilere ayrılır.

Ağacın Uygulanması

Ağaç veri yapısı, işaretçiler yardımıyla düğümlerin dinamik olarak oluşturulmasıyla oluşturulabilir. Bellekteki ağaç aşağıda gösterildiği gibi temsil edilebilir:

Yukarıdaki şekil, ağaç veri yapısının bellekteki temsilini göstermektedir. Yukarıdaki yapıda düğüm üç alan içermektedir. İkinci alan verileri saklar; ilk alan sol çocuğun adresini, üçüncü alan ise sağ çocuğun adresini saklar.

Programlamada bir düğümün yapısı şu şekilde tanımlanabilir:

 struct node { int data; struct node *left; struct node *right; } 

Yukarıdaki yapı yalnızca ikili ağaçlar için tanımlanabilir çünkü ikili ağacın en fazla iki çocuğu olabilir ve genel ağaçların ikiden fazla çocuğu olabilir. Genel ağaçlar için düğümün yapısı, ikili ağaçla karşılaştırıldığında farklı olacaktır.

Ağaçların uygulamaları

Ağaçların uygulamaları şunlardır:

Doğal olarak hiyerarşik verileri depolamak:Ağaçlar, verileri hiyerarşik yapıda depolamak için kullanılır. Örneğin dosya sistemi. Disk sürücüsünde saklanan dosya sistemi, dosya ve klasör doğal olarak hiyerarşik veriler halindedir ve ağaçlar şeklinde depolanır.Verileri düzenleyin:Verimli ekleme, silme ve arama amacıyla verileri düzenlemek için kullanılır. Örneğin, bir ikili ağacın bir öğeyi aramak için logN süresi vardır.Trie:Sözlüğü saklamak için kullanılan özel bir ağaç türüdür. Dinamik yazım denetiminin hızlı ve etkili bir yoludur.Yığın:Aynı zamanda diziler kullanılarak uygulanan bir ağaç veri yapısıdır. Öncelik kuyruklarını uygulamak için kullanılır.B-Ağacı ve B+Ağacı:B-Tree ve B+Tree, veritabanlarında indekslemeyi uygulamak için kullanılan ağaç veri yapılarıdır.Yönlendirme tablosu:Ağaç veri yapısı aynı zamanda verileri yönlendiricilerdeki yönlendirme tablolarında depolamak için de kullanılır.

Ağaç veri yapısı türleri

Ağaç veri yapısının türleri şunlardır:

Genel ağaç:Genel ağaç, ağaç veri yapısı türlerinden biridir. Genel ağaçta bir düğüm 0 veya maksimum n sayıda düğüme sahip olabilir. Düğümün derecesine (bir düğümün içerebileceği düğüm sayısı) ilişkin herhangi bir kısıtlama yoktur. Genel bir ağaçtaki en üstteki düğüm, kök düğüm olarak bilinir. Ana düğümün çocukları olarak bilinir alt ağaçlar .

Orada olabilir N genel bir ağaçtaki alt ağaç sayısı. Genel ağaçta, alt ağaçtaki düğümler sıralanamadığından alt ağaçlar sırasızdır.
Boş olmayan her ağacın aşağı doğru bir kenarı vardır ve bu kenarlar, adı verilen düğümlere bağlanır. alt düğümler . Kök düğüm 0 düzeyiyle etiketlenir. Aynı ebeveyne sahip düğümler olarak bilinir. kardeşler . İkili ağaç :Burada ikili ismin kendisi iki sayıyı, yani 0 ve 1'i önerir. İkili ağaçta, ağaçtaki her düğümün en fazla iki alt düğümü olabilir. Burada maksimum, düğümün 0 düğüme mi, 1 düğüme mi yoksa 2 düğüme mi sahip olduğu anlamına gelir.

İkili ağaç hakkında daha fazla bilgi edinmek için aşağıdaki bağlantıya tıklayın:
https://www.javatpoint.com/binary-tree İkili Arama ağacı :İkili arama ağacı, bir düğümün birbirine bağlı olduğu doğrusal olmayan bir veri yapısıdır. N düğüm sayısı. Düğüm tabanlı bir veri yapısıdır. Bir düğüm, ikili arama ağacında üç alanla (veri bölümü, sol çocuk ve sağ çocuk) temsil edilebilir. Bir düğüm, ikili arama ağacındaki en fazla iki alt düğüme bağlanabilir, böylece düğüm iki işaretçi içerir (sol alt ve sağ alt işaretçi).
Sol alt ağaçtaki her düğüm, kök düğümün değerinden daha küçük bir değer içermeli ve sağ alt ağaçtaki her düğümün değeri, kök düğümün değerinden büyük olmalıdır.

Olarak bilinen kullanıcı tanımlı bir veri türü yardımıyla bir düğüm oluşturulabilir. yapı, Aşağıda gösterildiği gibi:

farklı sql'yi say

 struct node { int data; struct node *left; struct node *right; } 

Yukarıdaki üç alanlı düğüm yapısıdır: veri alanı, ikinci alan düğüm tipinin sol işaretçisidir ve üçüncü alan düğüm tipinin sağ işaretçisidir.

İkili arama ağacı hakkında daha fazla bilgi edinmek için aşağıda verilen bağlantıya tıklayın:

https://www.javatpoint.com/binary-search-tree

AVL ağacı

İkili ağacın türlerinden biridir ya da ikili arama ağacının bir çeşidi diyebiliriz. AVL ağacı şu özelliği karşılıyor: ikili ağaç aynı zamanda ikili arama ağacı . tarafından icat edilen, kendi kendini dengeleyen bir ikili arama ağacıdır. Adelson Velsky Lindas . Burada kendi kendini dengeleme, sol alt ağaç ve sağ alt ağacın yüksekliklerinin dengelenmesi anlamına gelir. Bu dengeleme şu şekilde ölçülür: dengeleme faktörü .

Eğer ağaç ikili arama ağacına ve bir dengeleme faktörüne uyuyorsa, bir ağacı AVL ağacı olarak değerlendirebiliriz. Dengeleme faktörü şu şekilde tanımlanabilir: sol alt ağacın yüksekliği ile sağ alt ağacın yüksekliği arasındaki fark . Dengeleme faktörünün değeri 0, -1 veya 1 olmalıdır; bu nedenle AVL ağacındaki her düğümün dengeleme faktörünün değeri 0, -1 veya 1 olmalıdır.

AVL ağacı hakkında daha fazla bilgi edinmek için aşağıda verilen bağlantıya tıklayın:

https://www.javatpoint.com/avl-tree

Kırmızı-Siyah Ağaç

Kırmızı-Siyah ağaç ikili arama ağacıdır. Kırmızı-Siyah ağacın ön şartı ikili arama ağacını bilmemizdir. İkili arama ağacında sol alt ağacın değeri o düğümün değerinden küçük, sağ alt ağacın değeri ise o düğümün değerinden büyük olmalıdır. Ortalama durumda ikili aramanın zaman karmaşıklığının log olduğunu biliyoruz.₂n, en iyi durum O(1) ve en kötü durum O(n)'dir.

Ağaç üzerinde herhangi bir işlem yapıldığında ağacımızın dengeli olmasını isteriz ki arama, ekleme, silme vb. tüm işlemler daha az zaman alsın ve tüm bu işlemler şu kadar zaman karmaşıklığına sahip olsun: kayıt₂N.

Kırmızı-siyah ağaç kendi kendini dengeleyen bir ikili arama ağacıdır. AVL ağacı aynı zamanda yükseklik dengeleyici bir ikili arama ağacıdır. neden Kırmızı-Siyah ağaca ihtiyacımız var? . AVL ağacında ağacı dengelemek için kaç döndürme gerektiğini bilmiyoruz ancak Kırmızı-siyah ağaçta ağacı dengelemek için maksimum 2 döndürme gerekir. Ağacın dengelenmesini sağlamak için bir düğümün kırmızı veya siyah rengini temsil eden ekstra bir bit içerir.

Yayvan ağaç

Yayvan ağaç veri yapısı aynı zamanda yeni erişilen öğenin bazı döndürme işlemleri yapılarak ağacın kök konumuna yerleştirildiği ikili arama ağacıdır. Burada, yayılıyor yakın zamanda erişilen düğüm anlamına gelir. Bu bir kendini dengeleme gibi açık bir denge koşulu olmayan ikili arama ağacı AVL ağaç.

Yayvan ağacın yüksekliğinin dengeli olmaması ihtimali olabilir, yani hem sol hem de sağ alt ağaçların yüksekliği farklı olabilir, ancak yayılım ağacındaki işlemler şu sırayı alır: sakinlik zaman nerede N düğüm sayısıdır.

c'de dizileri kullanan yapılar

Yayvan ağaç dengeli bir ağaçtır ancak yüksekliği dengeli bir ağaç olarak kabul edilemez çünkü her işlemden sonra dengeli bir ağaca yol açan döndürme işlemi gerçekleştirilir.

Hazine

Treap veri yapısı Tree ve Heap veri yapısından geldi. Yani hem Ağaç hem de Heap veri yapılarının özelliklerini içerir. İkili arama ağacında, sol alt ağaçtaki her düğüm, kök düğümün değerine eşit veya bundan küçük olmalıdır ve sağ alt ağaçtaki her düğüm, kök düğümün değerine eşit veya ondan büyük olmalıdır. Yığın veri yapısında, hem sağ hem de sol alt ağaçlar kökten daha büyük anahtarlar içerir; dolayısıyla kök düğümün en düşük değeri içerdiğini söyleyebiliriz.

Treap veri yapısında her düğüm her ikisine de sahiptir. anahtar Ve öncelik burada anahtar İkili arama ağacından türetilir ve öncelik yığın veri yapısından türetilir.

Hazine veri yapısı aşağıda verilen iki özelliği takip eder:

• Bir düğümün sağ çocuğu>=geçerli düğüm ve bir düğümün sol çocuğu<=current node (binary tree)< li>
• Herhangi bir alt ağacın çocukları düğümden (yığın) daha büyük olmalıdır

B ağacı

B-ağacı dengelidir m-yolu ağaç nerede M Ağacın sırasını tanımlar. Şu ana kadar düğümün yalnızca bir anahtar içerdiğini ancak b-ağacının birden fazla anahtara ve 2'den fazla çocuğa sahip olabileceğini okuduk. Her zaman sıralanan verileri korur. İkili ağaçta yaprak düğümlerin farklı seviyelerde olması mümkündür, ancak b-ağacında tüm yaprak düğümlerin aynı seviyede olması gerekir.

Sıra m ise düğüm aşağıdaki özelliklere sahiptir:

• Bir b-ağacındaki her düğümün maksimum değeri olabilir. M çocuklar
• Minimum çocuklar için, bir yaprak düğümün 0 çocuğu vardır, kök düğümün en az 2 çocuğu vardır ve iç düğümün minimum m/2 çocuk tavanı vardır. Örneğin m değeri 5'tir; bu, bir düğümün 5 çocuğa, iç düğümlerin ise en fazla 3 çocuğa sahip olabileceği anlamına gelir.
• Her düğümün maksimum (m-1) anahtarı vardır.

Kök düğüm en az 1 anahtar içermeli ve diğer tüm düğümler en az 1 anahtar içermelidir. m/2 eksi 1 tavanı anahtarlar.