Меню

Бінарне дерево пошуку на Java - приклади реалізації та коду

  • Головна
  • Інший
  • Бінарне дерево пошуку на Java - приклади реалізації та коду

binary search tree java implementation code examples

Спробуйте Наш Інструмент Для Усунення Проблем

Цей підручник охоплює бінарне дерево пошуку на Java. Ви навчитеся створювати BST, вставляти, видаляти та шукати елемент, обходити та впроваджувати BST на Java:

Бінарне дерево пошуку (далі - BST) - це тип бінарного дерева. Його також можна визначити як двійкове дерево на основі вузла. BST також називається 'впорядковане двійкове дерево'. У BST всі вузли в лівому піддереві мають значення, менші за значення кореневого вузла.

Подібним чином усі вузли правого піддерева BST мають значення, які перевищують значення кореневого вузла. Це впорядкування вузлів має бути справедливим і для відповідних піддерев.

=> Завітайте сюди, щоб ознайомитись із ексклюзивною серією навчальних посібників Java.

Бінарне дерево пошуку в Java

Що ви дізнаєтесь:

Бінарне дерево пошуку в Java

BST не дозволяє дублювати вузли.

На діаграмі нижче показано подання 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 показаний нижче.

Бінарне дерево пошуку - процес створення 1

bst будівництво

завершено BST
Завершено BST

Операції з бінарним деревом пошуку

BST підтримує різні операції. У наступній таблиці наведені методи, підтримувані BST в Java. Ми обговоримо кожен із цих методів окремо.

Спосіб / операціяОпис
ВставитиДодайте елемент до BST, не порушуючи властивостей BST.
ВидалитиВидаліть даний вузол з BST. Вузлом може бути кореневий вузол, нелистовий або листовий вузол.
ПошукШукайте місце розташування даного елемента в BST. Ця операція перевіряє, чи містить дерево вказаний ключ.

Вставте елемент у BST

Елемент завжди вставляється як листовий вузол у BST.

Нижче наведено кроки для вставки елемента.

  1. Почніть з кореня.
  2. Порівняйте елемент, який потрібно вставити, з кореневим вузлом. Якщо воно менше кореня, перейдіть лівим піддеревом або правим піддеревом.
  3. Перемістіть піддерево до кінця потрібного піддерева. Вставте вузол у відповідне піддерево як листовий вузол.

Давайте подивимося ілюстрацію операції вставки BST.

Розглянемо наступну BST і дозволимо вставити елемент 2 у дерево.

BST - операція вставки
Фігура 1
Вставте елемент у BST
Малюнок 2

Операція вставки для BST показана вище. На рис. (1) показаний шлях, який ми проходимо, щоб вставити елемент 2 у BST. Ми також показали умови, які перевіряються на кожному вузлі. В результаті рекурсивного порівняння елемент 2 вставляється як права дочірня частина 1, як показано на рис. (2).

Пошукова операція в BST

Для пошуку, чи присутній елемент у BST, ми знову починаємо з кореня, а потім обходимо ліве чи праве піддерево залежно від того, чи є елемент, який потрібно шукати, меншим або більшим за кореневий.

Нижче наведено кроки, яких ми маємо виконувати.

  1. Порівняйте шуканий елемент із кореневим вузлом.
  2. Якщо ключ (елемент, який потрібно шукати) = root, поверніть кореневий вузол.
  3. Інакше якщо ключ
  4. Інше траверсу правого піддерева.
  5. Повторно порівнюйте елементи піддерева, поки не буде знайдено ключ або не буде досягнуто кінець дерева.

Проілюструємо пошукову операцію на прикладі. Вважайте, що нам потрібно шукати ключ = 12.

На малюнку нижче ми простежимо шлях, яким ми йшли для пошуку цього елемента.

Пошукові операції в BST

Як показано на малюнку вище, спочатку ми порівнюємо ключ із коренем. Оскільки ключ більший, ми обходимо праве піддерево. У правому піддереві ми знову порівнюємо ключ із першим вузлом у правому піддереві.

Ми виявили, що ключ менше 15. Отже, ми переходимо до лівого піддерева вузла 15. Безпосередній лівий вузол 15 - це 12, який відповідає ключу. На цьому ми зупиняємо пошук і повертаємо результат.

Видаліть елемент із BST

Коли ми видаляємо вузол з BST, є три можливості, про які йдеться нижче:

Вузол - це листовий вузол

Якщо вузол, який потрібно видалити, є листовим, то ми можемо безпосередньо видалити цей вузол, оскільки він не має дочірніх вузлів. Це показано на зображенні нижче.

Вузол - це листовий вузол

Як показано вище, вузол 12 є листовим вузлом і може бути видалений відразу.

Вузол має лише одну дитину

Коли нам потрібно видалити вузол, який має одну дочірню особу, ми копіюємо значення дочірнього елемента у вузлі, а потім видаляємо дочірню.

Вузол має лише одну дитину

На наведеній вище схемі ми хочемо видалити вузол 90, який має одну дочірню долю 50. Таким чином, ми замінюємо значення 50 на 90, а потім видаляємо вузол 90, який є дочірнім вузлом.

Вузол має двох дітей

Коли вузол, який потрібно видалити, має двох дочірніх елементів, тоді ми замінюємо вузол наступним послідовністю вузла (лівий корінь-правий) або просто сказали мінімальний вузол у правому піддереві, якщо праве піддерево вузла не порожнє. Ми замінюємо вузол цим мінімальним вузлом і видаляємо вузол.

Вузол має двох дітей

На наведеній вище схемі ми хочемо видалити вузол 45, який є кореневим вузлом BST. Ми виявили, що праве піддерево цього вузла не є порожнім. Потім ми обходимо праве піддерево і виявляємо, що вузол 50 є мінімальним вузлом тут. Тож ми замінюємо це значення замість 45, а потім видаляємо 45.

Якщо ми перевіримо дерево, то побачимо, що воно відповідає властивостям BST. Таким чином, заміна вузла була правильною.

Впровадження бінарного дерева пошуку (BST) в Java

Наступна програма на Java забезпечує демонстрацію всіх вищезазначених операцій BST, використовуючи те саме дерево, що використано на ілюстрації, як приклад.

безкоштовний клієнт ssh для Windows 10 -
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 - результат

Обхід бінарного дерева пошуку (BST) в Java

Дерево є ієрархічною структурою, тому ми не можемо проходити його лінійно, як інші структури даних, такі як масиви. Будь-який тип дерева потрібно обходити спеціальним чином, щоб усі його піддерева та вузли були відвідані принаймні один раз.

Залежно від порядку, в якому кореневий вузол, ліве піддерево та праве піддерево обходять дерево, є певні обходи, як показано нижче:

  • Обхід в обхід
  • Обхід попереднього замовлення
  • Обхід PostOrder

Усі вищеописані обходи використовують техніку, що визначає глибину, тобто дерево обходить глибину.

Дерева також використовують метод обходу по ширині. Називається підхід із використанням цієї техніки “Рівневе замовлення” обхід.

У цьому розділі ми продемонструємо кожен з обходів, використовуючи наступний BST як приклад.

Обхід BST на Java

З BST, як показано на наведеній вище схемі, обхід порядку порядку для вищезазначеного дерева має вигляд:

Обхід порядку замовлення: 10 6 12 4 8

Обхід в обхід

Підхід в обхідному порядку пройшов BST в порядку, Ліве піддерево => RootNode => Праве піддерево . Обхід в обробці забезпечує зменшувальну послідовність вузлів BST.

Алгоритм InOrder (bstTree) для обходу InOrder наведено нижче.

  1. Обхід лівого піддерева за допомогою InOrder (left_subtree)
  2. Відвідайте кореневий вузол.
  3. Обхід правого піддерева за допомогою InOrder (right_subtree)

