Balanced Binary Tree

+10

root dizisi bir ikili ağaç tutar. Kök 0 indeksindedir; i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerindedir; boş bir yeri -1 belirtir ve sonda fazladan -1 girdileri bulunabilir.

Ağaç yükseklik dengeliyse, yani her düğümde sol ve sağ alt ağaçların yükseklikleri arasındaki fark en fazla 1 ise true, aksi hâlde false döndürün. Bir alt ağacın yüksekliği, aşağı doğru en uzun yol üzerindeki düğüm sayısıdır; boş bir alt ağacın yüksekliği 0’dır.

Fonksiyon

isBalanced(root: integer-array) → boolean

rootinteger-array: ikili ağacı seviye sırasına göre, boş yerler için -1 kullanarak
Döndürürboolean: Her düğümün iki alt ağacının yükseklikleri en fazla 1 farklıysa true, aksi hâlde false

Kısıtlar

1 ≤ root.length ≤ 32767
Her root[i], -1 ya da 0 ≤ root[i] ≤ 10⁵ koşulunu sağlayan bir değerdir.
root[0] hiçbir zaman -1 değildir, bu nedenle ağacın en az bir düğümü vardır.
Dizi, son düğümden sonra fazladan -1 girdileriyle bitebilir.
Boş bir noktanın iki çocuğu da boştur ve derinlik en fazla 14'tür.
Düğüm değerleri birbirinden farklıdır.

Örnekler

Girdi: root = [5, 2, 9, -1, -1, 7, 11]
Çıktı: true
Açıklama: Kökün sol alt ağacı, tek düğüm olan 2'dir ve yüksekliği 1'dir. Sağ alt ağacındaki 9, 7, 11 düğümlerinin yüksekliği 2'dir. Aralarındaki fark 1'dir ve diğer tüm düğümlerin iki alt ağacının yüksekliği eşittir.

Girdi: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Çıktı: false
Açıklama: Kökün her iki tarafının da yüksekliği 3, ancak 3 düğümü başarısız olur: 1, 0 sol alt ağacının yüksekliği 2’dir ve sağ alt ağacı boştur.

Girdi: root = [4, 2, -1, 1]
Çıktı: false
Açıklama: Kökün solunda 2, 1 zinciri ve 2 yüksekliği vardır; sağında ise hiçbir şey yoktur ve yüksekliği 0'dır. 2 farkı çok fazladır.

Ek soru

Ağacı açık bir yığın kullanarak özyineleme olmadan kontrol edebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Kural her düğüm için geçerlidir; bu nedenle kökü çift görünen bir ağaç, ikinci örnekte 3 düğümünde olduğu gibi daha alt seviyelerde yine de başarısız olabilir. Son-dolaşım geçişi, her alt ağacın yüksekliğini bir kez hesaplar ve bir başarısızlık ortaya çıkar çıkmaz bunu yukarı iletir; zaman karmaşıklığı O(n)'dir.

Düğümdeki yükseklikleri yeniden hesapla

Sezgi

Tanımı koda dönüştür. Boş bir noktada height(i) değeri 0, diğer yerlerde ise uzun olan çocuktan 1 fazladır. Her gerçek düğümde iki çocuğun yüksekliğini karşılaştır; aralarındaki farkın 1'den fazla olduğu ilk düğümde yanıt false olur.

Her kontrol, düğümünün altındaki tüm alt ağacı dolaşır; dolayısıyla bir düğüm, üstündeki her düğüm için bir kez dolaşılır: O(n·h). En fazla 14 seviye olduğunda, 16,383 düğümlü tam bir ağaç yaklaşık 2 × 10^5 adıma mal olur. n düğümlü bir zincirin maliyeti O(n²) olur.

Algoritma

Sonun ötesindeki bir indeks veya -1 için height(i) değerini 0, gerçek bir düğüm içinse 1 + max(height(2*i+1), height(2*i+2)) olarak tanımla.
Gerçek bir düğüm içeren her i indeksini ziyaret et.
height(2*i+1) ile height(2*i+2) arasındaki fark 1'den büyükse false döndür.
Döngü başarısızlık olmadan sona ererse true döndür.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Yüksekliği veya başarısızlığı bildiren tek bir son sıralı geçiş

