CP #46: Binary Tree Problemleri 2
7. Implement In-Order Traversal Without Recursion
Su orneklere bakalim:
2. Node'un sagda subtree'si yok ve de node solda. Ornegin 7'yi ele alalim. Bu durumda successor kendi parent'i olacaktir. Cunku inorder traversal siralamasi bu sekilde: left, node, right.
Recursion kullanmadan, verilen bir binary tree'yi in-order seklinde traverse ederek, node degerlerini bir array icerisinde dondurunuz.
Cozum
Recursion kullandigimiz cozumde, ust uste revuesive fonksiyon cagrilari yaptigimizda, aslinda bizim icin bunlarin sirasini tutan bir system call stack var. Bunu simule etmek iyi bir baslangic olabilir. Adi uzerinde zaten, en son cagri yapilan fonksiyon ilk donecek olandir. Yani stack yapisi.
def inorder_non_recursive(tree):
# traverse ettigimiz degerleri tutacagimiz array
ret = []
# call-stack simulatoru
stack = []
# root node'dan basliyoruz
cur = tree
# stack'te bisey kalmadigi zaman ve de cur de None oldugu zaman
# traversal bitmis demektir.
while cur or stack:
# eger cur pointeri None degil ise
# sol subtree'ye gitmemiz gerek
if cur:
stack.append(cur)
cur = cur.left
else:
# simdi geldik sola gidebilecegimiz son yere
# simdi bu stack'te en ustte duran node icin
# sol subtree islemesi bitti
# demek ki bu node degerini traversal'da ret'e kaydedebiliriz
top_stack = stack.pop()
ret.append(top_stack.data)
# sol tarafi bitirdik, node'un kendi datasini da yazdirdik
# simdi sag tarafa gitmek gerekli
cur = top_stack.right
return ret
Her bir node'u bir kere ziyaret ediyoruz ve her bir ziyaretin maliyeti constant. Bu durumda O(n) time compl. sahip bir cozum elde etmis oluyoruz. Ayrica stack icerisinde maksimum tree yuksekligi kadar eleman tutuyoruz ki bu da O(h) oluyor. Ancak ret arrayinda turm elemanlari zaten tutacagimizdan, ve O(n) daha domine olacagindan, space compl. icin O(n) diyebiliriz.
8. Implement Pre-Order Traversal Without Recursion
Recursion kullanmadan, verilen bir binary tree'yi pre-order seklinde traverse ederek, node degerlerini bir array icerisinde dondurunuz. (leetcode)
Cozum
Evet bir onceki probleme cok benzese de, yine de biraz dusunmeyi gerektiriyor. Izleyecegimiz yol ayni, ama node degerini yazdirdigimiz nokta, node'un None olmadigi zamana denk geliyor bu sefer.
def preorder_non_recursive(tree):
ret = []
stack = []
cur = root
while cur or stack:
if cur:
# elimizde None olmayan bir node var ise
# bunu direk ret arrayina ekliyoruz
ret.append(cur.data)
# stack'e de eklemek gerekiyor ki
# sag node'a gecmeye calistigimizda bu node'un referansi elimizde olsun
stack.append(cur)
# son olarak da soldan devam ediyoruz cunku
# pre-order siralamasi boyle: root, left, right
cur = cur.left
else:
# yine stack'teki en ustteki elemani
# koparip, sag sub-tree'den devam ediyoruz
top_stack = stack.pop()
cur = top_stack.right
return ret
Time ve space compl. olarak bir onceki cozumle ayni, O(n).
9. Implement Post-Order Traversal Without Recursion
Recursion kullanmadan, verilen bir binary tree'yi post-order seklinde traverse ederek, node degerlerini bir array icerisinde dondurunuz. (leetcode)
Cozum
Onceki iki problemden biraz daha farkli bir problemle karsi karsiyayiz. Neden? Cunku elimize bir node geldigi zaman once sol sub-tree'yi sonra sag sub-tree'yi traverse edip, enson node degerini ret arrayina eklemek gerekiyor. Bu acidan pre-order ve in-order'dan ayriliyor. Yani hangi node'un sub-tree'lerinin traverse edilip edilmedigini biryerde tutmamiz gerekiyor.
def postorder_non_recursive(tree):
cur = tree
ret = []
stack = []
# bir node'un sol ve sag subtree'lerini traverse ettigimizde
# bu set'e ekleyecegiz ki, tekrar bu node geldiginde anlayalim
subtrees_traversed = set()
while cur or stack:
if cur:
stack.append(cur)
# yine olabildigince sola gidiyoruz cunku postorder siralamasi
# left, right, node seklinde
cur = cur.left
else:
# simdi elimizde None olan bir node var
# demek ki stack'te en ustte duran node bir leaf node
# eger bu node'un sol ve sag taraflari traverse edilmis ise
# node'u stackten pop edip degerini ret'e ekleyebiliriz
if stack[-1] in subtrees_traversed:
ret.append(stack.pop().data)
else:
# henuz daha sag taraf traverse edilmemis
# o yuzden bu node'u pop etmeden, sag tarafa geciyoruz
cur = stack[-1].right
# ve de sag tarafi da traverse ettigimizi merkeze bildiyirouz
subtrees_traversed.add(stack[-1])
return ret
Her bir node'u bir kere ziyaret ediyoruz ve de her bir ziyaretin maliyeti constant, bu durumda lineer O(n) bir time compl.'ye ulasiyoruz. Ekstra space olarak ret arrayi var, stack var ayrica da subtrees_traversed set'i var. Burada en dominant olani suphesiz ki ret arrayi, her node'u tutatcak, ve de O(n) maliyetine sahip olmus oluyor.
10. K-th Node In In-Order Traversal
Inorder traversal yaptigimizda, k'inci elemanin ne olacagini O(n) ile bulabiliriz. Ancak, her bir node'un, root node o olacak sekilde bakildiginda kac tane child node'a sahip oldugu bilgisini barindirdigini dusunelim. Bu durumda, inorder traversal yapildiginda k'inci node'un hangisi olacagini O(n)'den daha performansli olarak bulunuz.
(node class'i su sekilde gorulecek: Node(data, left, right, size))
Cozum
Problem aciklamasinda da behsedilen naive yontem ile inorder traversal yaparak, k'inci nodeu bulabiliriz. Ama bu yontem, bize ekstra olarak verilen bir node'un altinda kac tane child node oldugunu bilgisini kullanmiyor.
Peki bu bilgiyi nasil kullanabiliriz? Oncelikle in-order traversal yaptigimizda nasil bir sonuc cikiyor tekrar bakalim. Elimizde bir Node olsun, inorder traversal sonucu su sekilde olacaktir:
[sol_taraf, Node.data, sag_taraf]
Bu arrayin k'inci elemani bu uc bucket arasindan hangisine duser? Bunu bilebilmek icin sol_taraf sub-arrayinin uzunlugunu bilmemiz gerekir. Ve bu bilgi bize node.left.size seklinde veriliyor!
Ornegin sol_taraf 5 elemandan olusuyor ise, k=3 icin aradigimiz eleman sol tarafta demektir. k=6 icin ise aradigimiz eleman Node'un kendisi oluyor, ve biz bunu geri dondurecegiz. k=6'dan buyuk degerler icin ise sag tarafa navigate etmek gerekli.
def kth_node_inorder(tree, k):
cur = tree
while cur:
# sol tarafta kac node var bakalim
# solda child olmayabilir, bu durumda 0 kabul edelim
left_size = cur.left.size if cur.left else 0
# aranan eleman sag tarafta
if k > left_size + 1:
cur = cur.right
# her navigate ettigimizde k'yi left_size kadar azaltiyoruz
# cunku sanki root, cur.left olacagi icin, k artik onceki root'a gore
# relative bir deger haline geliyor
k -= left_size + 1
# aradigimiz eleman node'un kendisi
elif k == left_size + 1:
return cur
# eleman sol tarafta
else:
cur = cur.left
Bakacak olursak, her bir adimda, tree'de bir level ilerliyoruz. Ve her adimdaki maliyet constant. Bu durumda while dongusu en fazla tree yuksekligi kadar donecegi icin, toplam time compl. O(h) oluyor. Bu da haliyle O(n)'den cok daha iyi. Space compl. olarak da constant oldugunu goruyor ve kendimizi takdir ediyoruz.
11. Compute The Successor
Bir binary tree node'u icin, in-order traversalda kendisinden hemen sonra gelen elemana, successor adi veriliyor. Verilen bir binary tree node'u icin successor'u bulan bir algortma gelistiriniz. Her bir node'un parent bilgisi oldugunu kabul ediyoruz.
Cozum
Arkadaslar, burada naive cozum ile basliyoruz yine. Neden? Cunku tekerlegi bir sekilde dondurmek lazim. Bize root degil, bir node veriliyor, ama parent bilgisi mevcur. Gidip root'u bulup, inorder traversal yapip bir arrayda tutuyoruz. Verilen node'u bu array icerisinde bulup, kendisinden bir sonraki gelen node'u donduruyoruz.
def find_successor(node):
# once root'a gidelim
root = node
while root.parent:
root = root.parent
# inorder traversal yapacak metod
# path ise node'larin inorder sekilde siralanmis hali
def rec(node, path):
if not node:
return
rec(node.left, path)
path.append(node)
rec(node.right, path)
# simdi inorder traverlsai yapalim
path = []
rec(root, path)
# path icerisinde node'u bulunca
# bir sonraki eleman successor olacak
# ama verilen node son elemansa, successor None olacaktir
# bu yuzden son elemandan bir oncesinde iterasyonu bitiriyoruz
for i in range(len(path) - 1):
if path[i] == node:
return path[i + 1]
return None
Bakacak olursak O(n) time compl. sahip bir cozum. Ekstra space olarak da node'lari tuttutgumuz path arrayi var ki bu da O(n) maliyete sahip.
Ama elbette ki bize parent bilgisi verildiyse bunu kullanmamiz lazim ve de O(n)'nin altina dusmemiz lazim.
Eger bir node'un saginda bir subtree var ise, successor, bu subtree'yi inorder traverse ettigimizde en solda kalan node olacaktir. Burasi acik. Ama sag subtree yok ise? Bu durumda bize verilen node solda mi sagda mi ona bakmamiz gerekiyor. Eger node solda ise, kendisinden bir sonraki gelecek olan node kesinlikle kendi parent'i olacaktir. Peki node sagda ise?
Su orneklere bakalim:
1. Node'un sag subtreesi var. Ornegin 3'u ele alalim. Sagindaki subtrree inorder traverse edilirse en solda 0 kalacaktir. Bu durumda 3'un successor'u 0'dir.
2. Node'un sagda subtree'si yok ve de node solda. Ornegin 7'yi ele alalim. Bu durumda successor kendi parent'i olacaktir. Cunku inorder traversal siralamasi bu sekilde: left, node, right.
3. Node'un sagda subtree'si yok ve de node sagda. Ornegin 4'u ele alalim. Gozle bakarak goruyoruz ki (aslinda akil ile bakiyoruz xP, kalp gozu belki de xD) 4'un successor'u 3 olacaktir. Bunu nasil bulabiliriz? Surasi da goruluyor ki, 4'ten yavas yavas yukariya cikip, (yani parent'ten parent'e), 5'e ulasiyoruz. Ve de 5, kendi parent node'unun sol node'u. Bu durumda (sol node oldugu icin) kendisinin parent'i successor olacaktir.
Aslin intuition suradan geliyor, eger bir node sagda ise, inorder traversalda, o subtree icin en sonda yer alacaktir. Bu durumda, bu node'un successor'unu bulabilmek icin solda duran bir subtree bulup onun parentini almak gerekiyor.
def find_successor(node):
# eger sag subtree var ise
# inorder traversalda en sola dusecek eleman, surekli left'e gidip
# artik daha gidemedigimiz elemandir :)
cur = node
while cur.left:
cur = cur.left
return left
# bu noktada sag subtree yok
# bize verilen node'u, sol subtree'sinde iceren en yakin
# ancestor node'u ariyoruz. yukaridaki ornekte 2. ve 3. maddeye tekabul ediyor.
while node.parent and node.parent.right == node:
node = node.parent
return node.parent
Bakacak olursak, sagda subtree olsa da olmasa da en fazla tree yuksekligi kadar iterasyon yapiyoruz. Bu da demek oluyor ki O(h) time compl. sahip bir cozum elde ettik ki, bir ondekinden cok daha iyi. Ayrica ekstra space kullanmiyoruz.
Neler Ogrendik?
- Recursion olmadan tree traverse etmek icin stack yapisi kullanilir.
- inorder ve preorder icin, hatta postorderda da biraz modifiye edilerek kullanilmak uzere soyle bir pattern mevcut:
ret = []
stack = []
cur = root
while cur or stack:
if cur:
...
else:
...
return ret
Binary tree konusu yine bitmiyor. Bir sonraki postta yine binary tree isliyor olacagiz. Esen kalin.
Yorumlar
Yorum Gönder