Структура даних бінарного дерева пошуку, пояснена на прикладах

Дерево - це структура даних, що складається з вузлів, що має такі характеристики:

  1. Кожне дерево має кореневий вузол (вгорі), що має якесь значення.
  2. Кореневий вузол має нуль або більше дочірніх вузлів.
  3. Кожен дочірній вузол має нуль або більше дочірніх вузлів тощо. Це створює піддерево в дереві. Кожен вузол має власне піддерево, яке складається з його дітей та їх дітей тощо. Це означає, що кожен вузол сам по собі може бути деревом.

Бінарне дерево пошуку (BST) додає ці дві характеристики:

  1. Кожен вузол має максимум до двох дітей.
  2. Для кожного вузла значення його лівих низхідних вузлів менше, ніж поточного вузла, а це, в свою чергу, менше правих низхідних вузлів (якщо такі є).

BST побудований на ідеї двійкового алгоритму пошуку, який дозволяє швидко шукати, вставляти та видаляти вузли. Спосіб їх налаштування означає, що в середньому кожне порівняння дозволяє операціям пропустити приблизно половину дерева, так що кожен пошук, вставка або видалення займає час, пропорційний логарифму кількості елементів, що зберігаються в дереві, O(log n).

Однак іноді може трапитися найгірший випадок, коли дерево не збалансовано, а складність часу - O(n)для всіх трьох цих функцій. Ось чому самобалансуючі дерева (AVL, червоно-чорні тощо) набагато ефективніші, ніж базові BST.

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

Основні операції на BST

  • Створити: створює порожнє дерево.
  • Вставити: вставити вузол у дерево.
  • Пошук: пошук вузла у дереві.
  • Видалити: видаляє вузол з дерева.

Створити

Спочатку створюється порожнє дерево без будь-яких вузлів. Змінна / ідентифікатор, який повинен вказувати на кореневий вузол, ініціалізується зі NULLзначенням.

Пошук

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

Вставити

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

Видалити

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

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

Складність часу для створення дерева становить O(1). Складність часу для пошуку, вставки або видалення вузла залежить від висоти дерева h, тому найгірший випадок O(h).

Попередник вузла

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

Наступник вузла

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

Особливі типи БТ

  • Купи
  • Червоно-чорне дерево
  • B-дерево
  • Splay дерево
  • N-арне дерево
  • Trie (дерево Radix)

Час роботи

Структура даних: масив

  • Найгірша продуктивність: O(log n)
  • Найкраща робота: O(1)
  • Середня продуктивність: O(log n)
  • Найгірша космічна складність: O(1)

Де nкількість вузлів у BST.

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

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

struct node { int data; struct node *leftChild; struct node *rightChild; };

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

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

struct node* search(int data){ struct node *current = root; printf("Visiting elements: "); while(current->data != data){ if(current != NULL) { printf("%d ",current->data); //go to left tree if(current->data > data){ current = current->leftChild; }//else go to right tree else { current = current->rightChild; } //not found if(current == NULL){ return NULL; } } } return current; }

Операція вставки

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

void insert(int data) { struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } }//go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } } 

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

  • To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
  • To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.

Let’s look at a couple of procedures operating on trees.

Since trees are recursively defined, it’s very common to write routines that operate on trees that are themselves recursive.

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

  • For instance, if we have a nil tree, then its height is a 0.
  • Otherwise, We’re 1 plus the maximum of the left child tree and the right child tree.

So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

Height(tree) algorithm

if tree = nil: return 0 return 1 + Max(Height(tree.left),Height(tree.right))

Here is the code in C++

int maxDepth(struct node* node) { if (node==NULL) return 0; else { int rDepth = maxDepth(node->right); int lDepth = maxDepth(node->left); if (lDepth > rDepth) { return(lDepth+1); } else { return(rDepth+1); } } } 

We could also look at calculating the size of a tree that is the number of nodes.

  • Again, if we have a nil tree, we have zero nodes.

Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

Size(tree) algorithm

if tree = nil return 0 return 1 + Size(tree.left) + Size(tree.right)

Here is the code in C++

int treeSize(struct node* node) { if (node==NULL) return 0; else return 1+(treeSize(node->left) + treeSize(node->right)); }

Relevant videos on freeCodeCamp YouTube channel

  • Binary Search Tree
  • Binary Search Tree: Traversal and Height

Following are common types of Binary Trees:

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

 18 / \ 15 30 / \ / \ 40 50 100 40

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

 18 / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9