binary search tree c
Детаљан водич о бинарном стаблу претраживања (БСТ) на језику Ц ++ који укључује операције, имплементацију Ц ++, предности и примере програма:
Бинарно стабло претраживања или БСТ, како га популарно називају, је бинарно стабло које испуњава следеће услове:
- Чворови који су мањи од коренског чвора који је постављен као лева деца БСТ-а.
- Чворови који су већи од коренског чвора који је постављен као право подређено стање БСТ-а.
- Лево и десно подстабла су заузврат бинарна стабла претраживања.
Овакав распоред редоследа кључева у одређеном низу омогућава програмеру да ефикасније извршава операције попут претраживања, уметања, брисања итд. Ако чворови нису поредани, можда ћемо морати упоредити сваки чвор пре него што добијемо резултат операције.
=> Овде погледајте комплетну серију обука за Ц ++.
Шта ћете научити:
- Бинарно стабло претраживања Ц ++
- Основне операције
- Имплементација бинарног стабла претраживања Ц ++
- Предности БСТ-а
- Примене БСТ-а
- Закључак
- Препоручено читање
Бинарно стабло претраживања Ц ++
Пример БСТ је приказан испод.
Бинарно дрвеће за претрагу се такође назива и „уређено бинарно дрвеће“ због овог специфичног уређења чворова.
Из горњег БСТ-а можемо видети да лево подстабло има чворове мање од корена, тј. 45, док десно подстабло има чворове веће од 45.
Сада ћемо разговарати о неким основним операцијама БСТ-а.
Основне операције
# 1) Уметак
Операција уметања додаје нови чвор у бинарно стабло претраживања.
Алгоритам за операцију уметања бинарног стабла претраживања дат је у наставку.
који програм ће отворити епс датотеку
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; end
Као што је приказано у горњем алгоритму, морамо осигурати да је чвор постављен на одговарајући положај како не бисмо прекршили БСТ редослед.
Као што видимо у горњем редоследу дијаграма, правимо низ операција уметања. Након упоређивања кључа који се убацује са коренским чвором, бира се лево или десно подстабло да би се кључ уметнуо као чвор листа на одговарајућем положају.
# 2) Избриши
Операција брисања брише чвор који се подудара са датим кључем из БСТ-а. И у овој операцији морамо да преместимо преостале чворове након брисања тако да БСТ редослед не буде нарушен.
Стога, у зависности од тога који чвор морамо избрисати, у БСТ имамо следеће случајеве за брисање:
# 1) Када је чвор Леаф Ноде
Када је чвор који треба избрисати чвор у облику листа, тада чвор директно бришемо.
# 2) Када чвор има само Једно дете
Када чвор који треба избрисати има само једно дете, тада копирамо дете у чвор и бришемо дете.
# 3) Када чвор има двоје деце
Ако чвор који треба избрисати има двоје подређених, тада проналазимо наследника инордер-а за чвор, а затим копирамо инордер-наследника на чвор. Касније ћемо избрисати наследника инордер.
У горњем дрвету за брисање чвора 6 са двоје деце, прво проналазимо наследника инордер за тај чвор који треба избрисати. Наследника инордера проналазимо проналажењем минималне вредности у правом подстаблу. У горњем случају, минимална вредност је 7 у десном подстаблу. Копирамо га у чвор који треба избрисати, а затим бришемо наследника инордер.
# 3) Претрага
Операција претраживања БСТ-а тражи одређену ставку која је идентификована као „кључ“ у БСТ-у. Предност претраживања ставке у БСТ-у је та што не треба да претражујемо цело дрво. Уместо због наручивања у БСТ-у, само упоређујемо кључ са кореном.
Ако је кључ исти као роот, тада враћамо роот. Ако кључ није роот, упоређујемо га са роот-ом да бисмо утврдили да ли треба да претражимо лево или десно подстабло. Једном када пронађемо подстабло, треба да претражимо кључ и рекурзивно га тражимо у било ком од подстабала.
Следи алгоритам за операцију претраживања у БСТ-у.
Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end
Ако желимо да претражимо кључ са вредношћу 6 у горњем стаблу, прво упоређујемо кључ са коренским чвором, тј. Иф (6 == 7) => Не иф (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.
Даље се спуштамо до левог подстабла. Ако је (6 == 5) => Не.
Ако (6 Не; то значи 6> 5 и морамо се померити удесно.
Ако (6 == 6) => Да; кључ је пронађен.
# 4) Преласци
Већ смо разговарали о преласцима бинарног стабла. И у случају БСТ-а, можемо да пређемо дрво да бисмо добили секвенцу инОрдер, преордер или постОрдер. У ствари, када пређемо БСТ у секвенци Инордер01, тада ћемо добити сортирану секвенцу.
То смо показали на доњој илустрацији.
Прелазак горе наведеног стабла је следећи:
Унутрашња обилазница (лнр): 3 5 6 7 8 9 10
Прелазак предбиљежбе (нлр): 7 5 3 6 9 8 10
ПостОрдер прелазак (лрн): 3 6 5 8 10 9 7
Илустрација
Направимо бинарно стабло претраживања на основу података даних у наставку.
45 30 60 65 70
Узмимо први елемент као коријенски чвор.
# 1) 45
У наредним корацима поставићемо податке према дефиницији бинарног стабла претраживања, тј. Ако су подаци мањи од надређеног чвора, они ће бити постављени на лево дете, а ако су подаци већи од надређеног чвора, биће право дете.
како додати елемент у низ Јава
Ови кораци су приказани у наставку.
# 2) 30
# 3) 60
# 4) 65
# 5) 70
Када извршимо инверзни обилазак горњег БСТ-а који смо управо конструисали, редослед је следећи.
Видимо да редослед преласка има елементе поредане у растућем редоследу.
Имплементација бинарног стабла претраживања Ц ++
Покажимо БСТ и његове операције користећи имплементацију Ц ++.
#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'< Излаз:
Створено бинарно стабло претраживања (Инордер обилажење):
30 40 60 65 70
Избриши чвор 40
Преокрет за модификовано бинарно стабло претраживања:
30 60 65 70
У горњем програму, БСТ приказујемо за редослед преласка редоследом.
Предности БСТ-а
# 1) Претрага је врло ефикасна
Имамо све чворове БСТ-а у одређеном редоследу, стога је тражење одређене ставке врло ефикасно и брже. То је зато што не треба да претражујемо цело стабло и упоређујемо све чворове.
Само морамо да упоредимо основни чвор са ставком коју претражујемо, а затим одлучујемо да ли треба да претражујемо у левом или десном подстаблу.
# 2) Ефикасан рад у поређењу са низовима и повезаним листама
Када претражујемо ставку у случају БСТ, решавамо се половине левог или десног подстабла на сваком кораку, побољшавајући тако перформансе операције претраживања. То је за разлику од низова или повезаних листа у којима морамо секвенцијално упоређивати све ставке да бисмо претражили одређену ставку.
# 3) Уметање и брисање су бржи
Операције уметања и брисања такође су брже у поређењу са другим структурама података као што су повезане листе и низови.
Примене БСТ-а
Неке од главних примена БСТ-а су следеће:
- БСТ се користи за примену индекса на више нивоа у апликацијама база података.
- БСТ се такође користи за примену конструката попут речника.
- БСТ се може користити за примену различитих ефикасних алгоритама претраживања.
- БСТ се такође користи у апликацијама којима је потребан сортирани списак као улаз, попут мрежних продавница.
- БСТ се такође користе за процену израза помоћу стабала израза.
Закључак
Бинарна стабла претраживања (БСТ) су варијација бинарног стабла и широко се користе у пољу софтвера. Такође се називају уређеним бинарним стаблима јер се сваки чвор у БСТ поставља према одређеном редоследу.
Прелазак БСТ-а у редослед даје сортирани редослед предмета у растућем редоследу. Када се БСТ користе за претрагу, то је врло ефикасно и обавља се у кратком року. БСТ се такође користе за разне апликације попут Хуффмановог кодирања, вишестепеног индексирања у базама података итд.
=> Овде прочитајте популарне серије обуке за Ц ++.
Препоручено читање
- Структура података бинарног стабла у језику Ц ++
- Структура података АВЛ стабла и гомиле у Ц ++
- Структура података Б Трее и Б + Трее у Ц ++
- Основне улазно / излазне операције на Ц ++
- Основне И / О операције у Јави (улазни / излазни токови)
- Дрвеће на језику Ц ++: Основна терминологија, технике преласка и типови стабала Ц ++
- Излазне операције уноса датотека у Ц ++
- Показивачи и операције показивача у Ц ++