Двоичное дерево в структуре данных (ПРИМЕР)
Сара Чен
Что такое бинарное дерево?
Слово «бинарный» означает «два». В древовидной структуре данных «двоичное дерево» означает дерево, в котором каждый узел может иметь максимум два дочерних узла (левый и правый узлы). Это простое двоичное дерево.
Однако есть еще одно двоичное дерево, которое используется чаще всего и имеет несколько вариантов использования. Это называется двоичным деревом поиска (BST). Это дерево может сделать алгоритм поиска намного быстрее, с точностью до log(n) временной сложности. В структуре данных n означает количество узлов в двоичном дереве.
Каковы различия между двоичным деревом и двоичным деревом поиска?
Разница между BST и обычным двоичным деревом заключается в том, что левый узел BST имеет меньшее значение, чем корневой узел, а правый узел имеет большее значение, чем корневой узел. Таким образом, левое поддерево всегда будет содержать меньшее значение, чем корень, а правое поддерево всегда будет содержать большее значение, чем корень.
Пример двоичных деревьев поиска
Давайте рассмотрим следующий пример для демонстрации концепций двоичного дерева поиска.
Здесь вы можете все узлы следовать заданной дисциплине. Существует формула максимального количества узлов в дереве двоичного поиска. Если мы посмотрим на приведенное выше дерево, мы увидим, что у каждого узла есть два дочерних узла, за исключением всех конечных узлов. А высота (h) данного двоичного дерева равна 4. Формула: 2h -1. Итак, получается 15.
Приведенное выше изображение не является полным двоичным деревом или сбалансированным двоичным деревом, оно называется полным двоичным деревом или сбалансированным двоичным деревом. Существует еще одна структура данных, называемая AVL (еще один тип двоичного дерева), которая оптимизирует высоту двоичного дерева и ускоряет поиск BST, как показано на рис. 3.
Попробуйте вычислить упорядоченный обход приведенного выше двоичного дерева. Вы обнаружите, что это даст неубывающий отсортированный массив, а алгоритмы обхода будут такими же, как и у двоичного дерева.
Типы двоичного дерева
Вот некоторые важные типы двоичного дерева:
- Полное бинарное дерево: Каждый узел может иметь 0 или 2 дочерних узла в этом двоичном дереве. В этом типе двоичного дерева не допускается наличие только одного дочернего узла. Таким образом, за исключением листового узла, все узлы будут иметь двух дочерних узлов.
- Полное бинарное дерево: Каждый узел может иметь 0 или 2 узла. Это похоже на полное двоичное дерево, но все листовые элементы наклонены к левому поддереву, тогда как в полном двоичном дереве узел может находиться как в правом, так и в левом поддереве.
- Идеальное бинарное дерево: Все узлы должны иметь 0 или 2 узла, а все конечные узлы должны находиться на одном уровне или высоте. Приведенный выше пример полной двоичной древовидной структуры не является идеальным двоичным деревом, поскольку узлы 6 и узлы 1,2,3 не имеют одинаковой высоты. Но пример полного двоичного дерева — идеальное двоичное дерево.
- Вырожденное двоичное дерево: Каждый узел может иметь только одного дочернего узла. Все операции, такие как поиск, вставка и удаление, занимают время O(N).
- Сбалансированное бинарное дерево: Вот это бинарное дерево, разница высот левого и правого поддерева не превышает 1. Итак, при добавлении или удалении узла нам нужно снова сбалансировать высоту дерева. Этот тип самобалансированного двоичного дерева называется AVL дерево.
Существует три основных операции BST. Они подробно обсуждаются ниже.
Реализация двоичного дерева в C и C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int value;
struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
tempNode->value = val;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
struct Node *successor(struct Node *node)
{
struct Node *present = node;
// going to the left most node
while (present != NULL && present->left != NULL)
{
present = present->left;
}
return present;
}
struct Node *insert(struct Node *node, int value)
{
if (node == NULL)
{
return getEmptynode(value);
}
if (value < node->value)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
int searchInBST(struct Node *node, int value)
{
struct Node *current = node;
while (current->value != value)
{
if (current->value > value)
{
current = current->left;
}
else
{
current = current->right;
}
if (current == NULL)
{
return 0;
}
}
return 1;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
struct Node *deleteNode(struct Node *node, int value)
{
if (node == NULL)
{
return node;
}
if (value < node->value)
{
node->left = deleteNode(node->left, value);
}
else if (value > node->value)
{
node->right = deleteNode(node->right, value);
}
else
{
if (node->left == NULL)
{
struct Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)
{
struct Node *temp = node->left;
free(node);
return temp;
}
struct Node *temp = successor(node->right);
node->value = temp->value;
node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
{
struct Node *root = NULL;
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 13);
root = insert(root, 15);
cout << "InOrder Traversal after inserting all nodes: " << endl;
inorder(root);
root = insert(root, -10);
cout << "\nInOrder Traversal after inserting -10 : " << endl;
inorder(root);
cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
root = deleteNode(root,8);
cout<<"After deleting node 8, inorder traversal: "<<endl;
inorder(root);
root = deleteNode(root,-10);
cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
inorder(root);
}
Вывод:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
Реализация двоичного дерева в Python
class Node:
def __init__(self,value):
self.left = None
self.right = None
self.value = value
def insert(root,value):
if root == None:
return Node(value)
if value< root.value:
root.left = insert(root.left,value)
else:
root.right = insert(root.right,value)
return root
def searchInBST(root,value):
current = root
while current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
if current == None:
return "Not found"
return "Found"
def inorder(root):
if root != None:
inorder(root.left)
print(root.value,end=" ")
inorder(root.right)
def successor(root):
present = root
while present != None and present.left != None:
present = present.left
return present
def deleteNode(root,value):
if root == None:
return root
if value < root.value:
root.left = deleteNode(root.left, value)
elif value>root.value:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
root = None
return temp
elif root.right == None:
temp = root.left
root = None
return temp
temp = successor(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
root = Node(8)
root = insert(root, 4)
root = insert(root, 12)
root = insert(root, 2)
root = insert(root, 6)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 1)
root = insert(root, 3)
root = insert(root, 5)
root = insert(root, 7)
root = insert(root, 9)
root = insert(root, 11)
root = insert(root, 13)
root = insert(root, 15)
print("InOrder Traversal after inserting all nodes: ")
inorder(root)
root = insert(root, -10)
print("\nInOrder Traversal after inserting -10 : ")
inorder(root)
print("\nSearching -5 in the BST: ",searchInBST(root, -5))
print("Searching -5 in the BST: ",searchInBST(root, -10))
root = deleteNode(root,8)
print("After deleting node 8, inorder traversal:")
inorder(root)
root = deleteNode(root,-10)
print("\nAfter deleting node -10, inorder traversal:")
inorder(root)
Вывод:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
Применение двоичного дерева
Вот некоторые распространенные применения двоичного дерева:
- Организация данных узла в отсортированном порядке
- Используется в объектах узлов карты и набора в библиотеках языков программирования.
- Поиск элементов в структурах данных
» Узнайте наш следующий урок о Комбинированный алгоритм
