Binary Tree

Binary tree, her düğümün iki veya daha az child’ı olan bir tree’dir. Child’lara genellikle sol(left) ve sağ(right) denir.

class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left  = null;
    this.right = null;
  }
}

Bu, aşağıdaki gibi bir yapı oluşturmamızı sağlar:

Bu özel örnek, ağacın(tree) her seviyesi tamamen dolu olduğu için özeldir. “Boşluklar” yoktur. Bu tür ağaçlara(tree) “mükemmel” (perfect) diyoruz.

Binary tree(ikili ağaç) ların mükemmel olduklarında birkaç ilginç özelliği vardır:

Özellik 1: Her “düzey”deki toplam düğüm sayısı, ağaçtan aşağı indikçe ikiye katlanır.

Özellik 2: Son düzeydeki düğüm sayısı, diğer tüm düzeylerdeki düğümlerin sayısının toplamına eşittir (artı 1). Diğer bir deyişle, düğümlerimizin yaklaşık yarısı son seviyededir.

Düğüm sayısına n ve ağacın yüksekliğine h diyelim. h, “seviye sayısı” olarak da düşünülebilir.

Eğer h olsaydı, n’yi nasıl hesaplayabilirdik?

Her seviyedeki düğüm sayısını toplayalım! Her seviyede kaç düğüm var?

Seviyeleri sıfırlarsak, xx. seviyedeki düğüm sayısı tam olarak 2^x olur.

1. Level 00: 2⁰²⁰ nodes,
2. Level 11: 2¹²¹ nodes,
3. Level 22: 2²²² nodes,
4. Level 33: 2³²³ nodes,
5. etc

Yani toplam düğüm sayımız:

n=2^0+2^1+2^2+2^3+…+2^(h−1)

Neden sadece 2^(h-1)’e kadar?
Seviyelerimizi 0'dan saymaya başladığımıza dikkat edin. Yani toplamda h seviyemiz varsa, son seviye aslında “h-1”-inci seviyedir. Bu, son seviyedeki düğüm sayısının 2^(h-1)olduğu anlamına gelir.

Ama basitleştirebiliriz. Özellik 2 bize, son seviyedeki düğüm sayısının toplam düğüm sayısının yarısından (1 fazla) olduğunu söyler, bu yüzden sadece son seviyedeki düğüm sayısını alabilir, 2 ile çarpabilir ve 1'den çıkarabiliriz. toplam düğüm sayısını alın. Son seviyedeki düğüm sayısının 2^{h-1} olduğunu biliyoruz.
, Böylece:

Böylece h’den n’ye gidebiliriz. Peki ya diğer yön?

h’yi üssünden aşağı indirmeliyiz. Log’lar bunun için var!

İlk olarak, biraz hızlı inceleme. log_{10} (100)
basitçe “100 almak için 10'u hangi üsse yükseltmeniz gerekir?” anlamına gelir. Hangisi 2, çünkü 10² = 100

Log’u basitleştirebileceğimiz gerçeğinden yararlanarak değişkenleri üslerden aşağı çekmek için cebirde logları kullanabiliriz . 100'ü elde etmek için hangi üsse yükseltmeliyiz? log{10}10²
Bu kolay — 2.

Dolayısıyla bu durumda her iki tarafın log{2}’sini alabiliriz:

Mükemmel(perfect) bir binary tree(ikili ağaç) içinde yükseklik ve toplam düğümler arasındaki ilişki budur.