Range Sum of BST

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

Budanmış 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 O(h + k) zaman, tüm değerler aralıkta olduğunda ise O(n) zaman alır. Yığın veya özyineleme O(h) alan kullanır.

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

Evet. Sıralı dolaşım değerleri artan sırada listeler; bu nedenle değerler low değerine ulaştığında onları eklersin ve high değerinden büyük olan ilk değerde durursun. Erken durmak ağacın sağ tarafındaki işi azaltır; budama ise her iki taraftaki işi azaltır.

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

İkisi de işe yarar. Burada derinlik en fazla 14 olduğundan özyineleme sığ kalır. Açık bir yığın, binlerce seviyeli uzun bir ağaçta özyineleme sınırına takılmayı önler.

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

+10

İkili arama ağacı, dizi tree içinde seviye sırasıyla saklanır: kök 0 indeksindedir, i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerindedir ve boş bir yeri -1 belirtir. İ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 düğümün değerinden büyüktür.

low ≤ v ≤ high koşulunu sağlayan tüm düğüm değerlerinin v toplamını döndür; böyle bir değer yoksa 0 döndür.

Fonksiyon

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

treeinteger-array: ikili arama ağacını seviye sırasına göre, boş bir 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: düşük ve yüksek değerleri de dâhil olmak üzere, aralarındaki düğüm değerlerinin toplamı

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, dolayısıyla ağacın en az bir düğümü vardır.
Dizi, son düğümden sonra fazladan -1 girdileri içerebilir.
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 tamsayı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 değildir; 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 indisindeki 4, 2 düğümünün sağ çocuğudur; dolayısıyla yanıt 4 olur.

Ek soru

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

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Her düğümü ziyaret etmek ve aralıktaki değerleri toplamak doğrudur. Arama ağacının sıralaması daha az işlem yapmanı sağlar: Bir düğümün değeri, küçük ve büyük değerlerin hangi tarafta olduğunu gösterir; böylece aralığa ulaşamayacak bir alt ağaç hiç açılmaz.

Her düğümü ziyaret et

Sezgi

Bir çocuk, yalnızca dizideki indeksi mevcutsa ve oradaki değer -1 değilse gerçektir. İlk örnekte, 4 indeksindeki 12'nin 9 ve 10 indekslerinde 10 ve 15 değerleri vardır; 2 indeksindeki 31'in ise 5 indeksinde boş bir sol yeri vardır.

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 yığın dolaşımı doğru toplamı verir. Arama ağacının sırasını göz ardı ettiğinden, aralıkta yalnızca birkaç değer olsa bile n düğümün tümüne dokunur.

Algoritma

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

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

v değerini tutan bir düğümün sol alt ağacında yalnızca v değerinden küçük değerler bulunur. v ≤ low ise bunların hiçbiri aralıkta değildir; bu nedenle bu alt ağacı atla. v ≥ high ise sağ alt ağaçta yalnızca high değerinden büyük değerler bulunur; bu nedenle onu atla. İlk örnekte 31, high değerine eşittir; bu yüzden sağ çocuğu 40 hiçbir zaman yığına eklenmez. 8, low değerinden küçüktür; bu nedenle sol çocuğu 3 atlanır, ancak 8 ile 20 arasındaki değerler aralıkta olabileceği için sağ çocuğu 12 ziyaret edilir.

Aralıktaki k değeri ve kökten başlayan en fazla iki yol üzerindeki düğümleri ziyaret edersin: derinlik h için O(h + k) zaman. Aralık ağacın tamamını kapsadığında bile bu süre O(n) olur.

Algoritma

Kök indeksini 0 yığına ekleyin ve total = 0 olarak ayarlayın.
Yığından i indeksini çıkarın ve v = tree[i] değerini okuyun. low ≤ v ≤ high ise v değerini total değerine ekleyin.
v > low ise, gerçek olduğu durumda sol çocuk 2*i+1 değerini yığına ekleyin.
v < high ise, gerçek olduğu durumda sağ çocuk 2*i+2 değerini yığına ekleyin.
Yığın boş olduğunda total değerini döndürün.

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

Katı karşılaştırmalar kullanmak. Her iki uç da dahildir; bu nedenle low = high = 4 olan üçüncü örnekte 4 sayılmalıdır.
Bir adım çok erken budamak. v = low olduğunda sol alt ağaç elenebilir; ancak v = low + 1 olduğunda bu alt ağaçta low değerinin kendisi bulunabilir.
Aralığın dışındaki bir düğümün iki tarafını da elemek. İlk örnekteki 8, low değerinden küçüktür; ancak sağ alt ağacında 10, 12 ve 15 bulunur.
Dizinin sonunu aşan bir çocuğu okumak. Okumadan önce 2*i+1 < tree.length koşulunu kontrol edin ve -1 değerini çocuk olmadığı şeklinde değerlendirin.
Lua ve R'de diziler 1'den başlar: 2*i+1 aritmetiği için düğüm indekslerini 0 tabanlı tutun ve tree[i + 1] öğesini okuyun.

Sıkça sorulan sorular3

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

Budanmış 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 O(h + k) zaman, tüm değerler aralıkta olduğunda ise O(n) zaman alır. Yığın veya özyineleme O(h) alan kullanır.

BST'nin Aralık Toplamı, sıralı dolaşım kullanılarak çözülebilir mi?

Evet. Sıralı dolaşım değerleri artan sırada listeler; bu nedenle değerler low değerine ulaştığında onları eklersin ve high değerinden büyük olan ilk değerde durursun. Erken durmak ağacın sağ tarafındaki işi azaltır; budama ise her iki taraftaki işi azaltır.

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

İkisi de işe yarar. Burada derinlik en fazla 14 olduğundan özyineleme sığ kalır. Açık bir yığın, binlerce seviyeli uzun bir ağaçta özyineleme sınırına takılmayı önler.

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

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı