JS ALGORITHM
İkili Arama Ağacına (BST) TopView Algoritması
Binary Search Tree Algoritmalarında bugün ağaca yukarıdan baktığımızda (TopView) soldan sağa sıralama algoritmasını anlatacağız.
Bu algoritmada amacımız. İkili arama ağacına yukardan baktığımızda gördüğümüz düğümleri soldan sağa doğru yazdırmak.
Bunun için öncelikle ağacımızı inceliyelim. Ağacımız aslında X ve Y ekseninde bir koordinat düzleminde yer alıyor. Ortadaki resimde ızgaraları çizgilerini oluşturursak ve Root(value:1) → (0, 0) pozisyonunda dersek;
- 2 →(1,1)
- 5 → (2,2)
- 3 → (1,3)
- 6 → (3,3)
- 4 → (2,4)
Yukarıdaki resimde bir kişi ekrana yukarıdan baktığında üstten gördüğü düğümleri sadece ekrana yazdıralım istiyoruz. Yani en sağdaki resimde görüldüğü gibi 1,2,5, ve 6 düğümleri ekrana yazdırılacak. 3 sayısı 2 ‘nin altında ,4 sayısıda 5 nolu düğümün altında kaldığı için ekrana yazdırılmayacak.
Algoritmamızı önce adımlara bölelim.
- Tüm düğümlerin içerisine x,y değeri olacak şekilde eksenleri yazacağız.
- Bunların her X eksenindeki değer için Y en küçük olan elemanı bir map tutacağız.
- Bu topViewMap içerisindekileri array dönüştürüp, bunların sırasında en soldan en sağa olacak şekilde sort edeceğiz.
- Sort edilmiş bu array ekrana yazdıracağız.
1nci ve 2nci Adım
Öncelikle her bir düğümün içerisine x,y koordinatlarını yerleştirelim. Bunun için tüm düğümleri gezip bu gezme(traverse) sırasında sırasında koordinat sistemi bilgisini node eklememiz gerekiyor.
Düğümlere Konumları Atayalım
Bizim için her bir alt kademeye indiğimizde depth +1 olmalı, x ekseni içinse dist değeri sol düğüme giderken dist -1, sağ düğüme giderken dist + 1 olmalı.
Tüm düğümlerin üzerinden geçtiğimizde yandaki şekilde depth(y ekseni) ve dist(x ekseni) değerini oluşturmuş oluyoruz.
X ekseninde En Üstte Kalan Düğümleri Map atalım.
visit fonksiyonu içerisinde yapmamız gereken bir işte x eksenindeki her bir nokta için sadece en üstte olan düğümü tutan bir map oluşturmak.
Bunun içinde ilgili node.depth değeri en düşük değeri (en derinde olmayan, en yüksekte olan) düğümü bulum bunu mapOfTopNodes içerisine dolduruyoruz.
3ncü ve 4ncü Adım
Eğer yukarıdaki adımları yapmışsanız, bundan sonraki adımlar oldukça basit. Map içerisindeki değerleri Array dönüştürüp bunları X eksenine göre sıralamamız gerekiyor.
Kaynak
Okumaya Devam Et 😃
Bu yazının devamı veya yazı grubundaki diğer yazılara erişmek için bu linke tıklayabilirsiniz.