Sezgi

Bir düğümdeki kontrol, iki alt ağacının yüksekliklerine ihtiyaç duyar; düğümün kendi yüksekliğini bildirmek için de bunlar gerekir. Öyleyse ikisini de tek bir post-order ziyaretiyle alın: her çağrı, iki çocuk da döndükten sonra alt ağacının yüksekliğini döndürür.

Aşağıdaki bir başarısızlık da yukarı taşınmalıdır. Gerçek bir yükseklik hiçbir zaman negatif olmadığından, bunun için -1 kullanın: bir çocuk -1 döndürdüyse veya çocukların yükseklikleri arasındaki fark 1'den büyükse çağrı -1 döndürür. İkinci örnekte 3, 2 ve 0 yüksekliklerini görür ve -1 döndürür; kök de sağ tarafını ziyaret etmeden bu değeri yukarı iletir.

Hiçbir düğüme iki kez girilmediğinden, zaman karmaşıklığı O(n), yığındaki çağrı sayısı ise O(h) olur.

Algoritma

check(i) yazın. Dizinin sonunu aşan bir indeks veya -1 için 0 döndürün.
left = check(2*i+1) değerini hesaplayın. Bu değer -1 ise -1 döndürün.
right = check(2*i+2) değerini hesaplayın. Bu değer -1 ise veya left ile right arasındaki fark 1'den büyükse -1 döndürün.
Aksi takdirde 1 + max(left, right) döndürün.
check(0) değerinin -1 olmadığını döndürün.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Tuzaklar ve uç durumlar

Yalnızca kökü kontrol etmek. İkinci örnekte kökün her iki tarafının yüksekliği 3, ancak 3 düğümünün farkı 2.
En sığ ve en derin yaprakları karşılaştırmak. Yüksekliği 6 olan en küçük dengeli ağacın yaprakları 4 ve 6 derinliklerinde bulunur ve bu ağaçtaki her düğüm koşulu sağlar.
Yukarı çıkarken bir hatayı kaybetmek. Bir çocuk -1 döndürür ve ebeveyn 1 + max(-1, 2) hesaplamasını yaparsa hata yeniden yüksekliğe dönüşür.
Dizi uzunluğunu yükseklik olarak kullanmak. Sondaki -1 girdileri diziyi ağacın derinliğinden daha uzun hâle getirir.
Lua ve R'de diziler 1'den başlar. 2*i+1 için düğüm indekslerini 0 tabanlı tutun ve root[i + 1] okuyun.

Sıkça sorulan sorular3

Dengeli İkili Ağacın zaman karmaşıklığı nedir?

Tek bir son-sıra geçişi her düğüme bir kez uğrar: yüksekliği h olan bir ağaç için O(n) zaman ve O(h) yığın alanı kullanır. Her düğümde yüksekliği yeniden hesaplamak O(n·h) maliyetlidir; bu, bir zincirde O(n²) olur.

İkili ağacın yükseklik bakımından dengeli olması ne anlama gelir?

Her düğümde, sol ve sağ alt ağaçların yükseklikleri en fazla 1 fark eder. AVL ağaçları her ekleme ve silme işleminden sonra bu özelliği yeniden sağlar; böylece yükseklikleri O(log n) olur.

Tam bir ikili ağaç her zaman dengeli midir?

Evet. Tam bir ağacın son seviye hariç tüm seviyeleri doludur; son seviye soldan başlayarak dolar. Bu nedenle herhangi bir düğümde iki alt ağacın yükseklikleri arasındaki fark en fazla 1 olur. Tersi doğru değildir: dengeli bir ağacın son seviyesinin sol tarafında boşluklar olabilir.

def isBalanced(root):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

root = [5, 2, 9, -1, -1, 7, 11]

Beklenen Çıktı

true