Lowest Common Ancestor of a BST

Q: BST'de en düşük ortak atayı bulmanın 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 O(n) işlem gerektiren her düğümü aramanız gerekebilir. Bir arama ağacında, iki değeri bir düğümle karşılaştırmak her birinin hangi tarafta olduğunu gösterir; böylece kökten başlayarak tek bir yolu izlersiniz.

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ündeyse yanıt p olur ve iki değer eşitse yanıt o değerdir.

Ortaİkili arama ağacı

+10

Bir ikili arama ağacı, tree dizisinde yığın sırasına göre saklanıyor: 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. 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.

Ağaçta bulunan p ve q değerlerinin en düşük ortak atasının değerini döndüren lowestCommonAncestor fonksiyonunu yaz: her ikisini de alt ağacında bulunduran en derin düğüm. Bir düğüm kendi alt ağacının parçasıdır; bu nedenle p, q'nun üzerinde yer alıyorsa yanıt p'dir.

Fonksiyon

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

treeinteger-array: ikili arama ağacını düzey sırasına göre, 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 bir tree[i], -1 veya 0 ≤ tree[i] ≤ 10⁵ değeridir.
tree[0] hiçbir zaman -1 değildir, dolayısıyla 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 ve 15'ten yukarı çıkıldığında, ikisinin de ulaştığı ilk düğüm 8'dir: 3, onun sol çocuğudur ve 15, sağındaki 12'nin altındadır. Kök 20 de ortak bir atadır, ancak daha yukarıdadır.

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 ve bir düğüm kendi atası sayıldığından 12 her iki değeri de içerir ve onun altındaki hiçbir düğüm bunları içermez. Burada p daha büyük değerdir.

Girdi: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Çıktı: 70
Açıklama: Her iki değer de kök 50 değerinden büyük, bu yüzden ikisi de onun sağında yer alır. 70 düğümünde yolları ayrılır: 55 daha küçüktür ve solunda, 60 değerinin altında yer alır; 80 ise daha büyüktür.

Ek soru

p veya q ağaçta bulunmayabilecek olsaydı 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

Bir arama ağacı, her düğümde bir değerin nerede bulunduğunu söyler: küçük değerler solda, büyük değerler sağda. Kökten başlayıp her iki değeri de barındıran tarafa doğru ilerle. Aynı tarafı paylaşmayı bıraktıkları ilk düğüm cevaptır ve ona tek bir yol izleyerek ulaşırsın.

Ağacın tamamını, sırayı dikkate almadan ara

Sezgi

Bu yöntem her ikili ağaçta çalışır. Özyinelemeli find(i), i düğümündeki alt ağacın ne içerdiğini bildirir. p veya q değerini içeren bir düğüm kendisini bildirir: diğer değer onun altındaysa yanıt odur; değilse daha yukarıdaki bir düğüm her ikisini de görür. Diğer tüm düğümler iki çocuğuna da sorar. İkisi de bir şey bildirirse, p ve q farklı taraflardadır ve bu düğüm buluştukları yerdir; yalnızca biri bildirirse, bunu yukarı iletir.

3 ve 15 için 8, solundan 3 indeksini ve sağından 10 indeksini alır ve kendisini bildirir. Her düğümü ziyaret edebilir: O(n) zaman ve özyineleme için O(h).

Algoritma

find(i) yaz. i konumu boşsa (sondan sonraysa veya -1 ise), -1 döndür.
tree[i], p veya q ise i döndür.
2*i+1 ve 2*i+2 üzerinde find çağır. İkisi de bir şey bulduysa i döndür.
Aksi takdirde, bir şey bulan tarafı 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

Bir değeri her zamanki şekilde ara: kökten başla, değeri düğümden küçükse sola, büyükse sağa git. Kökten bir düğüme giden yol tektir; bu nedenle izlenen yol, değerin tüm atalarından ve başka hiçbir şeyden geçmez.

Her iki yolu da kaydet. Değerler farklı yönlere gidene kadar yollar aynı düğümleri paylaşır; bu nedenle ortak başlangıç, ortak ataları listeler ve son değer en aşağıdaki atadır. 3 ve 15 için yollar 20, 8, 3 ve 20, 8, 12, 15 şeklindedir: 20, 8 değerlerini paylaşırlar, dolayısıyla yanıt 8 olur. Her yol, seviye başına bir adım sürer: O(h) zaman ve listeler için O(h) alan.

Algoritma

path(target) yazın: 0 indeksinden başlayın, tree[i] değerini kaydedin, bu değer target'a eşit olduğunda durun; aksi takdirde target daha küçükse 2*i+1 indeksine, daha büyükse 2*i+2 indeksine geçin.
p'ye giden yolu ve q'ya giden yolu oluşturun.
Her iki listede de baştan başlayarak ilerleyin ve ortak olan 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

Ayrılana kadar aşağı doğru ilerle

Sezgi

p ve q aynı yönde ilerlerken iki yol örtüşür; bu yüzden ikisini birlikte yürütün. v değerini tutan bir düğümde, her iki değer de daha küçükse ikisi de sol alt ağaçta bulunur ve v altındaki tüm ortak atalar da oradadır: sola gidin. Her ikisi de daha büyükse sağa gidin.

Aksi takdirde, değerlerden biri daha küçük, diğeri daha büyüktür; dolayısıyla v düğümünün hiçbir çocuğu ikisini birden içermez ya da değerlerden biri v'ye eşittir ve v onun kendi atasıdır. Her iki durumda da v, ikisinin de üzerindeki en derin düğümdür. Üçüncü örnekte 50, her iki değerin de altındadır; bu yüzden 70'e doğru sağa gidilir. Burada 55 daha küçük, 80 ise daha büyüktür. Her seviyede bir karşılaştırma çifti yapılması O(h) zaman ve O(1) alan gerektirir.

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

Hareket kontrollerinde ≤ ve ≥ kullanmak. p = 12 ve q = 10 iken, yürüyüş 12'yi geçip 10'a gider, ardından 10'u döndürür veya ağacın dışına çıkar.
p < q olduğunu varsaymak. İkinci örnekte p daha büyük değerdir. Her ikisini de düğüme göre kontrol edin veya önce yerlerini değiştirin.
Değer yerine indeksi döndürmek. Yanıt i değil, tree[i]'dir.
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] değerini okuyun.

Sıkça sorulan sorular3

BST'de en düşük ortak atayı bulmanın 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 O(n) işlem gerektiren her düğümü aramanız gerekebilir. Bir arama ağacında, iki değeri bir düğümle karşılaştırmak her birinin hangi tarafta olduğunu gösterir; böylece kökten başlayarak tek bir yolu izlersiniz.

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ündeyse yanıt p olur ve iki değer eşitse yanıt o değerdir.

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

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

Lowest Common Ancestor of a BST

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Ağacın tamamını, sırayı dikkate almadan ara

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

Ayrılana kadar aşağı doğru ilerle

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler