Кіріспе
Ағаш түріндегі дерек құрылымы, жылдам іздеу үшін реттелген. Компьютер ғылымында іздеу ағашы – жиын ішіндегі нақты кілттерді табуға қолданылатын ағаш түріндегі дерек құрылымы. Ағаш іздеу ағашы ретінде жұмыс істеуі үшін, әрбір түйіндің кілті сол жақтағы тармақтардағы кез келген кілттерден үлкен, ал оң жақтағы тармақтардағы кез келген кілттерден кіші болуы керек. Іздеу ағаштарының артықшылығы – ағаш орынды тепе-тең болғандағы тиімді іздеу уақыты, яғни екі шеттегі жапырақтардың тереңдігі шамалас. Әртүрлі іздеу ағашы дерек құрылымдары бар, олардың кейбіреулері элементтерді тиімді қосуға және жоюға мүмкіндік береді, бұл операциялар ағаштың тепе-теңдігін сақтау керек. Іздеу ағаштары көбінесе ассоциативтік массивті жүзеге асыру үшін қолданылады. Іздеу ағашы алгоритмі орынды табу үшін кілт-мәнді жұптың кілтін пайдаланады, содан кейін қосымша сол кілт-мәнді жұпты сол нақты орынға сақтайды.
In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less than any keys in subtrees on the right. The advantage of search trees is their efficient search time given the tree is reasonably balanced, which is to say the leaves at either end are of comparable depths. Various search tree data structures exist, several of which also allow efficient insertion and deletion of elements, which operations then have to maintain tree balance. Search trees are often used to implement an associative array. The search tree algorithm uses the key from the key–value pair to find a location, and then the application stores the entire key–value pair at that particular location.
Бинарлық іздеу ағашы
Бинарлық іздеу ағашы – түйінге негізделген деректер құрылымы, онда әрбір түйінде кілт және екі кіші ағаш болады: сол және оң. Барлық түйіндер үшін сол кіші ағаштың кілті түйіннің кілтінен кіші, ал оң кіші ағаштың кілті түйіннің кілтінен үлкен болуы тиіс. Бұл кіші ағаштардың бәрі де бинарлық іздеу ағаштарының шарттарына сай болуы керек. Бинарлық іздеу ағашында іздеудің ең нашар жағдайдағы уақыт күрделілігі – ағаштың биіктігі, ол n элементі бар ағаш үшін O(log n) дейін төмен болуы мүмкін.
B-ағаш
B ағаштары – екілік іздеу ағаштарының жалпылама түрі, себебі әрбір түйінде өзгеретін саны бар тармақтар болуы мүмкін. Балалық түйіндердің белгілі бір диапазоны болғанымен, олар міндетті түрде деректермен толтырылмайды, демек B ағаштары кейбір жадты босқа жұмсауы мүмкін. Артықшылығы – B ағаштарын басқа өздігінен теңесетін ағаштар сияқты жиі теңестірудің қажеті жоқ. Түйін ұзындығының өзгеретін диапазонына байланысты, B ағаштары үлкен дерек блоктарын оқитын жүйелер үшін жақсырақ жұмыс істейді, сондай-ақ олар деректер базаларында кеңінен қолданылады. B ағашында іздеудің уақыттық күрделілігі O(log n) құрайды.
Тернарлық іздеу ағашы
Үштік іздеу ағашы - 3 түйінге ие болатын ағаш түрі: төменгі ұл, тең ұл және жоғары ұл. Әрбір түйін бір таңбаны сақтайды, ал ағаш өзі екілік іздеу ағашы сияқты реттелген, бірақ қосымша үшінші түйін болуы мүмкін. Үштік іздеу ағашында іздеу жасау үшін, ағашта бар-жоғын тексеру үшін бір жолдан тұратын мәтін беріледі. Теңгерілген үштік іздеу ағашында іздеудің уақыттық күрделілігі O(log n) құрайды.
Белгілі бір кілтті іздеу
Ағаш ретімен орналасқан деп есептесек, кілтті таңдап алып, оны ағаш ішінде іздеуге тырысамыз. Келесі алгоритмдер екілік іздеу ағаштары үшін жасалған, бірақ осы принципті басқа форматтағы ағаштарға да қолдануға болады.
Минималды және максималды іздеу
Сорталған ағашта ең кіші мән сол жаққа қарай ең шеткі түйінде, ал ең үлкен мән оң жаққа қарай ең шеткі түйінде орналасқан.