Наивное дерево поиска - История изменений

Algocourselecturenotes: /* Удаление */

2020-05-24T21:58:40Z

‎Удаление

Algocourselecturenotes: /* Асимптотическая сложность */

2020-05-24T21:57:20Z

‎Асимптотическая сложность

Algocourselecturenotes: /* Операции над деревом */

2020-05-24T21:56:50Z

‎Операции над деревом

Algocourselecturenotes в 21:56, 24 мая 2020

2020-05-24T21:56:05Z

Algocourselecturenotes: Новая страница: «==Определение и свойства== '''Двоичное дерево поиска''' (англ. - ''Binary Search tree - BST'') - структура д…»

2020-05-24T19:39:02Z

Новая страница: «==Определение и свойства== '''Двоичное дерево поиска''' (англ. - ''Binary Search tree - BST'') - структура д…»

Новая страница

==Определение и свойства==
'''Двоичное дерево поиска''' (англ. - ''Binary Search tree - BST'') - структура данных двоичное дерево, для любого узла которого выполняются следующие свойства:
# Оба узла поддерева являются двоичными деревьями поиска;
# Все значения ключей левого поддерева меньше ключа узла;
# Все значения ключей правого поддерева больше ключа узла.
[[Файл:BST.png|200 px|right|thumb|Двоичное дерево поиска]]
==Операции над деревом==
===Поиск===
====Алгоритм====
Поиск узла по заданному ключу можно осуществлять рекурсивно, начиная из вершины.
# Если узел отсутствует, возвращаем нулевой указатель.
# Если значение в узле равно ключу, возвращаем указатель на узел.
# Если значение в узле больше ключа, запускаем поиск по ключу в левом поддереве.
# Если значение в узле меньше ключа, запускаем поиск по ключу в правом поддереве.
====Реализация на языке C====
node_t* find (node_t* head, elem_t key) { 
&emsp;'''if''' (!head) 
&emsp;&emsp;'''return''' ''NULL''; 
&emsp;if (head->data == key) 
&emsp;&emsp;'''return''' head; 
&emsp;'''if''' (head->data > key) 
&emsp;&emsp;'''return''' find(head->left, key); 
&emsp;'''if''' (head->data < key) 
&emsp;&emsp;'''return''' find(head->right, key); 
}
===Вставка===
====Алгоритм====
Вставку ключа, как и поиск, будем осуществлять рекурсивно, начиная из вершины.
# Если узел пустой, вставляем на его место новый узел с ключом.
# Если ключ равен значению в узле, возвращаемся и ничего не добавляем.
# Если ключ меньше значения в узле, рекурсивно вызываем вставку в левом поддереве.
# Если ключ больше значения в узле, рекурсивно вызываем вставку в правом поддереве.
====Реализация на языке C====
void insert (node_t* head, T key) { 
&emsp; '''if''' (head->data == key) 
&emsp;&emsp; '''return'''; 
&emsp; '''if''' (head->data > key) { 
&emsp;&emsp; '''if''' (head->left == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->left = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->left, key); 
&emsp; } 
&emsp; '''if''' (head->data < key) { 
&emsp;&emsp; '''if''' (head->right == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->right = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->right, key); 
&emsp; } 
}
===Удаление===
====Алгоритм====
Удаление вершины по ключу будем также осуществлять рекурсивно, начиная из вершины.
# Если вершина пуста, возвращаемся.
# Если вершина пуста
#
#

@@ Строка 62: / Строка 62: @@
 ===Удаление===
 ====Алгоритм====
 Удаление вершины по ключу будем также осуществлять рекурсивно, начиная из вершины.
 # Если вершина пуста, возвращаемся.
@@ Строка 70: / Строка 71: @@
 ## Один из детей является пустым. В таком случае удаляем вершину, присоединяя ребёнка к родителю удалённого узла.
 ## Оба ребёнка присутствуют. В таком случае находим элемент u, следующий за удаляемым (для этого, начиная с правого ребёнка удаляемого, совершаем проход влево), и помещаем его значение в удаляемый элемент, после чего удаляем элемент u.
 ==Асимптотическая сложность операций==

@@ Строка 72: / Строка 72: @@
 [[Файл:BST.png|200 px|right|thumb|Удаление элемента с двумя детьми]]
-==Асимптотическая сложность==
+==Асимптотическая сложность операций==
 Асимптотическая сложность операций поиска, вставки и удаления составляет O(h), где h - высота дерева.
 Отметим при этом, что в худшем случае возможно вырождение дерева в список (например, при последовательном добавлении элементов отсортированного массива), в связи с чем возникает потребность в балансировке дерева, осуществляемой в различных видах деревьев поиска (Декартово дерево, АВЛ-дерево, Splay-дерево, Красно-чёрное дерево, B-дерево).

@@ Строка 24: / Строка 24: @@
 &emsp;&emsp;'''return''' find(head->right, key);<br>
+}
 ===Вставка===
 ====Алгоритм====
@@ Строка 54: / Строка 57: @@
 &emsp; }<br>
+}
 ===Удаление===
 ====Алгоритм====
@@ Строка 65: / Строка 71: @@
 ## Оба ребёнка присутствуют. В таком случае находим элемент u, следующий за удаляемым (для этого, начиная с правого ребёнка удаляемого, совершаем проход влево), и помещаем его значение в удаляемый элемент, после чего удаляем элемент u.
 [[Файл:BST.png|200 px|right|thumb|Удаление элемента с двумя детьми]]
 ==Асимптотическая сложность==
 Асимптотическая сложность операций поиска, вставки и удаления составляет O(h), где h - высота дерева.
 Отметим при этом, что в худшем случае возможно вырождение дерева в список (например, при последовательном добавлении элементов отсортированного массива), в связи с чем возникает потребность в балансировке дерева, осуществляемой в различных видах деревьев поиска (Декартово дерево, АВЛ-дерево, Splay-дерево, Красно-чёрное дерево, B-дерево).

@@ Строка 58: / Строка 58: @@
 Удаление вершины по ключу будем также осуществлять рекурсивно, начиная из вершины.
 # Если вершина пуста, возвращаемся.
-# Если вершина пуста
+# Если значение в вершине больше ключа, вызываем удаление для левого поддерева.
+# Если значение в вершине меньше ключа, вызываем удаление для правого поддерева.
+# Если значение в вершине равно ключу, возможны следующие три случая: