Dengeli bir ikili ağaç aynı zamanda yükseklik dengeli ağaç olarak da bilinir. Sol alt ağaç ile sağ alt ağacın yükseklikleri arasındaki fark m'den fazla olmadığında ikili ağaç olarak tanımlanır; burada m genellikle 1'e eşittir. Bir ağacın yüksekliği, iki ağaç arasındaki en uzun yol üzerindeki kenarların sayısıdır. kök düğüm ve yaprak düğüm.
Yukarıdaki ağaç bir ikili arama ağacı . İkili arama ağacı, sol taraftaki her düğümün üst düğümden daha düşük bir değere sahip olduğu ve sağ taraftaki düğümün üst düğümden daha yüksek bir değere sahip olduğu bir ağaçtır. Yukarıdaki ağaçta n1 bir kök düğümdür ve n4, n6, n7 ise yaprak düğümlerdir. N7 düğümü kök düğüme en uzak düğümdür. n4 ve n6 2 kenar içerir ve kök düğüm ile n7 düğümü arasında üç kenar bulunur. n7 kök düğümden en uzak nokta olduğundan; dolayısıyla yukarıdaki ağacın yüksekliği 3'tür.
Şimdi yukarıdaki ağacın dengeli olup olmadığını göreceğiz. Sol alt ağaç n2, n4, n5 ve n7 düğümlerini içerirken sağ alt ağaç n3 ve n6 düğümlerini içerir. Sol alt ağacın iki yaprak düğümü vardır, yani n4 ve n7. n2 ve n4 düğümleri arasında yalnızca bir kenar ve n7 ve n2 düğümleri arasında iki kenar vardır; bu nedenle n7 düğümü kök düğümden en uzak olanıdır. Sol alt ağacın yüksekliği 2'dir. Sağ alt ağaç yalnızca bir yaprak düğümü, yani n6 içerir ve yalnızca bir kenarı vardır; dolayısıyla sağ alt ağacın yüksekliği 1'dir. Sol alt ağaç ile sağ alt ağacın yükseklikleri arasındaki fark 1'dir. 1 değerini aldığımıza göre yukarıdaki ağacın yükseklik dengeli bir ağaç olduğunu söyleyebiliriz. Yükseklikler arasındaki farkın hesaplanmasına ilişkin bu işlem, n2, n3, n4, n5, n6 ve n7 gibi her bir düğüm için gerçekleştirilmelidir. Her bir düğümü işlediğimizde k'nin değerinin 1'den fazla olmadığını göreceğiz, dolayısıyla yukarıdaki ağacın dengeli bir ağaç olduğunu söyleyebiliriz. ikili ağaç .
Yukarıdaki ağaçta n6, n4 ve n3 yaprak düğümlerdir; burada n6, kök düğümden en uzak düğümdür. Kök düğüm ile yaprak düğüm arasında üç kenar bulunur; dolayısıyla yukarıdaki ağacın yüksekliği 3'tür. n1'i kök düğüm olarak kabul ettiğimizde, sol alt ağaç n2, n4, n5 ve n6 düğümlerini içerirken, alt ağaç n3 düğümünü içerir. Sol alt ağaçta n2 bir kök düğümdür ve n4 ve n6 da yaprak düğümlerdir. n4 ve n6 düğümleri arasında n6, kök düğümünden en uzaktaki düğümdür ve n6'nın iki kenarı vardır; dolayısıyla sol alt ağacın yüksekliği 2'dir. Sağ alt ağacın solunda ve sağında herhangi bir alt ağaç yoktur; dolayısıyla sağ alt ağacın yüksekliği 0 olur. Sol alt ağacın yüksekliği 2 ve sağ alt ağacın yüksekliği 0 olduğundan sol alt ağaç ile sağ alt ağacın yüksekliği arasındaki fark 2 olur. Tanıma göre fark sol alt ağacın yüksekliği ile sağ alt ağacın yüksekliği arasında 1'den büyük olmamalıdır. Bu durumda fark 2 olur, bu da 1'den büyüktür; bu nedenle yukarıdaki ikili ağaç dengesiz bir ikili arama ağacıdır.
amrita rao aktör
Neden dengeli bir ikili ağaca ihtiyacımız var?
Dengeli bir ikili ağaca olan ihtiyacı bir örnekle anlayalım.
Yukarıdaki ağaç bir ikili arama ağacıdır çünkü tüm sol alt ağaç düğümleri ana düğümden daha küçüktür ve tüm sağ alt ağaç düğümleri üst düğümden daha büyüktür. Yukarıdaki ağaçta 79 değerini bulmak istediğimizi varsayalım. Öncelikle n1 düğümünün değerini 79 ile karşılaştırıyoruz; 79 değeri 35'e eşit olmadığı ve 35'ten büyük olduğu için n3 düğümüne yani 48'e geçiyoruz. 79 değeri 48'e eşit olmadığından ve 79 değeri 48'den büyük olduğundan sağa gidiyoruz 48'in çocuğu. 48. düğümün sağ çocuğunun değeri 79'dur ve bu da aranacak değere eşittir. Bir öğeyi (79) aramak için gereken atlama sayısı 2'dir ve herhangi bir öğeyi aramak için gereken maksimum atlama sayısı 2'dir. Bir öğeyi aramak için ortalama durum O(logn)'dur.
Yukarıdaki ağaç aynı zamanda bir ikili arama ağacıdır çünkü tüm sol alt ağaç düğümleri ana düğümden daha küçüktür ve tüm sağ alt ağaç düğümleri üst düğümden daha büyüktür. Yukarıdaki ağaçta 79 değerini bulmak istediğimizi varsayalım. Öncelikle 79 değerini n4 düğümüyle yani 13 ile karşılaştırıyoruz. 79 değeri 13'ten büyük olduğundan 13 düğümünün sağ çocuğuna, yani n2(21)'ye geçiyoruz. n2 düğümünün değeri 21 olduğundan 79'dan küçüktür, dolayısıyla yine 21. düğümün sağına doğru hareket ederiz. 21. düğümün sağ çocuğunun değeri 29'dur. 79 değeri 29'dan büyük olduğundan sağa doğru hareket ederiz. 29. düğümün çocuğu. 29. düğümün sağ çocuğunun değeri 35'tir ve bu 79'dan küçüktür, dolayısıyla 35. düğümün sağ çocuğuna, yani 48'e gideriz. 79 değeri 48'den büyüktür, dolayısıyla sağ çocuğa gideriz. 48 numaralı düğümün sağ alt düğümünün değeri 79'dur ve bu da aranacak değere eşittir. Bu durumda bir elemanı aramak için gereken atlama sayısı 5'tir. Bu durumda en kötü durum O(n)'dir.
Düğüm sayısı artarsa ağaç diyagramında1 kullanılan formül, ağaç diyagramında2 kullanılan formülden daha etkilidir. Yukarıdaki ağaçların her ikisinde de mevcut düğüm sayısının 100.000 olduğunu varsayalım. Ağaç diyagramında2 herhangi bir öğeyi aramak için harcanan süre 100.000 µs iken ağaç diyagramında bir öğeyi aramak için harcanan süre log(100.000) olup, bu da 16,6 µs'ye eşittir. Yukarıdaki iki ağaç arasındaki muazzam zaman farkını gözlemleyebiliyoruz. Dolayısıyla denge ikili ağacının doğrusal ağaç veri yapısına göre daha hızlı aramayı sağladığı sonucuna varıyoruz.