Екілік іздеу ағашы – сандар сұрыпталған тізімін жүргізуге мүмкіндік беретін деректер құрылымы.
- Екілік (екілік) ағаш шақырылады, себебі әрбір ағаш түйінінде ең көбі екі еншілес элемент болады.
- Іздеу ағашы, себебі ол санды O(log(n)) уақытында іздеу үшін пайдаланылуы мүмкін (уақыт күрделілігі T(n) = O(log(n))(ed. ескертпе) алгоритмі).
Екілік іздеу ағашын кәдімгі екілік ағаштан ажырататын қасиеттер:
- Сол жақ ішкі ағаштың барлық түйіндері түбір түйінінен кіші.
- Оң жақ ішкі ағаштың барлық түйіндері түбірлік түйіннен үлкен.
- Әрбір түйіннің екі ішкі ағаштары да BST болып табылады, яғни. олардың жоғарыдағы екі қасиеті бар.
Оң жақтағы екілік ағаш екілік іздеу ағашы емес, себебі "3" түйінінің оң жақ ішкі ағашында одан кіші мән бар.
Екілік іздеу ағашында орындауға болатын екі негізгі операция бар:
1. Санның екілік іздеу ағашында бар-жоғын тексеру.
Алгоритм BST қасиетіне байланысты, сондықтан әрбір сол жақ ішкі ағашта түбірден төмен мәндер болса, әрбір оң жақтағы ішкі ағашта түбірден жоғары мәндер болады.
Егер мән түбірден төмен болса, мән оң жақ ішкі ағашта жоқ деп сенімді түрде айта аламыз, яғни оны сол жақ ішкі ағаштан іздеу керек.
Және керісінше, егер мән түбірден жоғары болса, мән сол жақ ішкі ағашта емес екені сөзсіз, яғни оң жақтан іздеу керек.
Алгоритм:
If root == NULL
return NULL;
If number == root->data
return root->data;
If number < root->data
return search(root->left)
If number > root->data
return search(root->right)
Алгоритмді диаграмма арқылы көрнекі түрде көрсетуге тырысайық.
Егер мән табылса, төмендегі суретте көрсетілгендей, ол рекурсияның әрбір қадамы арқылы таралатындай мәнді қайтарамыз.
қайтару іздеу (құрылымдық түйін) функциясын төрт рет шақырғанымызды байқаған боларсыз. Жаңа түйінді немесе NULL мәнін қайтарған кезде іздеу (түбір) соңғы нәтижені қайтарғанша мән қайта-қайта қайтарылады.
Ешбір мән табылмаса, біз ақыр соңында NULL болатын соңғы түйіннің сол немесе оң еншілесіне жетеміз және ол таралады және қайтарылады.
2. Екілік іздеу ағашына мән енгізу (BST)
Мәнді дұрыс орынға енгізу іздеуге ұқсас, себебі біз сол ішкі ағаш түбірден кіші және оң ішкі ағаш түбірден үлкен деген ережені сәйкестендіруге тырысамыз.
Біз мәнге байланысты оң немесе сол ішкі ағашқа қарай жүреміз және сол немесе оң ішкі ағаш нөлге тең болатын нүктеге жеткенде, сол жерге жаңа түйін қоямыз.
Алгоритм:
If node == NULL
return createNode(data)
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
return node;
Алгоритм көрінгендей қарапайым емес. Бар BST-ге санды қалай қосатынымызды визуализациялауға тырысайық.
Біз түйінді қостық, бірақ біз әлі де ағаштың қалған бөлігіне зиян келтірместен функциядан шығуымыз керек. Бұл жерде соңында қайтару түйіні пайдалы болады. Бұл жағдайда NULL, жаңадан жасалған түйін қайтарылады және негізгі түйінге бекітіледі, әйтпесе сол түйін біз түбірлік түйінге оралғанша ешбір өзгеріссіз қайтарылады.
Бұл ағашқа қайта көтерілгенде, басқа түйіндерге қосылымдар өзгермейтініне кепілдік береді.
Си бағдарламалау тілінде BST енгізу және іздеудің толық коды төменде келтірілген:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(value){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct node* insert(struct node* root, int data)
{
if (root == NULL) return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}
void inorder(struct node* root){
if(root == NULL) return;
inorder(root->left);
printf("%d ->", root->data);
inorder(root->right);
}
int main(){
struct node *root = NULL;
root = insert(root, 8);
insert(root, 3);
insert(root, 1);
insert(root, 6);
insert(root, 7);
insert(root, 10);
insert(root, 14);
insert(root, 4);
inorder(root);
}
Бағдарламаның шығысы
1 ->3 ->4 ->6 ->7 ->8 ->10 ->14 ->
