Validate Binary Search Tree

Q: Bir ikili arama ağacını doğrulamanın zaman karmaşıklığı nedir?

Sıralı dolaşım denetimi ve aralık denetimi her düğümü bir kez ziyaret eder: O(n) zaman alır; derinliği h olan bir ağaçta aralık denetiminin yığını için O(h) ek alan gerekir. Her düğümü tüm alt ağaçlarıyla karşılaştırmak O(n × h) maliyetlidir; yol şeklindeki bir ağaçta bu değer O(n²) olur.

Q: Her değeri saklamadan, sıralı dolaşma kullanarak bir BST'nin geçerliliğini doğrulayabilir misin?

Evet. Denetim yalnızca her değeri kendisinden önceki değerle karşılaştırır; bu yüzden değerleri bir listede tutmak yerine önceki değeri bir değişkende sakla ve bir değer daha büyük değilse hemen false döndür. Ek alan, özyineleme veya yığın için O(h) düzeyine düşer.

Q: Bir ikili arama ağacı yinelenen değerler içerebilir mi?

Burada kullanılan katı tanıma göre hayır: eşit bir değer iki taraftan hiçbirine uymaz. Bazı ders kitapları, örneğin sağ tarafta, eşit değerlere izin verir. Bu kurala göre katı karşılaştırmalardan biri ≤ olur.

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

+10

İkili ağaç, yığın sırasına göre tree dizisinde saklanır: kök 0 indeksindedir, i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerindedir, -1 boş bir yeri belirtir ve dizinin sonunda fazladan -1 girdileri bulunabilir.

Ağaç bir ikili arama ağacıysa true, değilse false döndüren isValidBST fonksiyonunu yaz. İkili arama ağacında her düğümün değeri, sol alt ağacındaki tüm değerlerden kesinlikle büyük ve sağ alt ağacındaki tüm değerlerden kesinlikle küçüktür.

Fonksiyon

isValidBST(tree: integer-array) → boolean

treeinteger-array: ikili ağacı seviye sırasına göre, boş bir konum için -1 kullanarak
Döndürürboolean: Ağaç bir ikili arama ağacıysa doğru, aksi takdirde yanlış.

Kısıtlar

1 ≤ tree.length ≤ 32767
Her tree[i], -1 veya 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.
Değerler tekrarlanabilir.

Örnekler

Girdi: tree = [8, 3, 12, 1, 6, 10, 15]
Çıktı: true
Açıklama: Sırayla okunduğunda (sol alt ağaç, düğüm, sağ alt ağaç), değerler 1, 3, 6, 8, 10, 12, 15 olur. Değerler kesinlikle artar; bu nedenle her düğüm, tüm atalarının doğru tarafında bulunur.

Girdi: tree = [10, 5, 15, -1, -1, 6, 20]
Çıktı: false
Açıklama: Her düğüm sol çocuğundan büyük ve sağ çocuğundan küçüktür; ancak 5 indeksindeki 6, kökün sağ alt ağacında olduğundan 10'dan büyük olmalıdır.

Girdi: tree = [12, 7, 12]
Çıktı: false
Açıklama: Kökün sağ çocuğunda, köke eşit olan 12 bulunur. Sağ alt ağaç kesinlikle daha büyük olmalıdır; bu nedenle ağaç koşulu sağlamaz.

Ek soru

Bir düğümün ebeveyni (i-1)/2 indeksindedir; aşağı yuvarlanır. Yığın veya özyineleme yerine ebeveynler üzerinden ilerleyerek ağacı sıralı biçimde O(1) ek alan kullanarak dolaşabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Kural tüm alt ağaçları kapsar; bu nedenle her düğümü iki çocuğuyla karşılaştırmak yeterli değildir: derinlerdeki bir düğüm, birkaç seviye yukarıdaki bir atasının belirlediği sınırı aşabilir. Ya ağacı sıralı biçimde dolaşıp değerlerin kesin olarak arttığını kontrol edin ya da her düğüme atalarının izin verdiği aralığı aktarın.

Tam ağacın alt ağaçlarının her bir düğümünü karşılaştırın

Sezgi

Bir düğümün solundaki her değer, yalnızca oradaki en büyük değer v değerinden küçükse kendi v değerinden küçüktür; sağındaki her değer de yalnızca oradaki en küçük değer v değerinden büyükse kendi v değerinden büyüktür. İki özyinelemeli yardımcı bunları bulur. Boş bir taraf, değer aralığının dışında olan -1 veya 100001 değerini döndürür, böylece hiçbir zaman başarısız olmaz.

Her düğüm, her atası için bir kez taranır; derinliği h olan bir ağaçta yaklaşık n × h ziyaret gerçekleşir. Derinlik en fazla 14 olduğunda bu maliyet düşüktür, ancak n düğümlü bir yolda maliyet O(n²) düzeyine çıkar.

Algoritma

Değeri -1 olmayan her i indisini sırayla dolaşın.
2*i+1 konumundaki sol alt ağaçta bulunan en büyük değeri (-1 ise boş) ve 2*i+2 konumundaki sağ alt ağaçta bulunan en küçük değeri (100001 ise boş) bulun.
En büyük değer tree[i] değerine eşit veya ondan büyükse ya da en küçük değer tree[i] değerine eşit veya ondan küçükse false döndürün.
true döndürün.

def isValidBST(tree):
    n = len(tree)

    def largest(i):
        # Largest value in the subtree at index i, or -1 when that spot is empty.
        if i >= n or tree[i] == -1:
            return -1
        return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))

    def smallest(i):
        # Smallest value in the subtree at index i, or 100001 when that spot is empty.
        if i >= n or tree[i] == -1:
            return 100001
        return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))

    for i in range(n):
        if tree[i] == -1:
            continue
        # Everything on the left must be smaller, everything on the right larger.
        if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
            return False
    return True

In-order değerleri kesinlikle artmalıdır

Sezgi

Sıralı dolaşma önce sol alt ağacı, sonra düğümü, ardından sağ alt ağacı ziyaret eder; bu nedenle bir ikili arama ağacında değerleri sıralı biçimde okur.

Tersi de geçerlidir. Herhangi bir v düğümü için, sol alt ağacının tamamı dizide ondan hemen önce, sağ alt ağacının tamamı ise hemen sonra gelir. Dizi kesin olarak artıyorsa, v düğümünden önceki her değer daha küçük, sonraki her değer ise daha büyüktür; dolayısıyla bu kural v düğümünde ve aynı şekilde her düğümde geçerlidir.

İkinci örnek 5, 10, 6, 15, 20 şeklinde okunur: 10 değerinden 6 değerine düşüş, yanlış yere yerleştirilmiş düğümü ortaya çıkarır. Her düğüm bir kez ziyaret edilir: O(n) zaman ve liste için O(n) alan.

Algoritma

walk(i) yazın: konum boşsa durun; aksi takdirde 2*i+1 konumuna gidin, tree[i] değerini ekleyin, ardından 2*i+2 konumuna gidin.
Değerleri sırayla toplamak için walk(0) çağırın.
1 konumundan başlayarak her k konumu için, values[k-1] ≥ values[k] ise false döndürün.
true döndürün.

def isValidBST(tree):
    n = len(tree)
    values = []

    def walk(i):
        # Left subtree, then the node, then the right subtree.
        if i >= n or tree[i] == -1:
            return
        walk(2 * i + 1)
        values.append(tree[i])
        walk(2 * i + 2)

    walk(0)
    # A search tree read in order gives strictly increasing values.
    for k in range(1, len(values)):
        if values[k - 1] >= values[k]:
            return False
    return True

Ağaç boyunca izin verilen aralığı aşağıya taşı

Sezgi

Her ata bir düğüme bir sınır koyar: düğüm, a değerini taşıyan bir atanın sol alt ağacındaysa a değerinden küçük, sağ alt ağacındaysa a değerinden büyük olmalıdır. Bu sınırlar birlikte bir açık aralık oluşturur: (low, high). Düğüm, değeri bu aralığın kesin olarak içinde yer alıyorsa doğru konumdadır.

