Kth Smallest Element in a BST

Q: Bir BST'de k'inci en küçük öğeyi bulmanın zaman karmaşıklığı nedir?

Yinelemeli sıralı dolaşım, derinliği h olan bir ağaç için O(h + k) zaman ve O(h) ek alan gerektirir. En kötü durumda, k = n olduğunda veya ağaç bir yol şeklinde olduğunda, bu O(n) olur.

Q: Özyinelemeli inorder dolaşımını k'ıncı değerde nasıl durdurursunuz?

Özyineleme dışında, k değerinden başlayan bir sayaç tut. Bir düğümün sol alt ağacı döndükten sonra 1 çıkar ve sayaç 0 değerine ulaştığında düğümün değerini kaydet. Her çağrıdan sonra yanıt kaydedilmişse hemen dön. Böylece özyineleme, yığın sürümüyle aynı olur: O(h + k) zaman, O(h) alan.

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

+10

Yığın sıralamasında root dizisi olarak bir ikili arama ağacı alırsın: kök, 0 indeksindedir; i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerindedir ve -1 boş bir yeri belirtir. Dizi, fazladan -1 girdileriyle bitebilir. Her düğümde, sol alt ağaç yalnızca daha küçük değerleri, sağ alt ağaç ise yalnızca daha büyük değerleri içerir.

Ağaçtaki, 1'den başlayarak sayılan k'inci en küçük değeri döndür.

Fonksiyon

kthSmallest(root: integer-array, k: integer) → integer

rootinteger-array: ikili arama ağacını seviye sırasına göre, boş noktalar için -1 kullanarak
kinteger: artan sırada bulmak için konum, 1'den başlayarak
Döndürürinteger: ağaçtaki k'ıncı en küçük değer

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 olmaz, bu nedenle ağaçta en az bir düğüm vardır.
Dizi, son düğümden sonra fazladan -1 öğeleriyle bitebilir.
Boş bir noktanın her iki çocuğu da boştur ve derinlik en fazla 14 olur.
Sıralama kuralı her düğümde geçerlidir, bu nedenle hiçbir değer iki kez görünmez.
1 ≤ k ≤ ağaçtaki düğüm sayısı.

Örnekler

Girdi: root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
Çıktı: 29
Açıklama: Artan sırayla değerler 6, 17, 22, 29, 41, 65, 90 şeklindedir ve dördüncü değer 29'dur. Bu, kökün sol alt ağacındaki dört değerin en büyüğüdür.

Girdi: root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
Çıktı: 2
Açıklama: En küçük değer, sola doğru devam eden yolun sonunda yer alır: 12, 5, 2. 9'un altındaki 7 ve -1 dolgusu bunu değiştirmez.

Ek soru

If the tree changes often and you are asked for the k'inci en küçük değeri many times, what could each node store so that every query takes O(h)?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir ikili arama ağacında sıralı dolaşım (sol alt ağaç, düğüm, sağ alt ağaç), değerleri artan sırada okur; bu nedenle ulaştığı k. değer yanıttır. Dolaşımı kendi yığınını kullanarak gerçekleştir ve o noktada dur; sıralama gerekmez.

Her değeri topla ve sırala

Sezgi

Şekli göz ardı et: -1 olmayan her girdiyi tut, sırala ve k-1 konumundaki öğeyi döndür. İlk örnekte sıralanmış liste 6, 17, 22, 29, 41, 65, 90 olur ve 3 konumunda 29 bulunur.

Bu yöntem, sıralı olsun ya da olmasın her ağaç için doğrudur. Bedeli de budur: ağacın zaten sahip olduğu sıralamayı göz ardı eder, sıralama için O(n log n) zaman ve kopya için O(n) bellek kullanır.

Algoritma

root içindeki -1 olmayan tüm girdileri topla.
Toplanan değerleri artan sırada sırala.
k-1 konumundaki değeri döndür.

def kthSmallest(root, k):
    values = [v for v in root if v != -1]  # every node, in any order
    values.sort()
    return values[k - 1]

Sıralı dolaşımı bir listeye aktarma

Sezgi

Herhangi bir düğümün altında, sol alt ağaç yalnızca daha küçük değerleri, sağ alt ağaç ise yalnızca daha büyük değerleri barındırır. Önce sol alt ağacı, ardından düğümü, sonra da sağ alt ağacı ziyaret edin ve aynı işlemi her alt ağaçta tekrarlayın: her düğüm, tüm küçük değerlerden sonra ve tüm büyük değerlerden önce gelir; böylece çıktı sıralanmış olur. İlk örnekte gezinme 6, 17, 22, 29, 41, 65, 90 sonucunu verir.

Tek bir geçiş sıralamanın yerini alır: O(n) zaman ve liste için O(n) alan gerekir. Yanıtın en soldaki yolun sonunda olduğu k = 1 durumunda bile ağacın tamamını ziyaret eder.

Algoritma

inorder(i) yazın: boş bir konumda (sondan sonra veya -1) geri dönün.
Aksi takdirde inorder(2*i+1) çağrısını yapın, root[i] değerini listeye ekleyin, ardından inorder(2*i+2) çağrısını yapın.
inorder(0) çağrısını yapın.
k-1 konumundaki liste öğesini döndürün.

