2-3 Ağaclar

2-3 ağacı, John Hopcroft tərəfindən icad edilmiş zərif bir məlumat strukturu olaraq, ikili axtarış ağacının funksionallığını təmin etmək üçün nəzərdə tutulmuşdur. Bu ağac, aşağıdakı xüsusiyyətlərə malik olan sıralanmış köklü bir ağacdır:

• Kök və hər bir daxili zirvə ya 2, ya da 3 uşağa sahibdir;

• Ağacın kökündən hər hansı bir yarpağa qədər olan məsafə eynidir.

Yeganə istisna, yalnız bir zirvədən ibarət olan ağacdır — bu halda ağacın kökü həm də yeganə zirvədir və eyni zamanda yarpaqdır, yəni uşaqları yoxdur. Bu xüsusiyyətlərin əsas ideyası ondan ibarətdir ki, l yarpağa malik bir ağacın hündürlüyü O(log l)-dir.

Verilən yarpaqların sayı l olduqda, l yarpağa malik bir neçə etibarlı 2-3 ağacı mövcud ola bilər. Məsələn, aşağıdakı şəkil dəqiq 6 yarpağa malik iki mümkün 2-3 ağacını göstərir.

Verilən l üçün, l yarpağa malik müxtəlif 2-3 ağaclarının sayını tapın. Bu say kifayət qədər böyük ola biləcəyi üçün, onu r modulunda çıxış edin.