B-ağacı ve İkili ağaç Arasındaki Fark
İçerik
- Karşılaştırma Tablosu
- B-tree'un tanımı
- M düzen B ağacının özellikleri
- İkili ağaç tanımı
- Geçiş Teknikleri
- Sonuç
B-ağacı ve İkili ağaç, doğrusal olmayan veri yapısının tipleridir. Her ne kadar terimler benzer gözükse de her yönüyle farklı. RAM'in erişim hızı diskten çok daha yüksek olduğundan, kayıtlar veya veriler disk yerine RAM'de depolandığında ikili bir ağaç kullanılır. Öte yandan, B-ağacı, veriler diskte depolanırken, ağaç yüksekliğini azaltarak ve düğümdeki dalları artırarak erişim süresini azaltır.
B ağacı ve ikili ağaç arasındaki diğer bir fark, B ağacının tüm alt düğümlerinin aynı seviyede olması gerekirken, ikili ağacın böyle bir kısıtlaması yoktur. Bir ikili ağacın maksimum 2 alt ağacı veya düğümü olabilir, oysa B ağacında M, B ağacının sırası olduğu M alt sınıfı veya düğümü olmayabilir.
- Karşılaştırma Tablosu
- Tanım
- Anahtar Farklılıklar
- Sonuç
Karşılaştırma Tablosu
| Karşılaştırma için temel | B-tree | İkili ağaç |
|---|---|---|
| Temel kısıtlama | Bir düğümde maksimum M sayısı alt düğümlere sahip olabilir (burada M ağacın sırasıdır). | Bir düğümde en fazla 2 alt ağaç sayısı olabilir. |
| Kullanılmış | Veriler diskte depolandığında kullanılır. | Kayıtlar ve veriler RAM'de saklandığında kullanılır. |
| Ağacın yüksekliği | günlükM N (m, M yollu ağacın sırasıdır) | günlük2 N- |
| Uygulama | Birçok DBMS'de kod indeksleme veri yapısı. | Kod optimizasyonu, Huffman kodlaması vb. |
B-tree'un tanımı
B-ağacı dengeli M-yollu bir ağaçtır ve aynı zamanda dengeli ağaç olarak da bilinir. Düğümlerin düzensiz hareketler temelinde organize edildiği ikili arama ağacına benzer. B-ağacının uzay karmaşıklığı O (n) 'dir. Ekleme ve silme süresi karmaşıklığı O (log n) 'dir.
B ağacı için geçerli olması gereken belirli koşullar vardır:
- Ağacın yüksekliği mümkün olduğu kadar asgari düzeyde durmalıdır.
- Ağacın yapraklarının üstünde boş alt ağaç bulunmamalıdır.
- Ağacın yaprakları aynı seviyede gelmelidir.
- Bütün düğümler izin düğümleri dışında en az sayıda çocuğa sahip olmalıdır.
M düzen B ağacının özellikleri
- Her bir düğüm maksimum M çocuk sayısına ve minimum M / 2 çocuk sayısına veya herhangi bir sayıya 2 ila maksimum olabilir.
- Her bir düğümde, maksimum M-1 tuşları olan çocuklardan bir anahtar daha az bulunur.
- Anahtarların düzenlenmesi düğümler içinde belirli bir düzendedir. Anahtarın solunda bulunan alt ağaçta bulunan tüm anahtarlara, anahtarın öncülleridir ve anahtarın sağında bulunanlara halefler adı verilir.
- Tam bir düğümün yerleştirilmesi sırasında, ağaç iki parçaya bölünür ve ortanca değere sahip olan anahtar üst düğüme yerleştirilir.
- Birleştirme işlemi, düğümler silindiğinde gerçekleşir.
İkili ağaç tanımı
Bir İkili ağaç, alt düğümleri için en fazla iki işaretçiye sahip olan bir ağaç yapısıdır. Bir düğümün sahip olabileceği en yüksek derecenin 2 olduğu ve sıfır veya bir derecelik düğümün de olabileceği anlamına gelir.
İkili bir ağacın kesinlikle ikili ağaç, tam ikili ağaç, uzatılmış ikili ağaç, vs. gibi bazı değişkenleri vardır.
- Kesinlikle ikili ağaç, her bir terminal olmayan düğümün sol alt ağaç ve sağ alt ağaç içermesi gereken bir ağaçtır.
- Bir ağaç 2 olması koşulunu sağladığında Tam İkili ağaç olarak adlandırılır. ben i seviyesinin olduğu her seviyedeki düğümler.
- Dişli ikili, 0 düğüm sayısı veya 2 düğüm sayısından oluşan ikili bir ağaçtır.
Geçiş Teknikleri
Ağaç geçişi, her bir düğümün tam olarak bir kez sistematik bir şekilde ziyaret ettiği ağaç veri yapısı üzerinde yapılan en yaygın işlemlerden biridir.
- Sıralama - Bu ağaç geçişinde sol alt ağacı tekrar tekrar ziyaret edilir, ardından kök düğüm ziyaret edilir ve son sağ alt ağaçta ziyaret edilir.
- Preorer- Bu ağaç geçişinde kök düğüm ilk önce sol alt ağaçta ve son sağ alt ağaçta ziyaret edilir.
- Postorder - Bu teknik sol alt ağaçtan sonra sağ alt ağaçtan ve son kök düğümden ziyaret eder.
- B ağacında, terminal olmayan bir düğümün sahip olabileceği en fazla alt düğüm sayısı, M'nin B ağacının sırası olduğu M'dir. Öte yandan, bir İkili ağacın en fazla iki alt ağacı veya alt düğümü olabilir.
- Veriler diskte depolanırken B-ağacı kullanılırken, veriler RAM gibi hızlı bellekte saklanırken ikili ağaç kullanılır.
- B-ağacı için bir başka uygulama alanı, DBMS'deki kod indeksleme veri yapısının aksine, İkili ağaç kod optimizasyonu, huffman kodlaması vb.
- Bir B-ağacının maksimum yüksekliğiMN (M ağacın sırasıdır). Karşı, ikili ağaç maksimum yüksekliği log2N (N, düğüm sayısıdır ve taban 2'dir, çünkü ikilidir).
Sonuç
B-ağacı ikili ve ikili arama ağacı üzerinde kullanılır ve bunun ana nedeni CPU'nun düşük bant genişliği kanalından CPU'ya bağlanması sırasında CPU'nun yüksek bant genişliği kanallarıyla önbelleğe bağlanmasıdır. Kayıtlar RAM'de saklandığında (küçük ve hızlı) bir ikili ağaç, kayıtlar diskte saklandığında (büyük ve yavaş) B-ağacı kullanılır. Bu nedenle, İkili ağaç yerine B-ağacı kullanımı, yüksek dallanma faktörü ve düşük ağaç yüksekliği nedeniyle erişim süresini önemli ölçüde azaltır.