def kthSmallest(root, k):
    n = len(root)
    values = []

    def inorder(i):
        if i >= n or root[i] == -1:
            return
        inorder(2 * i + 1)  # smaller values first
        values.append(root[i])
        inorder(2 * i + 2)  # then larger ones

    inorder(0)
    return values[k - 1]  # values is sorted

k'de duran yinelemeli sıralı dolaşım

Sezgi

Açık bir yığın, dolaşımı ortasında durdurmanı sağlar. Her düğümü yığına ekleyerek olabildiğince sola ilerle. En üstteki düğüm, henüz sayılmamış en küçük değerdir; çünkü ondan küçük her şey, boş olan ya da zaten sayılmış olan sol alt ağacında bulunur. Düğümü çıkarıp say; sıralı düzende sırada sağ alt ağacı gelir.

İlk örnekte k = 4 için: 41, 17, 6 değerlerini yığına ekle. 6 değerini, ardından 17 değerini çıkar ve sağ çocuğuna geç: 29 ve 22 değerlerini yığına ekle. 22 değerini, ardından dördüncü olan 29 değerini çıkar. Dolaşım 65 veya 90 düğümlerine hiç ulaşmaz.

Yığın, her seviye için en fazla bir düğüm tutar; bu nedenle alan karmaşıklığı O(h) olur. Dolaşım bir kez aşağı iner ve ardından k kez düğüm çıkarır: zaman karmaşıklığı O(h + k).

Algoritma

Boş bir yığın ve i = 0 ile başla.
i gerçek bir düğüm olduğu sürece, onu yığına ekle ve 2*i+1 konumuna ilerle.
En üstteki öğeyi i değişkenine çıkar ve k değerinden 1 çıkar.
k artık 0 ise root[i] değerini döndür.
Aksi takdirde 2*i+2 konumuna ilerle ve 2. adıma dön.

def kthSmallest(root, k):
    n = len(root)
    stack = []  # nodes whose left side is being visited, deepest on top
    i = 0
    while True:
        while i < n and root[i] != -1:  # go as far left as you can
            stack.append(i)
            i = 2 * i + 1
        i = stack.pop()  # the smallest value not counted yet
        k -= 1
        if k == 0:
            return root[i]
        i = 2 * i + 2  # then everything in its right subtree

Tuzaklar ve uç durumlar

Diziyi indeks sırasına göre okumak. Seviye sırası sıralı değildir: ilk örnek 41, 17, 65 ile başlar.
k için bir kayma hatası. Sayım 1'den başlar: listedeki k-1 konumunu döndür ve sayım k'ye ulaştığında gezinmeyi durdur.
Bir pop işleminden sonra sağ alt ağacı atlamak. İkinci örnekte 9 ve 7, 5'in sağ alt ağacındadır ve gezinme bunları hiçbir zaman saymaz.
Eksik bir çocuğu gerçek bir çocuk gibi ele almak. İndeksi dizinin sonunu aşan veya -1 değerini içeren bir çocuk boştur: 22, 9 indeksindedir; bu nedenle 19 ve 20 çocukları dizinin sonunu aşar.
Lua ve R dizileri 1'den başlar. 2*i+1 için düğüm indekslerini 0 tabanlı tut ve root[i + 1] öğesini oku.

Sıkça sorulan sorular3

Bir BST'de k'inci en küçük öğeyi bulmanın zaman karmaşıklığı nedir?

Yinelemeli sıralı dolaşım, derinliği h olan bir ağaç için O(h + k) zaman ve O(h) ek alan gerektirir. En kötü durumda, k = n olduğunda veya ağaç bir yol şeklinde olduğunda, bu O(n) olur.

Bir BST'de k'inci en büyük elemanı nasıl bulursunuz?

Dolaşımı tersine çevir: önce sağ alt ağaç, sonra düğüm, ardından sol alt ağaç. Böylece değerler azalan sırada listelenir. Düğümleri yığına eklerken olabildiğince sağa ilerle, bir düğüm çıkarıp sayacı artır ve her çıkarmadan sonra sol çocuğa geç. k. çıkarılan düğüm, en büyük k. değerdir.

Özyinelemeli inorder dolaşımını k'ıncı değerde nasıl durdurursunuz?

Özyineleme dışında, k değerinden başlayan bir sayaç tut. Bir düğümün sol alt ağacı döndükten sonra 1 çıkar ve sayaç 0 değerine ulaştığında düğümün değerini kaydet. Her çağrıdan sonra yanıt kaydedilmişse hemen dön. Böylece özyineleme, yığın sürümüyle aynı olur: O(h + k) zaman, O(h) alan.

def kthSmallest(root, k):
    # Kodu buraya yazın

Test #1

Test #2

Argümanlar

root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]
k = 4

Beklenen Çıktı

Kth Smallest Element in a BST

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her değeri topla ve sırala

Sıralı dolaşımı bir listeye aktarma

k'de duran yinelemeli sıralı dolaşım

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler