Изменения

[[Файл:Binary_search_tree.svg.png|right|200px300px|thumb|Бинарное дерево поиска из 9 элементов]]'''Бинарное дерево поиска (англ. binary search tree, BST)''' - структура данных для работы с динамическими множествами.Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> - узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие или равные <tex>k</tex>, а в правом поддереве большие <tex>k</tex> (или в левом — строго меньшие, а в правом большие или равные).

Tree_inorderinorderTreeWalk(node Node x) if(x != null) Tree_inorderinorderTreeWalk(x.left); print(x.key); Tree_inorderinorderTreeWalk(x.right);

[[Файл:Bst search.png|thumb|250px318px|Поиск элемента 4]]Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева. Tree_searchtreeSearch(node Node x, key k) if (x == null or k == x.key) return x; if (k < x.key) return Tree_searchtreeSearch(x.left, k);

return Tree_searchtreeSearch(x.right, k);Приведенная выше функция принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.

Tree_mintreeMinimum(root Node x) while (x.left != null) x = x.left; return x;

Tree_maxtreeMaximum(root Node x) while (x.right != null) x = x.right; return x;

Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя. Tree_nexttreeNext(root Node x) if (x.right != null) return Tree_mintreeMinimum(x.right); y = x.parent; while(y != null and x == y.right) x = y; y = y.parent; return y;

Tree_prevtreePrev(root Node x) if (x.left != null) return Tree_maxtreeMaximum(x.left); y = x.parent; while(y != null and x == y.left) x = y; y = y.parent; return y;Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя. Обе операции выполняются за время <tex>O(h)</tex>.

Tree_inserttreeInsert(root Node x, root Node z) // корень дерева, вставляемый элемент root Node y = null; while (x != null) y = x; if(z.key > x.key) x = x.right;

x = x.left; z.parent = y; if(z.key > y.key) y.right = z;

y.left = z;

| [[Файл:Bst_del1.png‎|250px]]

| [[Файл:Bst_del2.png‎|250px]]

| [[Файл:Bst_del3.png‎|250px]]

| [[Файл:Bst_del4.png‎|250px]]

Tree_deletetreeDelete(root Node t, root Node z) // корень дерева, вставляемый удаляемый элемент root Node x, y; if(z.left == null or z.right == null) y = z;

y = Tree_nexttreeNext(z); if(y.left != null) x = y.left;

x = y.right; if(x != null) x.parent = y.parent; if(y.parent == null) t = x;

if(y == y.parent.left) y.parent.left = x;

y.parent.right = x; if(y != z) z.key = y.key; z.data = y.data; return y;