Lowest Common Ancestor of a BST

Q: BST'de en düşük ortak ata işleminin zaman karmaşıklığı nedir?

Kökten yapılan yürüyüş tek bir yolu izler; bu nedenle derinliği h olan bir ağaçta O(h) zaman ve O(1) ek alan gerektirir. Dengeli bir ağaçta bu O(log n) ; tek bir yol şeklindeki ağaçta ise O(n) olur.

Q: İkili arama ağacındaki LCA, ikili ağaçtaki LCA'dan nasıl farklıdır?

Sıradan bir ikili ağaçta bir değer herhangi bir yerde olabilir; bu yüzden her düğümün iki alt ağacını da ararsın ve iş miktarı O(n) olur. Bir arama ağacında iki değeri bir düğümle karşılaştırmak, her birinin hangi tarafta olduğunu söyler; bu yüzden kökten başlayarak tek bir yolu izlersin. Özyinelemeli herhangi-ağaç yöntemi bir arama ağacında da işe yarar, ancak bu bilgiyi göz ardı eder.

Q: Bir düğüm kendi en düşük ortak atası olabilir mi?

Evet. Bir düğüm kendisinin atası sayılır; bu nedenle p , q 'nun üstünde olduğunda yanıt p 'dir. İki değer eşit olduğunda da aynı kural p 'yi verir. Gezinme her iki durumu da ele alır: geçerli düğüm değerlerden birine eşit olur olmaz durur.

Q: Yürüyüş neden p ve q'nun ayrıldığı ilk düğümde durur?

Bu düğümde bir değer daha küçük, diğeri ise daha büyüktür; dolayısıyla farklı alt ağaçlarda bulunurlar. Bunun altındaki her düğüm bu alt ağaçlardan yalnızca birinde yer alır ve her iki değeri birden içeremez. Ayrılma düğümü her iki değeri de içerir ve daha aşağıdaki hiçbir düğüm içermez; bu da en düşük ortak atanın tanımının ta kendisidir.

Ortaİkili arama ağacı

+10

Seviye sırasına göre tree dizisinde saklanan bir ikili arama ağacı ve bu ağaçta bulunan p ve q değerleri veriliyor. Kök 0 dizininde bulunur, i dizinindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) dizinlerinde bulunur, boş bir yeri -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üçük, sağ alt ağacındaki her değer ise daha büyüktür.

lowestCommonAncestor adlı bir fonksiyon yazın. Bu fonksiyon, p ve q değerlerinin en düşük ortak atasının değerini döndürmelidir: her ikisini de alt ağacında bulunduran en derindeki düğüm. Bir düğüm kendi alt ağacının parçası sayılır; bu nedenle p, q'nun üstündeyse yanıt doğrudan p olur.

Fonksiyon

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: ikili arama ağacını seviye sırasıyla, boş konumlar için -1 kullanarak
pinteger: bulunacak ilk değer
qinteger: bulunacak ikinci değer
Döndürürinteger: Alt ağacında hem p hem de q bulunan en derin düğümün değeri

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 olmaz, 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.
p ve q ağaçtaki düğümlerin değerleridir. Herhangi bir sırada gelebilirler ve eşit olabilirler.

Örnekler

Girdi: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Çıktı: 8
Açıklama: 3, 8'in sol çocuğudur ve 15, 8'in sağında 12'nin altında yer alır. Her birinden yukarı doğru çıkıldığında, ikisinin de ulaştığı ilk düğüm 8'dir; dolayısıyla cevap budur. Kök 20 de ortak bir atadır, ancak daha üsttedir.

Girdi: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Çıktı: 12
Açıklama: 10, 12'nin sol çocuğudur. Bir düğüm kendisinin de atası sayılır; bu nedenle 12'nin alt ağacında her iki değer de bulunur ve altındaki hiçbir düğümde ikisi birden bulunmaz: yanıt 12'dir. Değerler her iki sırada da gelebilir; burada p daha büyük olanıdır.