Aşağı inerken aralığı oluşturun. Sol çocuk low değerini korur ve high = v değerini alır; sağ çocuk high değerini korur ve low = v değerini alır. İkinci örnekte 15, sol çocuğuna (10, 15) aralığını aktarır ve 6 hemen başarısız olur. Değerler 0 ile 10^5 arasındadır; bu nedenle -1 ve 100001 sınır olmadığını belirtir. Her düğüm bir kez kontrol edilir; zaman karmaşıklığı O(n), yığındaki düğüm sayısı O(h) olur.

Algoritma

(0, -1, 100001) öğesini ekle: gerçek bir sınırı olmayan kökü.
(i, low, high) öğesini çıkar. tree[i], low ve high arasında kesin olarak değilse false döndür.
Her gerçek çocuğu ekle: sol çocuğu 2*i+1 konumuna (low, tree[i]) ile, sağ çocuğu 2*i+2 konumuna (tree[i], high) ile.
Yığın boş olduğunda true döndür.

def isValidBST(tree):
    n = len(tree)
    # Each entry: a node index and the open range (low, high) its value must fall in.
    # -1 and 100001 lie outside every allowed value, so they mean "no limit".
    stack = [(0, -1, 100001)]
    while stack:
        i, low, high = stack.pop()
        value = tree[i]
        if not (low < value < high):
            return False
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append((left, low, value))  # the left side must stay below value
        if right < n and tree[right] != -1:
            stack.append((right, value, high))  # the right side must stay above value
    return True

Tuzaklar ve uç durumlar

Bir düğümü yalnızca çocuklarıyla karşılaştırmak. [10, 5, 15, -1, -1, 6, 20] dizisinde her ebeveyn-çocuk çifti doğru görünür, ancak 6 kökün sınırını ihlal eder.
Eşit değerlere izin vermek. [12, 7, 12] geçerli değildir: < ile karşılaştırın, asla ≤ ile değil.
Alt sınır için “sınır yok” anlamında 0 kullanmak. Bu, geçerli [0] ağacını reddeder.
2*i+1 < tree.length denetimini yapmadan bir çocuğu okumak. [12, 7, 12] içinde 3 indeksi dizinin sonunu aşar.
Lua ve R'de diziler 1'den başlar. 2*i+1 için düğüm indekslerini 0 tabanlı tutun ve tree[i + 1] değerini okuyun.

Sıkça sorulan sorular3

Bir ikili arama ağacını doğrulamanın zaman karmaşıklığı nedir?

Sıralı dolaşım denetimi ve aralık denetimi her düğümü bir kez ziyaret eder: O(n) zaman alır; derinliği h olan bir ağaçta aralık denetiminin yığını için O(h) ek alan gerekir. Her düğümü tüm alt ağaçlarıyla karşılaştırmak O(n × h) maliyetlidir; yol şeklindeki bir ağaçta bu değer O(n²) olur.

Her değeri saklamadan, sıralı dolaşma kullanarak bir BST'nin geçerliliğini doğrulayabilir misin?

Evet. Denetim yalnızca her değeri kendisinden önceki değerle karşılaştırır; bu yüzden değerleri bir listede tutmak yerine önceki değeri bir değişkende sakla ve bir değer daha büyük değilse hemen false döndür. Ek alan, özyineleme veya yığın için O(h) düzeyine düşer.

Bir ikili arama ağacı yinelenen değerler içerebilir mi?

Burada kullanılan katı tanıma göre hayır: eşit bir değer iki taraftan hiçbirine uymaz. Bazı ders kitapları, örneğin sağ tarafta, eşit değerlere izin verir. Bu kurala göre katı karşılaştırmalardan biri ≤ olur.

def isValidBST(tree):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

tree = [8, 3, 12, 1, 6, 10, 15]

Beklenen Çıktı

true

Validate Binary Search Tree

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Tam ağacın alt ağaçlarının her bir düğümünü karşılaştırın

In-order değerleri kesinlikle artmalıdır

Ağaç boyunca izin verilen aralığı aşağıya taşı

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler