Деревья двоичного поиска: объяснение BST с примерами

Что такое двоичное дерево поиска?

Дерево - это структура данных, состоящая из узлов, которая имеет следующие характеристики:

  1. Каждое дерево имеет наверху корневой узел (также известный как родительский узел), содержащий некоторое значение (может быть любым типом данных).
  2. У корневого узла ноль или более дочерних узлов.
  3. Каждый дочерний узел имеет ноль или более дочерних узлов и т. Д. Это создает поддерево в дереве. Каждый узел имеет собственное поддерево, состоящее из его дочерних и их дочерних узлов и т. Д. Это означает, что каждый узел сам по себе может быть деревом.

Бинарное дерево поиска (BST) добавляет эти две характеристики:

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

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

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

Основные операции на BST

  • Создать: создает пустое дерево.
  • Вставить: вставить узел в дерево.
  • Поиск: поиск узла в дереве.
  • Удалить: удаляет узел из дерева.
  • Inorder: обход дерева по порядку.
  • Preorder: предварительный заказ обхода дерева.
  • Postorder: обход дерева после заказа.

Создайте

Первоначально создается пустое дерево без узлов. Переменная / идентификатор, который должен указывать на корневой узел, инициализируется   NULL  значением.

Поиск

Вы всегда начинаете поиск в дереве с корневого узла и спускаетесь оттуда. Вы сравниваете данные в каждом узле с тем, который ищете. Если сравниваемый узел не совпадает, вы переходите либо к правому, либо к левому дочернему элементу, что зависит от результата следующего сравнения: если узел, который вы ищете, ниже, чем тот, с которым вы его сравнивали, вы переходите к левому ребенку, иначе (если он больше) вы переходите к правому ребенку. Зачем? Поскольку BST структурирован (согласно его определению), правый дочерний элемент всегда больше, чем родительский, а левый дочерний элемент всегда меньше.

Поиск в ширину (BFS)

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

Поиск в глубину (DFS)

При подходе поиска в глубину мы начинаем с корневого узла и спускаемся по одной ветви. Если желаемый узел найден вдоль этой ветви - отлично, но если нет, продолжайте движение вверх и ищите непосещенные узлы. Этот тип поиска также имеет большую нотацию O (n).

Вставить

Это очень похоже на функцию поиска. Вы снова начинаете с корня дерева и рекурсивно спускаетесь вниз, ища подходящее место для вставки нашего нового узла, точно так же, как описано в функции поиска. Если узел с таким же значением уже есть в дереве, вы можете либо вставить дубликат, либо нет. Некоторые деревья допускают дублирование, некоторые - нет. Это зависит от конкретной реализации.

Удаление

Есть 3 случая, когда вы пытаетесь удалить узел. Если это так,

  1. Без поддерева (без дочерних): это самый простой. Вы можете просто удалить узел без каких-либо дополнительных действий.
  2. Одно поддерево (один дочерний элемент): вы должны убедиться, что после удаления узла его дочерний элемент подключен к родительскому элементу удаленного узла.
  3. Два поддерева (два дочерних дерева): вам нужно найти и заменить узел, который вы хотите удалить, его преемником в порядке (крайний левый узел в правом поддереве).

Временная сложность создания дерева составляет   O(1). Сложность по времени для поиска, вставки или удаления узла зависит от высоты дерева   h, поэтому худший случай - это   O(h)  случай наклонных деревьев.

Предшественник узла

Предшественников можно описать как узел, который будет стоять прямо перед узлом, на котором вы сейчас находитесь. Чтобы найти предшественника текущего узла, посмотрите на самый правый / самый большой листовой узел в левом поддереве.

Преемник узла

Наследников можно охарактеризовать как узел, который будет идти сразу после текущего узла. Чтобы найти преемника текущего узла, посмотрите на самый левый / наименьший листовой узел в правом поддереве.

Особые виды БТ

  • Куча
  • Красно-черное дерево
  • B-дерево
  • Splay tree
  • N-арное дерево
  • Trie (Радиксное дерево)

Время выполнения

Структура данных: BST

  • Наихудший результат:  O(n)
  • Лучшая производительность:  O(1)
  • Средняя производительность:  O(log n)
  • Сложность пространства в наихудшем случае:  O(1)

Где   n  количество узлов в BST. В худшем случае - O (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; } } } } } 

Delete Operation

void deleteNode(struct node* root, int data){ if (root == NULL) root=tempnode; if (data key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if (root->left == NULL) { struct node *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct node *temp = root->left; free(root); return temp; } struct node* temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } 

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

Traversal

There are 3 kinds of traversals that are done typically over a binary search tree. All these traversals have a somewhat common way of going over the nodes of the tree.

In-order

This traversal first goes over the left subtree of the root node, then accesses the current node, followed by the right subtree of the current node. The code represents the base case too, which says that an empty tree is also a binary search tree.

void inOrder(struct node* root) { // Base case if (root == null) { return; } // Travel the left sub-tree first. inOrder(root.left); // Print the current node value printf("%d ", root.data); // Travel the right sub-tree next. inOrder(root.right); } 

Pre-order

This traversal first accesses the current node value, then traverses the left and right sub-trees respectively.

void preOrder(struct node* root) { if (root == null) { return; } // Print the current node value printf("%d ", root.data); // Travel the left sub-tree first. preOrder(root.left); // Travel the right sub-tree next. preOrder(root.right); } 

Post-order

This traversal puts the root value at last, and goes over the left and right sub-trees first. The relative order of the left and right sub-trees remain the same. Only the position of the root changes in all the above mentioned traversals.

void postOrder(struct node* root) { if (root == null) { return; } // Travel the left sub-tree first. postOrder(root.left); // Travel the right sub-tree next. postOrder(root.right); // Print the current node value printf("%d ", root.data); } 

Relevant videos on freeCodeCamp YouTube channel

And 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 

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

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

Augmenting a BST

Sometimes we need to store some additional information with the traditional data structures to make our tasks easier. For example, consider a scenario where you are supposed to find the ith smallest number in a set. You can use brute force here but we can reduce the complexity of the problem to O(lg n) by augmenting a red-black or any self-balancing tree (where n is the number of elements in the set). We can also compute rank of any element in O(lg n) time. Let us consider a case where we are augmenting a red-black tree to store the additional information needed. Besides the usual attributes, we can store number of internal nodes in the subtree rooted at x(size of the subtree rooted at x including the node itself). Let x be any arbitrary node of a tree.

x.size = x.left.size + x.right.size + 1

While augmenting the tree, we should keep in mind, that we should be able to maintain the augmented information as well as do other operations like insertion, deletion, updating in O(lg n) time.

Since, we know that the value of x.left.size will give us the number of nodes which proceed x in the order traversal of the tree. Thus, x.left.size + 1 is the rank of x within the subtree rooted at x.