Внутрішній обхід вищезазначеного дерева:

4 6 8 10 12

Як видно, послідовність вузлів в результаті обходу в порядку відбувається у порядку зменшення.

Обхід попереднього замовлення

При обробці попереднього замовлення спочатку відвідується корінь, а потім ліве і праве піддерево. Обхід попереднього замовлення створює копію дерева. Він також може бути використаний у деревах виразів для отримання префіксного виразу.

Алгоритм обходу PreOrder (bst_tree) наведено нижче:

  1. Відвідайте кореневий вузол
  2. Проведіть ліве піддерево за допомогою PreOrder (left_subtree).
  3. Проведіть правильне піддерево за допомогою PreOrder (right_subtree).

Наведений вище обхід попереднього замовлення для BST:

10 6 4 8 12

Обхід PostOrder

Обхід postOrder проходить BST в порядку: Ліве піддерево-> Праве піддерево-> Кореневий вузол . Обхід PostOrder використовується для видалення дерева або отримання виразу postfix у випадку дерев виразів.

Алгоритм обходу postOrder (bst_tree) такий:

  1. Проведіть ліве піддерево за допомогою postOrder (left_subtree).
  2. Проведіть правильне піддерево за допомогою postOrder (right_subtree).
  3. Відвідайте кореневий вузол

Обхід 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(); } }

Вихід:

Впровадження BST Transversal - Output

Часті запитання

Q # 1) Навіщо нам потрібне бінарне дерево пошуку?

Відповідь : Для того, як ми шукаємо елементи в лінійній структурі даних, такі як масиви, використовуючи двійкову техніку пошуку, дерево є ієрархічною структурою, нам потрібна структура, яка може бути використана для пошуку елементів у дереві.

Тут з’являється бінарне дерево пошуку, яке допомагає нам в ефективному пошуку елементів у зображенні.

Q # 2) Які властивості бінарного дерева пошуку?

Відповідь : Бінарне дерево пошуку, яке належить до категорії бінарного дерева, має такі властивості:

  • Дані, що зберігаються у двійковому дереві пошуку, є унікальними. Він не допускає повторення значень.
  • Вузли лівого піддерева менше, ніж кореневий вузол.
  • Вузли правого піддерева більші за кореневий вузол.

Запитання №3) Які програми мають двійкове дерево пошуку?

Відповідь : Ми можемо використовувати двійкові дерева пошуку для розв’язання деяких неперервних функцій у математиці. Пошук даних в ієрархічних структурах стає більш ефективним за допомогою двійкових дерев пошуку. З кожним кроком ми зменшуємо пошук наполовину піддерева.

Q # 4) Яка різниця між бінарним деревом та бінарним деревом пошуку?

Відповідь: Бінарне дерево - це ієрархічна деревоподібна структура, в якій кожен вузол, відомий як батьківський, може мати щонайбільше двох дітей. Бінарне дерево пошуку виконує всі властивості бінарного дерева, а також має свої унікальні властивості.

У двійковому дереві пошуку ліві піддерева містять вузли, менші або рівні кореневому вузлу, а праве піддерево має вузли, більші за кореневий вузол.

Q # 5) Чи унікальне дерево бінарного пошуку?

Відповідь : Бінарне дерево пошуку належить до категорії бінарного дерева. Він унікальний у тому сенсі, що не допускає повторення значень, а також усі його елементи упорядковані відповідно до конкретного порядку.

Висновок

Дерева двійкового пошуку є частиною категорії двійкового дерева і в основному використовуються для пошуку ієрархічних даних. Він також використовується для вирішення деяких математичних задач.

У цьому посібнику ми побачили реалізацію бінарного дерева пошуку. Ми також бачили різні операції, проведені на BST з їх ілюстрацією, а також досліджували обходи для BST.

=> Зверніть увагу на прості навчальні серії Java тут.

Рекомендована література

^