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

З Новим роком Посмішка. Дана стаття буде дещо відрізнятись від попередніх, так як в цій статті я буду писати про Бінарне дерево пошуку.

Що таке бінарне дерево пошуку

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

1.1

Рис 1.1 – Структура бінарного дерева

Отже, на попередній діаграмі ви можете побачити структуру бінарного дерева.

Тепер, для того щоб зрозуміти різницю між бінарним деревом і бінарним деревом пошуку розгляньте наступну діаграму:

1.2

Рис 1.2 – Структура бінарного дерева пошуку

На попередній діаграмі зображено те саме дерево, де кожна гілка містить якийсь ключ (в нашому випадку ціле число). Зверніть увагу на те, що це дерево спроектовано таким чином, що кожна гілка містить дочірні гілки з більшим або з меншим значенням ключа. Наприклад гілка, яка містить ключ 43, містить дві дочірні гілки з меншим значенням ключа – 27 (ліва гілка) та більшим значенням ключа – 47 (права гілка).

Реалізація

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

Створіть проект в Visual Studio 2010 на мові програмування C# (тип проекту Console Application).

Гілка дерева

Почнемо зі створення класу, який буде представляти конкретну гілку, і який ми назвемо Node:

public class Node
{
    public Node Parent { get; set; }
    public Int32 Key { get; set; }
    public Object Data { get; set; }
    public Node LeftNode { get; set; }
    public Node RightNode { get; set; }

    public Node(Node left, Int32 key, Node right, Node parent, Object data)
    {
        this.LeftNode = left;
        this.Key = key;
        this.RightNode = right;
        this.Parent = parent;
        this.Data = data;
    }
    public override string ToString()
    {
        return Key.ToString();
    }
}

Цей клас містить такі члени, які ідентифікують:

  • Батьківську гілку (Parent)
  • Ключ цієї гілки (Key)
  • Дані, які дана гілка зберігає (Data)
  • Ліва гілка (LeftNode)
  • Права гілка (RightNode)

Тепер, коли в нас є клас, який представляє гілку дерева, можна приступити до створення самого дерева.

Дерево

Добавте новий клас з назвою BinarySearchTree з однією приватною змінною – root:

public class BinarySearchTree
{
    private Node root;
}

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

Метод Insert (додавання гілок в дерево)

Принцип реалізації цьому методу є досить простим – потрібно перевірити чи корінь дерева вже існує, якщо ні, то добавити гілку в корінь дерева, в іншому випадку треба порівняти ключ гілки з ключем нової гілки на більшість або меншість. Якщо ключ нової гілки менший, то потрібно оперувати над лівою дочірньою гілкою даної гілки, якщо більший, то потрібно оперувати над правою.

Операція, яка описана зверху має відбуватись доти, доки вона не добереться до листка дерева (гілка, яка немає дочірніх гілок).

Це можна продемонструвати на діаграмі:

1.3

Рис 1.3 – Дерево до добавлення гілки з ключем 63

Якщо добавити гілку з ключем 63, то дерево прийме наступний вигляд:

1.4

Рис 1.4 – Дерево після добавлення гілки з ключем 63

Сам код наведено нижче:

public void Insert(Int32 key, Object value)
 {
     if (root == null)
         root = new Node(null, key, null, null, value);
     else
     {
         Node currentNode = root;
         while (currentNode != null) //Продовжувати цикл доти, доки ми не доберемся до листка дерева
         {
             if (currentNode.Key == key) //Якшо в даної гілки такий самий ключ, то додавання елементу буде просто проігнорованим
                 break;

             else if (key < currentNode.Key) //Перевірка чи ключ має менше значення ніж ключ гілки, яка знаходиться в перевірці
             {
                 if (currentNode.LeftNode == null) //Якщо дана гілка не має лівої дочірньої гілки, то потрібно її створити з новим ключем
                 {
                     currentNode.LeftNode = new Node(null, key, null, currentNode, value);
                     break;
                 }
                 else
                     currentNode = currentNode.LeftNode;

             }
             else if (key > currentNode.Key) //Перевірка чи ключ має більше значення ніж ключ гілки
             {
                 if (currentNode.RightNode == null) //Аналогічні дії, які описані зверху тільки для правої гілки
                 {
                     currentNode.RightNode = new Node(null, key, null, currentNode, value);
                     break;
                 }
                 else
                     currentNode = currentNode.RightNode;
             }
         }
     }
 }

Часова складність цього алгоритму (в ліпшому випадку) є O(log n), де n – кількість елементів. В гіршому O(n). Враховуючи цю часову складність, потрібно розуміти, що додавання елементів в дерево не є швидкою операцією, особливо якщо в дереві є багато елементів. Для прикладу, якщо дерево має 32 елементи (n = 32), то в середньому для добавлення нового елементу потрібно буде зробити 5 перевірок (log 32 = 5).

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

Метод Search (пошук гілки)

Цей метод я реалізував рекурсивно, який спочатку перевіряє чи дана гілка не є порожньою (кінець дерева), і в цьому випадку повертає null. Далі йде список ось таких перевірок:

  • Перевірка на рівність з переданим ключем (якщо ключі рівні, значить пошук завершено)
  • Перевірка чи ключ має менше значення ніж теперішня гілка та знову запуск цього самого метод рекурсивно, передавши в якості початку пошуку ліву гілку
  • Перевірка чи ключ має значення більше ніж теперішня гілка та запуск цьому методу з посиланням на праву гілку

Ось так виглядає код даного методу:

      public Node Search(Int32 key)
      {
          return Search(root, key);
      }
      private Node Search(Node node, Int32 key)
      {
          if (node == null)
              return null;
          if (key == node.Key)
              return node;
          else if (key < node.Key)
              return Search(node.LeftNode, key);
          else
              return Search(node.RightNode, key);
      }
 
Перший метод стоїть з модифікатором public (для клієнтів класу), а інший з модифікатором private (для головного методу Search).

Складність цієї операції в середньому є log n (напр. дерево має 64 гілки, то пошук буде містити 6 перевірок)

Метод Traverse (проходження по дереву)

Ну що, можна перейти до реалізації цього методу Посмішка.

Даний метод теж реалізований як рекурсивний і він просто обходить всі елементи дерева за таким принципом:

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

Тепер, гляньте код:

       public void Traverse()
       {
           Traverse(root);
       }
       private void Traverse(Node node)
       {
           if (node == null)
               return;
           Traverse(node.LeftNode);
           Console.WriteLine(node.Key);
           Traverse(node.RightNode);
       }

Метод Delete (видалення гілки)

Реалізація цього методу має бути самою складною. Нам потрібно мати змогу обробити три випадки:

1. Видалення гілки, яка не має нащадків:

1.5

Рис 1.5 – Дерево, яке має елемент (без дочірніх елементів) призначений для видалення (ключ 63)

2. Видалення гілки, яка має одну дочірню гілку

1.6

Рис 1.6 – Дерево, яке має елемент (з одним дочірнім елементом) призначений для видалення (ключ 60)

3. Гілка має дві дочірніх гілки:

1.7

Рис 1.7 – Дерево, яке має елемент (з двома дочірніми елементами) призначений для видалення (ключ 55)

Для того, щоб обробити ці три випадки нам потрібно робити відповідні дії для кожного з них

1. В цьому випадку все просто – потрібно скинути посилання батьківського елементу

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

1.8

Рис 1.8 – Дерево, яке має елемент (з одним дочірнім елементом) призначений для видалення (ключ 60)

1.9

Рис 1.9 – Дерево після видалення гілки з ключем 60

3. В даному випадку нам потрібно глянути на одну властивість дерева:

1.10

Рис 1.10 – Дерево до трансформації

1.11

Рис 1.11 – Дерево після трансформації

Якщо уважно подивитись на два попередніх зображення, то має стати ясно, що дерево можна перетворити для певних потреб. Зверніть увагу на те, що гілка з ключем 30 на першому зображені мала дві дочірніх гілки, а на другому жодної. Тобто, зробивши це перетворення ми можемо видалити потрібну нам гілку (в даному випадку з ключем 30) як гілку, яка не має дочірніх гілок.

Тепер давайте реалізуємо видалення Посмішка.

Спочатку добавте такий допоміжний метод, який дозволить знайти гілку з найменшим значенням:

private Node FindMin(Node node) //Метод, який шукає найменшу підгілку
{
    if (node.LeftNode != null) //Якщо ліва підгілка існує, то запустити цей метод рекурсивно
        return FindMin(node.LeftNode);
    else
        return node; //Гілка знайдена
}
 
Тепер добавте два методи Remove з різними перевантаженнями, які приймають або гілку або ключ:
 
public void Remove(Int32 key)
{
    var nodeToRemove = Search(key); //Пошук гілки для видалення
    Remove(nodeToRemove);
}
private void Remove(Node nodeToRemove)
{
    if (nodeToRemove != null)
    {
        var nodeParent = nodeToRemove.Parent;
        if (nodeToRemove.LeftNode == null && nodeToRemove.RightNode == null) //Випадок коли гілка не має дочірніх гілок
        {
            if (nodeToRemove.Key > nodeParent.Key) //Якщо ключ батьківсьої гілки менший за ключ гілки для видалення, то це значить, що гілка для  видалення знаходиться справа
                nodeParent.RightNode = null;
            else //Гілка для видалення знаходиться зліва відносно батьківсьої гілки
                nodeParent.LeftNode = null;
        }
        else if (nodeToRemove.LeftNode != null && nodeToRemove.RightNode != null) //Випадок коли гілка має дві дочірніх гілки
        {
            var minNode = FindMin(nodeToRemove.RightNode); //Пошук гілки з мінімальним ключем у правій підгілці гілки для видалення
            nodeToRemove.Key = minNode.Key;     //Заповнення даних гілки для видалення даними з правої мінімальної підгілки
            nodeToRemove.Data = minNode.Data;
            Remove(minNode); //Запуск методу видалення для знайденої мінімальної підгілки
        }
        else if (nodeToRemove.LeftNode != null || nodeToRemove.RightNode != null) //Випадок коли гілка має одну дочірню гілку
        {
            var nodeChild = nodeToRemove.LeftNode == null ? nodeToRemove.RightNode : nodeToRemove.LeftNode; //Якщо ліва гілка порожня то дістаємо праву гілку, в іншому випадку ліву
            if (nodeToRemove.Key > nodeParent.Key) //Гілка для видалення знаходиться справа відносно батьківсьої гілки
                nodeParent.RightNode = nodeChild; //Батько гілки для видалення має нову підгілку
            else //Гілка для видалення знаходиться зліва відносно батьківсьої гілки
                nodeParent.LeftNode = nodeChild;
            nodeChild.Parent = nodeParent; //В гілки з'явився новий батьківський елемент
        }
    }
}
 
Метод, який приймає ключ, користується методом Search для пошуку елементу, після того, як він знайшов гілку для видалення, він викликає метод Remove передаючи цю гілку. Код має достатньо коментарів, які описують що робить та чи інша операція.

Рекомендую звернути увагу на те, що у випадку коли гілка для видалення має два дочірніх елементи, запускається метод FindMin, в який передається права гілка (з більшим значенням ключа) елементу який потрібно видалити.

Складність даного методу в середньому має log n, де n – кількість елементів в дереві.

Використання дерева

Вітаю, ви реалізували просте дерево бінарного пошуку! Тепер давайте його від тестуємо Обличчя, яке підморгує.

Відкрийте файл Program.cs та в методі Main створіть екземпляр класу BinarySearchTree:

 
static void Main(string[] args)
{
    BinarySearchTree tree = new BinarySearchTree();
}
 
Тепер наповніть дерево такими елементами: (30, 26,35,22,31,24,15,14,23,25):
 
tree.Insert(30, null);
tree.Insert(26, null);
tree.Insert(35, null);
tree.Insert(22, null);
tree.Insert(31, null);
tree.Insert(24, null);
tree.Insert(15, null);
tree.Insert(14, null);
tree.Insert(23, null);
tree.Insert(25, null);
 
Це дерево буде мати ось такий вигляд:

1.12

Рис 1.12 – Наповнене дерево

Тепер застосуйте метод Search для пошуку гілки з ключем 24:

 

var searchResult = tree.Search(24);
 
В режимі відлагодження можете переглянути результат пошуку:

clip_image023

Рис 1.13 – Знайдений елемент з ключем 24

Запустіть метод Traverse:

 

tree.Traverse();
 
Перегляньте значення, які повиводились на екран:

clip_image025

Рис 1.14 – Результати методу Traverse

Зверніть увагу на те, що значення виводяться у відсортованому порядку, тобто ми можемо використовувати це дерево для сортування елементів.

Тепер запустіть метод Remove з параметром 24 і після цього знову запустіть метод Search:

 

tree.Remove(24);
searchResult = tree.Search(24);

clip_image027

Рис 1.15 – Результат методу Search після виконання методу Remove

Підсумок

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

  1. Insert
  2. Delete
  3. Traverse
  4. Search

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

 

1 BinarySearchTree<ClassName> tree = new BinarySearchTree<ClassName>();

З Новим роком вас, і всього найкращого Smile.

 

Скачати код

Advertisements

, , ,

  1. #1 by Dmitriy on March 11, 2012 - 01:42

    код хороший, але твої коменти просто ахтунг

  2. #2 by Serhiy Shumakov on March 11, 2012 - 09:24

    Я думав що навпаки буде легше розбиратись))

  3. #3 by Oleksandr on June 12, 2019 - 13:21

    private void Remove(Node nodeToRemove)
    {
    if (nodeToRemove.Key > nodeParent.Key) //Якщо ключ батьківсьої гілки менший за ключ гілки для видалення, то це значить, що гілка для видалення знаходиться справа

    краще замінити на:

    if (nodeParent->RightNode == nodeToRemove)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: