Дърво на двоично търсене в Java

binary search tree java implementation code examples

Опитайте Нашия Инструмент За Премахване На Проблемите

Изберете Операционната Система Изберете Програма За Проекция (По Желание)

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

Този урок обхваща двоично дърво за търсене в Java. Ще се научите да създавате BST, да вмъквате, премахвате и търсите елемент, да обхождате и прилагате BST в Java:

Бинарното дърво за търсене (наричано по-долу BST) е вид двоично дърво. Може да се определи и като двоично дърво, базирано на възел. BST се нарича още „Подредено двоично дърво“. В BST всички възли в лявото поддърво имат стойности, които са по-малки от стойността на основния възел.

По същия начин всички възли на дясното поддърво на BST имат стойности, които са по-големи от стойността на основния възел. Това подреждане на възли трябва да е вярно и за съответните поддървета.

=> Посетете тук за ексклузивната серия уроци за обучение по Java.

Какво ще научите:

Дърво на двоично търсене в Java
Заключение
- Препоръчително четене

BST не позволява дублиране на възли.

Диаграмата по-долу показва представяне на BST:

По-горе е показана примерна BST. Виждаме, че 20 е основният възел на това дърво. В лявото поддърво има всички стойности на възлите, които са по-малки от 20. В дясното поддърво има всички възли, които са по-големи от 20. Можем да кажем, че горното дърво отговаря на BST свойствата.

Структурата на данни BST се счита за много ефективна в сравнение с масиви и свързан списък, когато става въпрос за вмъкване / изтриване и търсене на елементи.

BST отнема O (log n) време за търсене на елемент. Докато елементите са подредени, половината от поддървото се изхвърля на всяка стъпка, докато се търси елемент. Това става възможно, тъй като можем лесно да определим грубото местоположение на елемента, който ще се търси.

По същия начин операциите за вмъкване и изтриване са по-ефективни в BST. Когато искаме да вмъкнем нов елемент, ние приблизително знаем в кое поддърво (ляво или дясно) ще вмъкнем елемента.

Създаване на бинарно дърво за търсене (BST)

Като се има предвид масив от елементи, трябва да изградим BST.

Нека направим това, както е показано по-долу:

Даден масив: 45, 10, 7, 90, 12, 50, 13, 39, 57

Нека първо разгледаме най-горния елемент, т.е. 45 като основен възел. Оттук нататък ще продължим да създаваме BST, като разглеждаме вече обсъдените свойства.

За да създадем дърво, ще сравним всеки елемент в масива с корена. След това ще поставим елемента на подходящо място в дървото.

Целият процес на създаване на BST е показан по-долу.

Завършен BST

Операции с бинарно дърво за търсене

BST поддържа различни операции. Следващата таблица показва методите, поддържани от BST в Java. Ще обсъдим всеки от тези методи поотделно.

Метод / операция	Описание
Поставете	Добавете елемент към BST, като не нарушавате BST свойствата.
Изтрий	Премахнете даден възел от BST. Възелът може да бъде коренният възел, нелистовият или листният възел.
Търсене	Потърсете местоположението на дадения елемент в BST. Тази операция проверява дали дървото съдържа посочения ключ.

Вмъкване на елемент в BST

Елемент винаги се вмъква като листен възел в BST.

По-долу са дадени стъпките за вмъкване на елемент.

Започнете от корена.
Сравнете елемента, който ще бъде вмъкнат, с основния възел. Ако е по-малко от корен, преминете през лявото поддърво или от дясното поддърво.
Преместете поддървото до края на желаното поддърво. Поставете възела в съответното поддърво като листен възел.

Нека да видим илюстрация на операцията за вмъкване на BST.

Помислете за следния BST и нека вмъкнем елемент 2 в дървото.

Фигура 1

Фигура 2

Операцията за вмъкване за BST е показана по-горе. На фиг. (1) показваме пътя, по който преминаваме, за да вмъкнем елемент 2 в BST. Също така показахме условията, които се проверяват на всеки възел. В резултат на рекурсивното сравнение елемент 2 се вмъква като дясното дъщерно число на 1, както е показано на фигура (2).

Операция за търсене в BST

За да търсим дали елемент присъства в BST, ние отново започваме от корена и след това обхождаме лявото или дясното поддърво в зависимост от това дали елементът, който трябва да се търси, е по-малък или по-голям от корена.

По-долу са изброени стъпките, които трябва да следваме.

Сравнете елемента, който трябва да се търси, с основния възел.
Ако ключът (елементът, който трябва да се търси) = корен, върнете коренния възел.
В противен случай ако ключ
Друго пресичане на дясно поддърво.
Повторно сравнявайте елементите на поддървото, докато ключът бъде намерен или не бъде достигнат краят на дървото.

Нека илюстрираме операцията за търсене с пример. Помислете, че трябва да търсим ключа = 12.

На фигурата по-долу ще проследим пътя, който следваме, за да търсим този елемент.

Както е показано на горната фигура, първо сравняваме ключа с root. Тъй като ключът е по-голям, прекосяваме дясното поддърво. В дясното поддърво отново сравняваме ключа с първия възел в дясното поддърво.

Откриваме, че ключът е по-малък от 15. Така се придвижваме към лявото поддърво на възел 15. Непосредственият ляв възел от 15 е 12, който съответства на ключа. В този момент спираме търсенето и връщаме резултата.

Премахнете елемента от BST

Когато изтрием възел от BST, има три възможности, както е обсъдено по-долу:

Възелът е листен възел

Ако възел, който трябва да се изтрие, е листен възел, тогава можем директно да изтрием този възел, тъй като той няма дъщерни възли. Това е показано на изображението по-долу.

Както е показано по-горе, възелът 12 е листови възел и може да бъде изтрит веднага.

Възелът има само едно дете

Когато трябва да изтрием възела, който има едно дете, тогава копираме стойността на детето във възела и след това изтриваме детето.

В горната диаграма искаме да изтрием възел 90, който има едно дъщерно устройство 50. Така че сменяме стойността 50 с 90 и след това изтриваме възел 90, който сега е дъщерен възел.

Node има две деца

Когато възел, който трябва да бъде изтрит, има две деца, тогава ние заместваме възела с inorder (ляв корен-десен) наследник на възела или просто казахме минималния възел в дясното поддърво, ако дясното поддърво на възела не е празно. Заместваме възела с този минимален възел и изтриваме възела.

В горната диаграма искаме да изтрием възел 45, който е основният възел на BST. Откриваме, че дясното поддърво на този възел не е празно. След това прекосяваме дясното поддърво и откриваме, че възел 50 е минималният възел тук. Така че заместваме тази стойност вместо 45 и след това изтриваме 45.

Ако проверим дървото, виждаме, че то отговаря на свойствата на BST. По този начин подмяната на възела беше правилна.

Внедряване на бинарно дърво за търсене (BST) в Java

Следващата програма в Java предоставя демонстрация на всички горепосочени операции BST, използвайки същото дърво, използвано в илюстрацията като пример.

как да отворите .dat файл?

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 ); } }

Изход:

Обход на бинарно дърво за търсене (BST) в Java

Дървото е йерархична структура, поради което не можем да го обхождаме линейно като други структури от данни като масиви. Всеки тип дърво трябва да бъде обходен по специален начин, така че всички негови поддървета и възли да бъдат посетени поне веднъж.

В зависимост от реда, в който коренният възел, лявото поддърво и дясното поддърво се обхождат в дърво, има определени обхождания, както е показано по-долу:

Вътрешно обръщане
Обръщане на предварителна поръчка
Обръщане на PostOrder

Всички горепосочени траверса използват техника с първоначална дълбочина, т.е.дървото се преодолява в дълбочина.

Дърветата също използват техниката за обхождане на първо място. Извиква се подходът, използващ тази техника „Поръчка на ниво“ обръщане.

В този раздел ще демонстрираме всеки от траверса, като използваме BST като пример.

С BST, както е показано на горната диаграма, обръщането на нивото на реда за горното дърво е:

Преминаване на нареждане на ниво: 10 6 12 4 8

Вътрешно обръщане

Подходът за вътрешно обхождане премина BST в реда, Ляво поддърво => RootNode => Десно поддърво . Вътрешното обхождане осигурява намаляваща последователност от възли на BST.

Алгоритъмът InOrder (bstTree) за InOrder Traversal е даден по-долу.

Прекосете лявото поддърво с помощта на InOrder (left_subtree)
Посетете основния възел.
Прекоси дясното поддърво с помощта на InOrder (right_subtree)

Вътрешното обръщане на горното дърво е:

4 6 8 10 12

Както се вижда, последователността на възлите в резултат на вътрешното обръщане е в низходящ ред.

Обръщане на предварителна поръчка

При обръщане на предварителна поръчка първо се посещава коренът, последван от лявото и дясното поддърво. Обръщането с предварителна поръчка създава копие на дървото. Може да се използва и в дърветата на изразите, за да се получи префикс израз.

Алгоритъмът за обръщане на PreOrder (bst_tree) е даден по-долу:

Посетете основния възел
Прекосете лявото поддърво с PreOrder (left_subtree).
Прекосете дясното поддърво с PreOrder (right_subtree).

Даденото по-горе обръщане за BST е:

10 6 4 8 12

Обръщане на PostOrder

Обръщането postOrder пресича BST в реда: Ляво поддърво-> Десно поддърво-> Корен възел . Обръщането PostOrder се използва за изтриване на дървото или получаване на израза postfix в случай на дървета на изрази.

Алгоритъмът за обхождане postOrder (bst_tree) е както следва:

Прекосете лявото поддърво с postOrder (left_subtree).
Прекосете дясното поддърво с postOrder (right_subtree).
Посетете основния възел

Обръщането на postOrder за горния пример BST е:

4 8 6 12 10

След това ще приложим тези ходове, като използваме техниката за дълбочина в изпълнение на Java.

//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) Уникално ли е бинарното дърво за търсене?

Отговор : Двоично дърво за търсене принадлежи към категория на двоично дърво. Той е уникален в смисъл, че не позволява дублиращи се стойности, а също така всички негови елементи са подредени според конкретното подреждане.

Заключение

Дърветата на двоичното търсене са част от категорията на двоичното дърво и се използват главно за търсене в йерархични данни. Използва се и за решаване на някои математически задачи.

В този урок видяхме прилагането на двоично дърво за търсене. Също така видяхме различни операции, извършени на BST с тяхна илюстрация, както и изследвахме ходовете за BST.

=> Внимавайте тук за простите учебни серии за Java.

Дърво на двоично търсене в Java - Примери за изпълнение и код