BST'de en yakın anahtar
Görev tanımı
Problem
Bir ikili arama ağacı (BST) birbirinden farklı tam sayı anahtarlar saklıyor. Kökü ve kesirli kısmı olabilen bir hedef verildiğinde, hedefe en yakın anahtarı döndür. İki anahtar eşit yakınlıktaysa küçük olanı döndür. Ağaçta her zaman en az bir düğüm var.
Örnekler
Input: tree = 8, left 3 with children 1 and 6 (6 has children 4 and 7),
right 10 with a right child 14; target = 5
Output: 4
Neden: 4 ve 6 ikisi de bir uzakta, 4 daha küçük
Input: same tree; target = 12.2
Output: 14
Neden: 14'ün uzaklığı 1,8, 10'unki ise 2,2
Input: tree = a single node 7; target = -100
Output: 7
Neden: edge case: tek anahtar en yakın olandır
İpuçları
0 / 3
Her düğümü ziyaret edip en iyisini tutmak işe yarar, ama bunu bir arama ağacı yapan sıralamayı yok sayar.
Hedefi sıkıştıran iki anahtar, onun altındaki en büyük ve üstündeki en küçük, hedef için normal bir aramanın izleyeceği yolun üzerindedir.
Hedefi arıyormuş gibi kökten aşağı in. Her düğümde mesafesini şimdiye kadar bulunan en iyiyle karşılaştır, eşitlikte küçük anahtarı tercih et; sonra hedef düğümden küçükse sola, değilse sağa adım at.
- Hedef zaman
- O(h)
- Hedef alan
- O(1)
Kısıtlar
- keys are distinct integers
- the tree has at least one node
- the target may have a fractional part
Çözüm
Hedef için bir arama tek bir kökten yaprağa yolu izler ve hedefin hemen altındaki ve hemen üstündeki anahtarların ikisi de bu yoldadır, çünkü arama her birinde dönmek zorundadır. En yakın anahtar bu ikisinden biridir, yani yalnız yoldaki düğümleri kontrol etmek yeter. Eşitlik kuralı mesafe ve anahtar çiftini karşılaştırarak ele alınır; bu, mesafeler eşleştiğinde küçük anahtarı tercih eder. h yüksekliğindeki bir ağaç için zaman O(h), alan O(1).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def closest_key(node, target):
best = node.val
while node:
# closer wins, and on a tie the smaller key wins
if (abs(node.val - target), node.val) < (abs(best - target), best):
best = node.val
node = node.left if target < node.val else node.right
return best
tree = T(8, T(3, T(1), T(6, T(4), T(7))), T(10, None, T(14)))
print(closest_key(tree, 5)) # -> 4
print(closest_key(tree, 12.2)) # -> 14
print(closest_key(T(7), -100)) # -> 7Kodda değil de fikirde mi takıldın? BST'de ekleme ve arama bunu anlatıyor.