İkitərəfli Axtarış Ağacının Qurulması

İkitərəfli Axtarış Ağacı (İAA) — kökü olan ikitərəfli ağacdır və aşağıdakı xüsusiyyətlərə malikdir:

• Sol alt ağac yalnız kökdəkindən ciddi şəkildə kiçik olan dəyərlərə malik düyünlərdən ibarətdir.

• Sağ alt ağac yalnız kökdəkindən ciddi şəkildə böyük olan dəyərlərə malik düyünlərdən ibarətdir.

• Bütün düyün dəyərləri fərqlidir.

• Sol və sağ alt ağaclar da rekursiv olaraq ikitərəfli axtarış ağacıdır.

Yeni düyün əlavə edilərkən aşağıdakı alqoritmdən istifadə olunur:

1. Əgər ağac boşdursa, yeni düyün kök olur və əlavəetmə prosesi başa çatır. Əks halda, 2-ci addıma keçin.

2. Cari düyün kimi ağacın kökünü təyin edin.

3. Əgər yeni düyünün dəyəri cari düyünün dəyərindən kiçikdirsə:

   • Əgər cari düyünün sol alt ağacı boşdursa, yeni düyün cari düyünün sol övladı olur və alqoritm bitir.

   • Əks halda sol alt ağacın kökünü cari düyün kimi götürün və 3-cü addıma qayıdın.

4. Əgər yeni düyünün dəyəri cari düyünün dəyərindən böyükdürsə:

   • Əgər cari düyünün sağ alt ağacı boşdursa, yeni düyün cari düyünün sağ övladı olur və alqoritm bitir.

   • Əks halda sağ alt ağacın kökünü cari düyün kimi götürün və 3-cü addıma qayıdın.

İAA-nın strukturu daxilolma ardıcıllığından asılıdır. Müxtəlif ardıcıllıqlar fərqli strukturlar yarada bilər, hətta ədədlər eyni olsa da.

1 2 3 ardıcıllığına baxaq. Aşağıdakı İAA yaranır:

Əgər daxilolma ardıcıllığı 2 1 3 olsa, belə bir ağac alınar:

Digər tərəfdən, müxtəlif daxilolma ardıcıllıqları eyni İAA strukturunu verə bilər. Məsələn, 2 1 3 ardıcıllığı ilə 4 6 2 ardıcıllığı eyni İAA strukturunu yaradacaq. O zaman ağac belə olacaq:

Verilmiş n düyün üçün, həmin İAA ilə eyni struktura malik neçə fərqli daxilolma ardıcıllığı mövcuddur? Düyün dəyərləri 1..m aralığından seçilir.