13- дәріс деректер қҰрылымы ретіндегі ағАШ. Бинарлы іздеу ағашы

Ағаштар іздеу құрылымы ретінде
Іздеудің бинарлы ағашы
Бинарлы ағаштар элементтерге ағаштардың орналасу ретімен сипатталуы мүмкін,
яғни олар элементтерді бекітілген ретпен сақтауы мүмкін. Сондықтан олар жеке
элементтерді іздеу барысында тиімді болып табылады. Бинарлы іздеу ағаштары бекітілген
ретпен элементтерде сақталады. Түбір элементінен кіші болатын барлық элементтер сол жақ
child
түбірінде сақталады. Түбір элементінен үлкен болатын барлық элементтер оң жақ
child
тармақталуында сақталады. Бұл қағида ағаштағы барлық түйіндер үшін рекурсивті
қолданылады.

Барлық бинарлы ағаштардың іздеу жапырақтары бір деңгейде орналаспайды.
Бинарлы іздеу ағашы балансталмаған болуы мүмкін.
Балансталмаған ағаштар
–
тармақтары бір деңгейге ерекшеленуі мүмкін ағаш. Бинарлы іздеу ағаштары
элементтерін
ағаш
өлшеміне
көбейтіп
және
төмендеткенде
құрылымдарды
қосымшалайды. Кейде бинарлы іздеу ағаштары тек бір
child
тармақтан тұруы мүмкін.
Мұндай бинарлы іздеу ағаштарын
толық емес ағаш
деп атайды.
Бинарлы іздеу ағаштарын қолдану
Бинарлы іздеу ағаштарының деректер құрылымы реттелген элементтер жиынынан тұрады.
Бинарлы іздеу ағаштары белгілі бір есептерді басқа деректер құрылымына қарағанда тиімді
орындауы мүмкін.
Мысалы
,
элементтерді сұрыптаудың тура ретімен қарау. Шеңбер бойымен
іздеу бинарлы іздеу ағаштарын қолдануда оңай орындалатын есептердің бірі болып
табылады. Бинарлы іздеу ағашының интерфейсін қарастырайық.

1-
листинг BSTree класының декларациясынан тұрады. Бұл – элементтерді
орналастыру, өшіру және қолжетімділік операциясынан тұратын бинарлы іздеу
ағашының класы. Ол, сонымен қатар BSTree сақталған элементтер санын
қайтаратын әдістен тұрады.

BSTree
класы
template class
болып табылады. Бұл әртүрлі деректер типін
сақтайтын кластардың көшірмесін құруға мүмкіндік береді. Бірақ бұл класты
қолданбас бұрын қолжетімділік, енгізу, өшіру элементтерін орындау үшін ==, < және
>
операторларын қолдану қажет.

жүктеу 497,39 Kb.

Достарыңызбен бөлісу: