Бинарно стабло претраживања у Јави

binary search tree java implementation code examples

Испробајте Наш Инструмент За Елиминисање Проблема

Изаберите Оперативни Систем Изаберите Програм Пројекције (Опционо)

Опишите Свој Проблем

Овај водич покрива бинарно стабло претраживања на Јави. Научићете да креирате БСТ, уметнете, уклоните и претражите елемент, пређете и примените БСТ на Јави:

Бинарно стабло претраживања (у даљем тексту БСТ) је врста бинарног стабла. Такође се може дефинисати као бинарно стабло засновано на чворовима. БСТ се такође назива и „Уређено бинарно стабло“. У БСТ-у сви чворови у левом подстаблу имају вредности које су мање од вредности коренског чвора.

Слично томе, сви чворови десног подстабла БСТ имају вредности које су веће од вредности коренског чвора. Ово уређење чворова мора бити тачно и за одговарајућа подстабла.

=> Посетите овде за ексклузивну серију лекција за Јава тренинг.

Шта ћете научити:

Бинарно стабло претраживања у Јави
Закључак
- Препоручено читање

БСТ не дозвољава дуплиране чворове.

Дијаграм испод приказује БСТ представништво:

Изнад је приказан пример БСТ. Видимо да је 20 коријенски чвор овог стабла. Лево подстабло има све вредности чворова које су мање од 20. Десно подстабло има све чворове веће од 20. Можемо рећи да горње стабло испуњава БСТ својства.

Сматра се да је структура података БСТ врло ефикасна у поређењу са низовима и повезаном листом када је реч о уметању / брисању и претраживању предмета.

БСТ-у је потребно О (лог н) време да тражи елемент. Како се елементи уређују, половина подстабла се одбацује у сваком кораку док се тражи елемент. То постаје могуће јер лако можемо одредити грубу локацију елемента који треба претражити.

Слично томе, операције уметања и брисања су ефикасније у БСТ-у. Када желимо да убацимо нови елемент, отприлике знамо у које подстабло (лево или десно) ћемо убацити елемент.

Стварање бинарног стабла претраживања (БСТ)

С обзиром на низ елемената, морамо конструисати БСТ.

Урадимо то како је приказано у наставку:

Дати низ: 45, 10, 7, 90, 12, 50, 13, 39, 57

Хајде да прво размотримо горњи елемент тј. 45 као коријенски чвор. Одавде ћемо наставити са стварањем БСТ-а узимајући у обзир својства о којима смо већ разговарали.

Да бисмо креирали стабло, упоредићемо сваки елемент у низу са кореном. Тада ћемо елемент поставити на одговарајући положај у дрвету.

Читав поступак стварања БСТ-а приказан је у наставку.

Завршен БСТ

Бинарне операције претраживања стабла

БСТ подржава разне операције. Следећа табела приказује методе које БСТ подржава у Јави. О свакој од ових метода разговараћемо одвојено.

Метод / операција	Опис
Уметни	Додајте елемент у БСТ не кршећи БСТ својства.
Избриши	Уклоните дати чвор из БСТ-а. Чвор може бити коријенски чвор, нелистни или лисни чвор.
Претрага	Претражите локацију датог елемента у БСТ-у. Ова операција проверава да ли стабло садржи наведени кључ.

Уметни елемент у БСТ

Елемент се увек убацује као чвор листа у БСТ.

Доље су дати кораци за уметање елемента.

Почните од корена.
Упоредите елемент који треба уметнути са основним чвором. Ако је мање од корена, пређите преко левог или десног подстабла.
Пређите поддрветом до краја жељеног подстабла. Уметните чвор у одговарајуће подстабло као чвор листа.

Погледајмо илустрацију операције уметања БСТ-а.

Узмите у обзир следећи БСТ и допустимо да уметнемо елемент 2 у стабло.

Слика 1

Слика 2

Операција уметања за БСТ је приказана горе. На слици (1) приказујемо путању којом прелазимо да бисмо уметнули елемент 2 у БСТ. Такође смо приказали услове који се проверавају на сваком чвору. Као резултат рекурзивног поређења, елемент 2 је уметнут као десно дете од 1, као што је приказано на слици (2).

Операција претраживања у БСТ-у

Да бисмо претражили да ли је елемент присутан у БСТ-у, поново почињемо од корена, а затим прелазимо левим или десним подстаблом у зависности од тога да ли је елемент који треба претраживати мањи или већи од корена.

У наставку су наведени кораци које морамо следити.

Упоредите елемент који треба претражити са основним чвором.
Ако је кључ (елемент који треба претражити) = роот, вратите роот чвор.
Иначе ако је кључ
Друго кретање десним подстаблом.
Непрекидно упоређујте елементе подстабла док се кључ не пронађе или док се не дође до краја стабла.

Илуструјмо операцију претраживања на примеру. Узмите у обзир да морамо претражити кључ = 12.

На доњој слици ћемо пратити пут којим идемо у потрази за овим елементом.

Као што је приказано на горњој слици, прво упоређујемо кључ са роот-ом. Пошто је кључ већи, прелазимо кроз десно подстабло. У десном подстаблу поново упоређујемо кључ са првим чвором у десном подстаблу.

Открили смо да је кључ мањи од 15. Дакле, прелазимо у лево подстабло чвора 15. Непосредни леви чвор 15 је 12 који се подудара са кључем. У овом тренутку заустављамо претрагу и враћамо резултат.

Уклоните елемент са БСТ-а

Када избришемо чвор из БСТ-а, постоје три могућности о којима се говори у наставку:

Чвор је чвор листа

Ако је чвор који треба избрисати лисни чвор, тада можемо директно да га избришемо јер нема подређених чворова. Ово је приказано на доњој слици.

Као што је горе приказано, чвор 12 је лисни чвор и може се одмах избрисати.

Чвор има само једно дете

Када треба да избришемо чвор који има једно дете, онда копирамо вредност детета у чвор, а затим избришемо дете.

У горњем дијаграму желимо да избришемо чвор 90 који има једно дете 50. Дакле, вредност 50 заменимо са 90, а затим избришемо чвор 90 који је сада подређени чвор.

Чвор има двоје деце

Када чвор који треба избрисати има двоје деце, тада га заменимо наследником чвора (лево-корен-десно) или једноставно изговоримо минимални чвор у десном подстаблу ако десно поддрево чвора није празно. Чвор замењујемо овим минималним чвором и бришемо чвор.

У горњем дијаграму желимо да избришемо чвор 45 који је основни чвор БСТ-а. Открили смо да десно подстабло овог чвора није празно. Затим прелазимо десно подстабло и налазимо да је чвор 50 овде минимални чвор. Дакле, замењујемо ову вредност уместо 45, а затим бришемо 45.

Ако проверимо дрво, видећемо да оно испуњава својства БСТ-а. Стога је замена чвора била исправна.

Имплементација бинарног стабла претраживања (БСТ) у Јави

Следећи програм на Јави пружа демонстрацију свих горе наведених БСТ операција користећи исто дрво коришћено на илустрацији као пример.

Питања и одговори за интервју са селеном вебдривер-ом

class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String() args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 /  10 90 /  / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }

Излаз:

Прелазак бинарног стабла претраживања (БСТ) у Јави

Стабло је хијерархијска структура, стога га не можемо линеарно прелазити попут других структура података, попут низова. Било коју врсту стабла треба прећи на посебан начин, тако да се сва њена стабла и чворови посете бар једном.

У зависности од редоследа којим се коријенски чвор, лево и десно подстабло прелазе на дрвету, постоје одређени преласци као што је приказано доле:

Инордер Траверсал
Пребацивање предбиљежбе
ПостОрдер Траверсал

Све горе поменуте технике користе технику прве дубине, тј. Дрво се прелази у дубину.

Дрвеће такође користи технику преласка у ширину. Назван је приступ који користи ову технику „Левел Ордер“ преокрет.

У овом одељку ћемо показати сваки од прелаза користећи пример БСТ-а.

Са БСТ-ом, као што је приказано на горњем дијаграму, прелазак реда нивоа за горње стабло је:

Прелазак редоследа нивоа: 10 6 12 4 8

Инордер Траверсал

Приступ унутрашњим прелазима прелазио је БСТ по редоследу, Лево подстабло => РоотНоде => Десно поддрево . Унутарња обилазница пружа опадајући низ чворова БСТ-а.

Алгоритам ИнОрдер (бстТрее) за ИнОрдер Траверсал је дат у наставку.

Пређите левим подстаблом користећи ИнОрдер (лефт_субтрее)
Посетите основни чвор.
Пређите десно подстабло помоћу ИнОрдер (ригхт_субтрее)

Унутрашњи обилазак горњег дрвета је:

4 6 8 10 12

Као што се види, редослед чворова као резултат унутрашњег заокрета је у опадајућем редоследу.

Пребацивање предбиљежбе

У превртању унапред, прво се посећује корен, а затим лево и десно подстабло. Прелазак унапред креира копију стабла. Такође се може користити у стаблима израза за добијање префиксног израза.

Алгоритам за прелазак ПреОрдер (бст_трее) дат је у наставку:

Посетите основни чвор
Пређите преко левог подстабла помоћу ПреОрдер (лефт_субтрее).
Пређите десно подстабло помоћу ПреОрдер (ригхт_субтрее).

Прелазак унапред за БСТ дат је горе:

10 6 4 8 12

ПостОрдер Траверсал

Прелазак постОрдер прелази БСТ редоследом: Лево подстабло-> Десно подстабло-> Коријенски чвор . ПостОрдер прелазак се користи за брисање стабла или добијање израза постфикса у случају стабала израза.

Алгоритам за прелазак постОрдер (бст_трее) је следећи:

Пређите преко левог подстабла са постОрдер (лефт_субтрее).
Пређите десно подстабло помоћу постОрдер (ригхт_субтрее).
Посетите основни чвор

Преокрет постОрдер за горњи пример БСТ је:

4 8 6 12 10

Даље, ми ћемо применити ове прелазе користећи технику дубине у Јава имплементацији.

//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String() args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }

Излаз:

Често постављана питања

П # 1) Зашто нам је потребно бинарно стабло претраживања?

Одговор : Начин на који претражујемо елементе у линеарној структури података попут низова помоћу бинарне технике претраживања, при чему је дрво хијерархијска структура, потребна нам је структура која се може користити за лоцирање елемената у дрвету.

Ту долази Бинарно стабло претраживања које нам помаже у ефикасном претраживању елемената на слици.

П # 2) Која су својства бинарног стабла претраживања?

Одговор : Бинарно стабло претраживања које припада категорији бинарног стабла има следећа својства:

Подаци похрањени у бинарном стаблу претраживања јединствени су. Не дозвољава дуплиране вредности.
Чворови левог подстабла мањи су од коренског чвора.
Чворови десног подстабла већи су од коренског чвора.

П # 3) Које су апликације бинарног стабла претраживања?

Одговор : Бинарно дрвеће за претрагу можемо користити за решавање неких континуираних функција у математици. Претраживање података у хијерархијским структурама постаје ефикасније са бинарним стаблима претраживања. Са сваким кораком смањујемо претрагу за пола подстабла.

П # 4) Која је разлика између бинарног стабла и бинарног стабла претраживања?

Одговор: Бинарно стабло је хијерархијска структура стабла у којој сваки чвор познат као родитељ може имати највише двоје деце. Бинарно стабло претраживања испуњава сва својства бинарног стабла и такође има своја јединствена својства.

У бинарном стаблу претраживања, лево подстабла садрже чворове који су мањи или једнаки кореновском чвору, а десно подстабло има чворове веће од коренског чвора.

П # 5) Да ли је бинарно стабло претраживања јединствено?

Одговор : Бинарно стабло претраживања припада категорији бинарног стабла. Јединствен је у смислу да не дозвољава дуплиране вредности, а такође су и сви његови елементи поређани према одређеном редоследу.

Закључак

Стабла бинарног претраживања део су бинарне категорије стабла и углавном се користе за претрагу хијерархијских података. Такође се користи за решавање неких математичких задатака.

У овом упутству видели смо примену бинарног стабла претраживања. Такође смо видели разне операције изведене на БСТ-у са њиховом илустрацијом, а такође смо истраживали и прелазе за БСТ.

=> Овде припазите на једноставну серију Јава тренинга.

Бинарно стабло претраживања у Јави - примери примене и кода