Girdi: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Çıktı: 70
Açıklama: Hem 55 hem de 80, kök 50'den büyüktür; bu yüzden ikisi de onun sağında yer alır. 70'te yolları ayrılır: 55 daha küçüktür ve solda (60'ın altında) yer alır, 80 ise daha büyüktür ve sağda yer alır. Dolayısıyla cevap 70'tir.

Gönderirken +12 gizli test

Ek soru

Tree'de p veya q eksik olabilseydi ve bu durumda fonksiyonun -1 döndürmesi gerekseydi neyi değiştirirdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Sıradan bir ikili ağaçta, her düğümün iki tarafını da aramadan bir değerin nerede bulunduğunu bilemezsiniz. Bir arama ağacı her düğümde şunu söyler: daha küçük değerler solda, daha büyük değerler sağdadır. Bu nedenle kökten başlayın ve her iki değeri de barındıran tarafa doğru ilerleyin. Değerlerin artık aynı tarafta olmadığı ilk düğüm yanıttır; bu düğümü tek bir yolu izleyerek bulursunuz ve ağacın geri kalanına hiç bakmazsınız.

Tüm ağacı, sıralamayı dikkate almadan ara

Sezgi

Öncelikle 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, ancak indeksi dizinin içindeyse ve o konumdaki değer -1 değilse gerçektir. [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] dizisinde, kök 20 indeksleri 1 ve 2 olan 8 ve 31 düğümlerine sahiptir; 4 indeksindeki 12 ise indeksleri 9 ve 10 olan 10 ve 15 düğümlerine sahiptir.

Bu ilk yöntem her ikili ağaçta çalışır. Özyinelemeli find(i), i konumundaki alt ağacın ne içerdiğini bildirir. Boş bir konum -1 bildirir. p veya q değerini taşıyan bir düğüm kendisini bildirir: diğer değer onun altındaysa yanıt bu düğümdür; diğer değer başka bir yerdeyse daha yukarıdaki bir düğüm her ikisini de görecektir. Aksi durumda düğüm her iki çocuğa da sorar. Her iki taraf da bir şey bildirirse p bir tarafta, q diğer taraftadır; dolayısıyla buluştukları düğüm bu düğümdür. Yalnızca bir taraf bir şey bildirirse, bildirilen değeri yukarı aktar.

p = 3 ve q = 15 için 8 düğümü, solundan indeks 3'ü, sağından ise indeks 10'u alır ve kendisini bildirir. Kök bu değeri solundan, sağından ise -1 alır ve 8 değerini yukarı aktarır.

Yöntem doğrudur, ancak her düğümü ziyaret edebilir: O(n) zaman ve özyineleme için O(h) alan kullanır. Değerlerin sıralamasından hiç yararlanmaz; oysa arama ağacının temel amacı budur.

Algoritma

find(i) yaz. i konumu boşsa (sonun ötesindeyse veya -1 ise), -1 döndür.
tree[i], p veya q ise i döndür.
find işlevini 2*i+1 ve 2*i+2 üzerinde çağır. Her ikisi de bir şey bulduysa i döndür.
Aksi takdirde, bir şey bulan tarafı döndür veya -1 döndür.
tree[find(0)] döndür.

def lowestCommonAncestor(tree, p, q):
    n = len(tree)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or tree[i] == -1:
            return -1
        if tree[i] == p or tree[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return tree[find(0)]

İki arama yolunu karşılaştırın

Sezgi

Şimdi sıralamayı kullan. Bir değeri, arama ağacının aranması gerektiği şekilde bulabilirsin: kökten başla, değer düğümden küçükse sola, büyükse sağa git ve değere ulaştığında dur. Bu yürüyüş, değerin tüm atalarından ve başka hiçbir şeyden geçmez; çünkü kökten bir düğüme giden yol tektir.

p için yürüyüşü ve q için yürüyüşü kaydet. İkisi de kökten başlar ve değerler farklı yönlere gidene kadar aynı düğümleri izler. Ortak başlangıç, ortak atalarının listesidir; dolayısıyla ortak son değer en alttakidir. 3 ve 15 için yollar 20, 8, 3 ve 20, 8, 12, 15 şeklindedir: 20, 8 değerlerini paylaşırlar ve cevap 8'dir. 12 ve 10 için yollar 20, 8, 12 ve 20, 8, 12, 10 şeklindedir ve cevap 12'dir.

Her yürüyüş seviye başına bir adım sürer; dolayısıyla zaman O(h) olur ve burada ağaç kaç düğüm içerirse içersin en fazla 14 adımdır. İki liste O(h) alan kullanır.

Algoritma

path(target) yazın: 0 indeksinden başlayın, tree[i] değerini kaydedin, eşit olduğunda target değerine ulaşınca durun; aksi takdirde target daha küçükse 2*i+1 indeksine, daha büyükse 2*i+2 indeksine geçin.
p için yolu ve q için yolu oluşturun.
Değerleri eşleştiği sürece her iki listede de baştan ilerleyin ve son eşleşmeyi aklınızda tutun.
Paylaşılan son değeri döndürün.

def lowestCommonAncestor(tree, p, q):
    def path(target):
        # The values met on the way from the root down to target.
        values = []
        i = 0
        while True:
            values.append(tree[i])
            if tree[i] == target:
                return values
            i = 2 * i + 1 if target < tree[i] else 2 * i + 2

    to_p, to_q = path(p), path(q)
    # Both paths start at the root; the answer is the last value they share.
    answer = to_p[0]
    for a, b in zip(to_p, to_q):
        if a != b:
            break
        answer = a
    return answer

Değerler ayrılana kadar aşağı in

Sezgi

p ve q aynı yönde ilerlediği sürece iki yol örtüşür, bu yüzden onları saklamanız gerekmez. İkisini aynı anda ilerletin. v değerini tutan bir düğümde, her iki değer de v değerinden küçükse ikisi de sol alt ağaçta bulunur ve v altındaki her ortak ata da sol alt ağaçtadır: sola gidin. İkisi de büyükse sağa gidin.

Aksi hâlde hedefe ulaşmışsınızdır. Ya değerlerden biri v değerinden küçük, diğeri büyük olduğundan farklı alt ağaçlarda yer alırlar ve v düğümünün hiçbir çocuğu ikisini birden içermez; ya da değerlerden biri v değerine eşittir ve bir düğüm kendi atasidir. Her iki durumda da v, ikisinin de üzerindeki en derin düğümdür.

Üçüncü örnekte kök 50, hem 55 hem de 80 değerlerinden küçük olduğundan sağa, 70 değerine gidersiniz. Burada 55 daha küçük ve 80 daha büyüktür: yanıt 70 olur. İkinci örnekte 20 değerinden 8 değerine, ardından 12 değerine gidersiniz; bu değer p'ye eşittir ve durursunuz.

Kökten başlayarak tek bir yolu izler, her seviyede bir karşılaştırma çifti yaparsınız; dolayısıyla zaman O(h), alan ise O(1) olur. Ağacın geri kalanı hiçbir zaman okunmaz.

Algoritma

i = 0 indeksinden başla.
v = tree[i] değerini oku.
p < v ve q < v ise 2*i+1 konumuna git ve tekrarla.
p > v ve q > v ise 2*i+2 konumuna git ve tekrarla.
Aksi takdirde v değerini döndür.

def lowestCommonAncestor(tree, p, q):
    i = 0  # start at the root
    while True:
        value = tree[i]
        if p < value and q < value:
            i = 2 * i + 1  # both are smaller: the answer is on the left
        elif p > value and q > value:
            i = 2 * i + 2  # both are larger: the answer is on the right
        else:
            return value  # they split here, or one of them is this node

Tuzaklar ve uç durumlar

Yürüyüş kısadır, bu yüzden hataların çoğu durdurma kuralından kaynaklanır.

Hareket testlerinde ≤ ve ≥ kullanmak. p = 12 ve q = 10 olduğunda, p ≤ 12 ve q ≤ 12 testi yanıtı geçerek 10 değerine ilerler ve yürüyüş buradan 10 değerini döndürür ya da ağacın dışına çıkar. Yalnızca her iki değer de kesin olarak aynı taraftayken hareket edin.
p < q olduğunu varsaymak. Değerler herhangi bir sırada gelebilir. İkisini de düğüme göre test edin ya da önce p daha küçük olacak şekilde yerlerini değiştirin.
Bir değerin diğerinin atası olabileceğini unutmak. Bu durumda yanıt, o değerin kendisidir; ebeveyni değil.
Değer yerine indeksi döndürmek. Fonksiyon i değil, tree[i] döndürür.
Tüm ağacı aramak. Bu doğru yanıtı verir, ancak tek bir yol yeterliyken ağaçtaki tüm düğümlere kadar ziyaret eder.
Dizilerin 1'den başladığı Lua ve R dillerindeki ofseti karıştırmak. 2*i+1 aritmetiği için düğüm indekslerini 0 tabanlı tutun ve tree[i + 1] okuyun.

Sıkça sorulan sorular4

BST'de en düşük ortak ata işleminin zaman karmaşıklığı nedir?

Kökten yapılan yürüyüş tek bir yolu izler; bu nedenle derinliği h olan bir ağaçta O(h) zaman ve O(1) ek alan gerektirir. Dengeli bir ağaçta bu O(log n); tek bir yol şeklindeki ağaçta ise O(n) olur.

İkili arama ağacındaki LCA, ikili ağaçtaki LCA'dan nasıl farklıdır?

Sıradan bir ikili ağaçta bir değer herhangi bir yerde olabilir; bu yüzden her düğümün iki alt ağacını da ararsın ve iş miktarı O(n) olur. Bir arama ağacında iki değeri bir düğümle karşılaştırmak, her birinin hangi tarafta olduğunu söyler; bu yüzden kökten başlayarak tek bir yolu izlersin. Özyinelemeli herhangi-ağaç yöntemi bir arama ağacında da işe yarar, ancak bu bilgiyi göz ardı eder.

Bir düğüm kendi en düşük ortak atası olabilir mi?

Evet. Bir düğüm kendisinin atası sayılır; bu nedenle p, q'nun üstünde olduğunda yanıt p'dir. İki değer eşit olduğunda da aynı kural p'yi verir. Gezinme her iki durumu da ele alır: geçerli düğüm değerlerden birine eşit olur olmaz durur.

Yürüyüş neden p ve q'nun ayrıldığı ilk düğümde durur?

Bu düğümde bir değer daha küçük, diğeri ise daha büyüktür; dolayısıyla farklı alt ağaçlarda bulunurlar. Bunun altındaki her düğüm bu alt ağaçlardan yalnızca birinde yer alır ve her iki değeri birden içeremez. Ayrılma düğümü her iki değeri de içerir ve daha aşağıdaki hiçbir düğüm içermez; bu da en düşük ortak atanın tanımının ta kendisidir.

Python

def lowestCommonAncestor(tree, p, q):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

Beklenen

Lowest Common Ancestor of a BST

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Tüm ağacı, sıralamayı dikkate almadan ara

İki arama yolunu karşılaştırın

Değerler ayrılana kadar aşağı in

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler