Range Sum of BST

Q: BST Aralık Toplamı'nın zaman karmaşıklığı nedir?

Arama ağacı sırasına göre budama yapan bir dolaşım, aralıktaki k düğümü ve kökten başlayan en fazla iki yol üzerindeki düğümleri ziyaret eder; derinliği h olan bir ağaç için zaman karmaşıklığı O(h + k) olur. En kötü durumda, tüm değerler aralıktaysa, bu O(n) olur. Ek alan, yığın veya özyineleme için O(h) olur.

Q: BST'nin Aralık Toplamı'nda alt ağaçları neden atlayabilirsiniz?

Bir ikili arama ağacında, bir düğümün solundaki her değer ondan küçüktür ve sağındaki her değer ondan büyüktür. Düğümün değeri en fazla low ise solundaki hiçbir değer aralığa giremez; en az high ise sağındaki hiçbir değer giremez. Bu tarafları atlamak, aralık içindeki hiçbir değerin gözden kaçmasına neden olmaz.

Q: BST'nin Aralık Toplamı, sıralı dolaşma ile çözülebilir mi?

Evet. İkili arama ağacının sıralı dolaşımı değerleri artan sırayla listeler; bu nedenle değerler low değerine ulaştığında toplamaya başlayabilir ve biri high değerini geçer geçmez durabilirsin. Aynı sonucu verir ve erken durmak ağacın sağ tarafında iş tasarrufu sağlarken, budanmış arama sol tarafta da iş tasarrufu sağlar.

Q: BST Aralık Toplamı için özyineleme mi yoksa yığın mı kullanmalısınız?

İkisi de işe yarar. Özyinelemeli çözüm daha kısadır ve burada derinlik en fazla 14 olduğundan çağrı yığını küçük kalır. Açık bir yığın, özyineleme sınırını tamamen aşar; bu, binlerce seviyeli uzun bir ağaçta önemlidir ve bu sayfadaki çözümlerde kullanılan yöntem budur.

Kolayİkili arama ağacı Ağaç dolaşma

+10

Dizi seviyesinde sıralı olarak tree dizisinde saklanan bir ikili arama ağacı ve iki sayı low ile high veriliyor. Kök 0 indeksinde bulunur, i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerinde bulunur, boş bir konumu -1 belirtir ve dizinin sonunda fazladan -1 girdileri olabilir. İkili arama ağacında, bir düğümün sol alt ağacındaki her değer düğümün değerinden küçüktür, sağ alt ağacındaki her değer ise daha büyüktür.

rangeSumBST adlı bir fonksiyon yazın. Bu fonksiyon, low ≤ v ≤ high koşulunu sağlayan tüm düğüm değerlerinin v toplamını, bu aralıkta hiçbir değer yoksa 0 döndürmelidir.

Fonksiyon

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: ikili arama ağacını seviye sırasına göre, boş konum için -1 kullanarak
lowinteger: sayılacak en küçük değer
highinteger: sayılacak en büyük değer
Döndürürinteger: low ve high arasındaki düğüm değerlerinin toplamı, her ikisi de dahil

Kısıtlar

1 ≤ tree.length ≤ 32767
Her tree[i], -1 ya da 0 ≤ tree[i] ≤ 10⁵ koşulunu sağlayan bir değerdir.
tree[0] hiçbir zaman -1 değildir, bu nedenle ağaçta en az bir düğüm vardır.
Dizi, son düğümden sonra fazladan -1 girdileriyle bitebilir.
Boş bir noktanın her iki çocuğu da boştur ve derinlik en fazla 14 olur.
Ağaç geçerli bir ikili arama ağacıdır, bu nedenle tüm değerleri birbirinden farklıdır.
0 ≤ low ≤ high ≤ 10⁵
Yanıt, 32 bitlik işaretli bir tam sayıya sığar.

Örnekler

Girdi: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Çıktı: 88
Açıklama: 9 ile 31 arasındaki değerler 10, 12, 15, 20 ve 31'dir; bunların toplamı 88 eder. 3, 8 ve 40 aralığın dışındadır.

Girdi: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Çıktı: 0
Açıklama: Ağaç 25, 50 ve 75 değerlerini içerir ve bunların hiçbiri 60 ile 70 arasında yer almaz; bu nedenle toplam 0 olur. Dört -1 girdisi, 25 ve 75 düğümlerinin boş çocuk konumlarıdır.

Girdi: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Çıktı: 4
Açıklama: low ve high değerleri 4 olduğunda, yalnızca değeri 4 olan bir düğüm sayılır. 4 indeksi 4 olan düğüm, 2 değerinin sağ çocuğudur; bu nedenle cevap 4 olur.

Gönderirken +14 gizli test

Ek soru

Aynı ağaçta binlerce farklı (low, high) sorgusunu yanıtlaman gerekseydi, her birini O(log n) sürede nasıl yanıtlayabilirdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Aralıktaki her değeri toplamak, basit bir dolaşmadır: her düğümü ziyaret et ve koşula uyanları al. Arama ağacının sıralaması daha iyisini yapmanı sağlar. Bir düğümün değeri, daha küçük ve daha büyük değerlerin hangi tarafta bulunduğunu gösterir; böylece içlerindeki tek bir düğüme bile bakmadan tüm alt ağaçları atlayabilirsin.

Her düğümü ziyaret et

Sezgi

Önce, dizide nasıl ilerleyeceğimize bakalım. i indeksindeki düğümün sol çocuğu 2*i+1, sağ çocuğu ise 2*i+2 indeksindedir. Bir çocuk, yalnızca indeksi dizinin sınırları içindeyse ve o konumdaki değer -1 değilse gerçektir. [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] dizisinde, kök 20'nin 1 ve 2 indekslerinde 8 ve 31 çocukları vardır; 4 indeksindeki 12'nin 9 ve 10 indekslerinde 10 ve 15 çocukları vardır; 31'in ise 5 indeksinde boş bir sol çocuk konumu bulunur.

Şimdi gelelim fikre. Aralıktaki her değer bir düğümde bulunduğundan, her düğüme ulaşan ve low ≤ v ≤ high koşulunu sağlayan değerleri toplayan bir dolaşım doğru toplamı verir. Düğüm indekslerinden oluşan bir yığın kullanın. Kökten başlayın, bir indeks çıkarın, değeri aralıktaysa toplama ekleyin ve gerçek olan her çocuğu yığına ekleyin.

Bu yöntem, arama ağacı özelliğini tamamen göz ardı eder; herhangi bir ikili ağaçta çalışır. n düğümün tümüne dokunur; zaman karmaşıklığı O(n)'dir ve yığın, bir yol boyunca bekleyen çocukları tutar; h derinliği için alan karmaşıklığı O(h)'dir. Aralık, binlerce düğümlü bir ağaçta yalnızca birkaç değeri kapsadığında, yapılan işin büyük bölümü boşa gider.

Algoritma

Kök dizin 0 değerini yığına ekle ve total = 0 olarak ayarla.
i dizinini yığından çıkar. low ≤ tree[i] ≤ high ise tree[i] değerini total değerine ekle.
Dizi sınırları içindeyse ve -1 değilse 2*i+1 ve 2*i+2 değerlerini yığına ekle.
Yığın boş olduğunda total değerini döndür.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Arama ağacı sırasına göre budama

Sezgi

Aynı yığın dolaşımını kullan, ancak sıralamadan yararlan. Bir düğümün v değerini tuttuğunu varsayalım. Sol alt ağacındaki tüm değerler v değerinden küçüktür. v ≤ low ise bu değerlerin hepsi low değerinden küçüktür; dolayısıyla sol alt ağaç hiçbir katkı sağlayamaz: onu atla. Benzer şekilde, v ≥ high ise sağ alt ağaç yalnızca high değerinden büyük değerler içerir: onu atla. Bu yüzden sol çocuğu yalnızca v > low olduğunda, sağ çocuğuysa yalnızca v < high olduğunda yığına eklersin.

[9, 31] aralığının kullanıldığı ilk örnekte 31, high değerine eşittir; bu nedenle sağ çocuğu 40 yığına hiçbir zaman eklenmez. 8, low değerinden küçüktür; bu nedenle sol çocuğu 3 atlanırken, 8 ile 20 arasındaki değerler aralıkta olabileceği için sağ çocuğu 12 ziyaret edilmeye devam eder.

