Validate Binary Search Tree

Önce, dizi içinde nasıl gezineceğ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 oradaki değer -1 değilse gerçektir. [10, 5, 15, -1, -1, 6, 20] dizisinde kök 10’un 1 ve 2 indekslerinde 5 ve 15 çocukları vardır; 15 düğümünün ise 5 ve 6 indekslerinde 6 ve 20 çocukları vardır.

Çoğu kişinin denediği ilk fikir, her düğümü yalnızca iki çocuğuyla karşılaştırır. Bu ağaç, bunun neden başarısız olduğunu gösterir: 5 < 10, 15 > 10, 6 < 15 ve 20 > 15 koşullarının hepsi sağlanır, ancak 6, 10 düğümünün sağında yer alır. Tanım, bir alt ağaçtaki her değerden söz eder; bu yüzden tam olarak bunu kontrol edin.

v değerini tutan bir düğüm için, solundaki her şeyin v değerinden küçük olması, solundaki en büyük değerin v değerinden küçük olmasına denktir. Aynı şekilde, sağındaki her şeyin v değerinden büyük olması, oradaki en küçük değerin v değerinden büyük olmasına bağlıdır. İki küçük özyinelemeli yardımcı işlev bu en büyük ve en küçük değerleri bulur. Bir taraf boşsa en büyük değer -1, en küçük değer ise 100001 olur. Bunlar izin verilen aralığın dışında kalan değerlerdir; bu nedenle boş bir taraf hiçbir zaman koşulu bozmaz.

Bu yöntem doğrudur, ancak aynı işi tekrarlar. Bir düğüm, üzerindeki her ata için bir kez taranır; dolayısıyla derinliği h olan bir ağaçta toplam ziyaret sayısı yaklaşık n × h olur. Derinlik en fazla 14 olduğunda bu yöntem burada uygundur, ancak n düğümden oluşan tek uzun bir yol biçimindeki ağaçta bu sayı O(n²) düzeyine çıkar.

Sıralı dolaşım önce sol alt ağacı, sonra düğümü, ardından sağ alt ağacı ziyaret eder. İkili arama ağacında bu sıralama düzenlidir: soldaki her şey daha küçüktür, dolayısıyla önce gelir; sağdaki her şey daha büyüktür, dolayısıyla sonra gelir. İlk örnek 1, 3, 6, 8, 10, 12, 15 şeklinde okunur.

Tersi de geçerlidir ve bu, bunu bir test yapan şeydir. Herhangi bir v düğümünü ele alalım. Sıralı dizide, sol alt ağacının tamamı hemen öncesinde, sağ alt ağacının tamamı ise hemen sonrasında yer alır. Dizi kesin olarak artıyorsa, v düğümünden önceki her değer daha küçük, sonraki her değer ise daha büyüktür; dolayısıyla kural v düğümünde ve aynı şekilde diğer tüm düğümlerde de geçerlidir.

Öyleyse ağacı sıralı biçimde dolaş, değerleri topla ve her birini kendinden öncekiyle karşılaştır. İkinci örnek 5, 10, 6, 15, 20 şeklinde okunur: 10 değerinden 6 değerine iniş, yanlış taraftaki düğümü ortaya çıkarır. Üçüncü örnek 7, 12, 12 şeklindedir ve tekrarlanan 12 kesinlik kontrolünü geçemez. Her düğüm bir kez ziyaret edilir; zaman karmaşıklığı O(n), listenin alan karmaşıklığı ise O(n)'dir.

Kurala bir düğümün bakış açısından bakın. Her ata, o düğüme bir sınır koyar. Düğüm, a değerini taşıyan bir atanın sol alt ağacındaysa değeri a'dan küçük olmalıdır; sağ alt ağacındaysa a'dan büyük olmalıdır. Tüm bu sınırlar birlikte açık bir aralık oluşturur: (low, high). Düğüm, değeri bu aralığın tam olarak içinde olduğunda doğru yerdedir.

Bu aralığı aşağı inerken oluşturabilirsiniz. Kökün sınırı yoktur. v değerini taşıyan bir düğümden sol çocuğuna geçerken low korunur ve high, v olacak şekilde düşürülür; sağ çocuğuna geçerken high korunur ve low, v olacak şekilde yükseltilir. v değeri eski aralığa göre denetimi geçtiğinden, yeni sınır her zaman yerini aldığı sınırdan daha dardır.

İkinci örnekte 15, (10, no limit) aralığını alır ve bunu sol çocuğuna (10, 15) olarak aktarır. 6, 10'dan küçüktür; bu nedenle başka herhangi bir düğüme bakmadan denetim hemen başarısız olur. Değerler 0 ile 10^5 arasındadır; bu yüzden -1 ve 100001, "sınır yok" anlamına gelir.

Bekleyen düğümleri, her birinin aralığıyla birlikte bir yığında tutun. Her düğüm bir kez denetlenir; zaman karmaşıklığı O(n)'dir. Yığın, tek bir yol üzerindeki bekleyen düğümleri tutar; alan karmaşıklığı O(h)'dir. İlk bozuk aralık aramayı sonlandırır.