Ziyaret ettiğin düğümler, aralıktaki k değer ile bu aralığın kenarları boyunca uzanan en fazla iki kökten yaprağa yolun düğümleridir; dolayısıyla zaman karmaşıklığı O(h + k) olur. Aralık ağacın tamamını kapsadığında bu yine O(n) olur; ancak büyük bir ağaçta dar bir aralık yalnızca birkaç düzine düğüme dokunur. Yığın O(h) alan gerektirir.

Algoritma

Kök dizini 0'ı yığına ekle ve total = 0 olarak ayarla.
i dizinini yığından çıkar ve v = tree[i] değerini oku. low ≤ v ≤ high ise v değerini total'a ekle.
v > low ise gerçek olduğunda sol çocuğu 2*i+1 yığına ekle.
v < high ise gerçek olduğunda sağ çocuğu 2*i+2 yığına ekle.
Yığın boşaldığında total değerini döndür.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

Tuzaklar ve uç durumlar

Çoğu yanlış yanıt, aralığın veya dizinin sınırlarından kaynaklanır.

Katı karşılaştırmalar kullanmak. Her iki uç da dahildir; bu nedenle low veya high değerine eşit bir düğüm hesaba katılır.
Bir adım çok erken budama yapmak. v, low değerine eşitse sol alt ağaç atlanabilir; ancak v, low + 1 ise atlanamaz: kendisi low değerini içerebilir.
Aralığın dışındaki bir düğümde durmak. low değerinden küçük bir düğümün sağ alt ağacı hâlâ aralıktaki değerlerle dolu olabilir; bu yüzden yalnızca sıralama kurallarının dışladığı tarafı atlayın.
Dizinin sonunu aşan bir çocuk indeksini okumak. Değeri okumadan önce 2*i+1 < tree.length koşulunu kontrol edin ve -1 değerini çocuk yok olarak değerlendirin.
Dizilerin 1'den başladığı Lua ve R'deki ofseti karıştırmak. 2*i+1 aritmetiği için düğüm indekslerini 0 tabanlı tutun ve tree[i + 1] öğesini okuyun.

Sıkça sorulan sorular4

BST Aralık Toplamı'nın zaman karmaşıklığı nedir?

Arama ağacı sırasına göre budama yapan bir dolaşım, aralıktaki k düğümü ve kökten başlayan en fazla iki yol üzerindeki düğümleri ziyaret eder; derinliği h olan bir ağaç için zaman karmaşıklığı O(h + k) olur. En kötü durumda, tüm değerler aralıktaysa, bu O(n) olur. Ek alan, yığın veya özyineleme için O(h) olur.

BST'nin Aralık Toplamı'nda alt ağaçları neden atlayabilirsiniz?

Bir ikili arama ağacında, bir düğümün solundaki her değer ondan küçüktür ve sağındaki her değer ondan büyüktür. Düğümün değeri en fazla low ise solundaki hiçbir değer aralığa giremez; en az high ise sağındaki hiçbir değer giremez. Bu tarafları atlamak, aralık içindeki hiçbir değerin gözden kaçmasına neden olmaz.

BST'nin Aralık Toplamı, sıralı dolaşma ile çözülebilir mi?

Evet. İkili arama ağacının sıralı dolaşımı değerleri artan sırayla listeler; bu nedenle değerler low değerine ulaştığında toplamaya başlayabilir ve biri high değerini geçer geçmez durabilirsin. Aynı sonucu verir ve erken durmak ağacın sağ tarafında iş tasarrufu sağlarken, budanmış arama sol tarafta da iş tasarrufu sağlar.

BST Aralık Toplamı için özyineleme mi yoksa yığın mı kullanmalısınız?

İkisi de işe yarar. Özyinelemeli çözüm daha kısadır ve burada derinlik en fazla 14 olduğundan çağrı yığını küçük kalır. Açık bir yığın, özyineleme sınırını tamamen aşar; bu, binlerce seviyeli uzun bir ağaçta önemlidir ve bu sayfadaki çözümlerde kullanılan yöntem budur.

Python

def rangeSumBST(tree, low, high):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

Beklenen