Бинарные деревья
Бинарные деревья
Всякое непустое двоичное T-дерево разбивается на 3 части: корень, левое и правое поддеревья. Отсюда можно дать следующее рекурсивное определение двоичного дерева:
пустое дерево – двоичное дерево;
вершина с левым и правым двоичными поддеревьями – двоичное дерево.
Бинарные деревья
PTree = ^TTree;
TTree = record
Item: T; {элемент дерева}
Left, Right: PTree; {указатели на поддеревья}
end;
Бинарные деревья
Двоичное T-дерево упорядочено, если для любой вершины X справедливо свойство:
все элементы, хранимые в левом поддереве, меньше элемента, хранимого в X,
а все элементы, хранимые в правом поддереве, больше элемента, хранимого в X.
Бинарные деревья: Поиск
function Exist(Item: T; Tree: PTree): Boolean;
begin
if Tree=nil then
begin
Exist := False;
Exit
end;
Поиск
if Tree^.Item=Item
then Exist := True
else if Tree^.Item>Item
then Exist := Exist(Item, Tree^.Left)
else Exist := Exist(Item, Tree^.Right);
end;
Бинарные деревья:добавление
procedure Add(Item: T; Tree: PTree); Var NewNode: PTree;
begin {поиск вершины}
while ((Item>Tree^.Item)and(Tree^.Right<>nil))or ((Item
(Tree^.Left<>nil)) do
if Item>Tree^.Item
then Tree := Tree^.Right
else Tree := Tree^.Left;
Бинарные деревья:добавление
{создание и добавление новой вершины}
NewNode := New (PTree); NewNode^.Item := Item;
NewNode^.Left := nil;
NewNode^.Right := nil;
If Item>Tree^.Item
then Tree^.Right := NewNode
else Tree^.Left := NewNode;
end;
Бинарные деревья: описание класса Tree
public class Tree {
/ / Определение класса узла дерева
public static class Node {
public Object item; // содержимое узла
public Node left = null; // указатель на левое поддерево
public Node right = null; //указатель на правое
//поддерево
/ / Конструкторы узла дерева:
/ / конструктор листа
public Node(Object item) {
this.item = item;
}
Бинарные деревья
// Конструктор промежуточного узла
public Node (Object item, Node left, Node right) {
this.item = item;
this.left = left;
this.right = right;
}
}
Node root = null; // корень дерева
}
Бинарные деревья
Рекурсивную природу дерева, отраженную в его определении, можно выразить
более явно и в описании класса, если в описании ссылок на поддеревья
вместо класса Node использовать описатель Tree.
Бинарные деревья
Высота бинарного
дерева может быть выражена следующей формулой:
Бинарные деревья
public class Tree {
private Object item;
private Tree left = null;
private Tree right = null;
public int height () {
int hi = (left == null ? 0 : left.height ( ) );
int hr = (right == null ? 0 : right.height());
return Math.max(hi, hr) + 1 ;
}
}
Бинарные деревья
public int height ( ) {
return height(root);
}
private int height(Node n) {
if (n == null) {
return 0;
}
else {
return Math.max(height(n.left), height(n.right)) + 1;
}
}
Бинарные деревья (создание/вставка)
Алгоритм:
Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), nil, nil) и остановиться.
Иначе сравнить K с ключом корневого узла X.
- Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.
- Если K
Бинарные деревья (создание/вставка)
class Tree {
public Tree left; // левое и правое поддеревья и ключ
public Tree right;
public int key;
public Tree (int k) { // конструктор с //инициализацией ключа
key = k;
}
Бинарные деревья (создание/вставка)
// insert (добавление нового поддерева (ключа))
public void insert( Tree aTree) {
if ( aTree.key < key )
if ( left != null ) left.insert( aTree );
else left = aTree;
else if ( right != null ) right.insert( aTree );
else right = aTree;
}
Бинарные деревья ( вставка в корень)
Бинарные деревья (удаление)
Алгоритм:
Если дерево T пусто, остановиться
Иначе сравнить K с ключом X корневого узла n.
- Если K>X, рекурсивно удалить K из правого поддерева Т.
- Если K
Бинарные деревья (удаление)
Если K=X, то необходимо рассмотреть три случая.
- Если узел – лист, обнуляем ссылку на него у родительского узла.
- Если у узла один потомок, то он и заменяет своего родителя
Бинарные деревья (удаление)
Если оба поддерева присутствуют, то
- найдём узел m, являющийся самым левым узлом правого поддерева;
- скопируем значения полей (key, value) узла m в соответствующие поля узла n.
- у родителя узла m заменим ссылку на узел m ссылкой на правого потомка m (который, в принципе, может быть равен nil).
- освободим память, занимаемую узлом m (на него теперь никто не указывает, а его данные были перенесены в узел n).
Бинарные деревья (удаление)
Деревья оптимального поиска
Довольно часто встречаются ситуации, когда есть информация о вероятностях обращения к отдельным ключам.
Обычно для таких ситуаций характерно «постоянство» ключей, т.е. в дерево поиска не включаются новые ключи и не исключаются старые, структура дерева остается неизменной.
сканер транслятора
электронные словари
системы распознавания текста и тп
Деревья оптимального поиска
Предположим, что в дереве поиска вероятность обращения к вершине i равна pi
Σ pi = 1, i=1,…,n
Требуется так организовать дерево поиска, чтобы общее число шагов поиска, подсчитанное для достаточно большого числа обращений, было минимальным.
Деревья оптимального поиска
Тогда (внутренняя) взвешенная длина пути представляет собой сумму всех путей от корня к каждой из вершин, умноженных на вероятность обращения к этой вершине:
p= Σ pi *hi, i=1,…,n
где hi — уровень вершины i
Конечная цель - минимизировать при заданном распределении вероятностей взвешенную длину пути.
Деревья оптимального поиска
p1 = 1/7, p2 = 2/7 и р3 = 4/7
Взвешенные длины путей деревьев:
Р(a)= 11/7, Р(b)=12/7, Р(с) = 12/7, Р(d) = 15/7
Р(е) =17/7
Деревья оптимального поиска
Деревья оптимального поиска
Сформулируем задачу следующим образом. Даны 2n + 1 вероятностей p1,p2, ,рп и q0,q1,...,qn, где
pi — вероятность того, что аргументом поиска является Ki
qi — вероятность того, что аргумент поиска лежит между Ki и Ki+1.
( q0 представляет собой вероятность того, что аргумент поиска меньше, чем К1, a qn — вероятность того, что аргумент поиска больше, чем Кп.) Таким образом,
p1+p2… +.. рп + q0+ q1 +... + qn = 1
Деревья оптимального поиска
A = {a1, a2,…an} – множество элементов, ключи которых упорядочены – K1< K2 <…< Kn
B = {b0, b1, ...bn} – множество элементов, ключи Х которых находятся в интервале Ki < X < Ki+1
для b0: X< K1, для bn: X > Kn
Дерево бинарного поиска с n+1 листьями,
представляющими элементы множества B,
называется расширенным деревом бинарного
поиска
Деревья оптимального поиска
нужно найти бинарное дерево, минимизирующее ожидаемое количество сравнений при поиске, а именно
Деревья оптимального поиска
Например, ожидаемое количество сравнений для дерева
равно 2q0+ 2p1+3q1+3p2 +3q2+р3+q3
Деревья оптимального поиска
это значение называется ценой дерева,
а дерево с минимальной ценой — оптимальным. При таком определении требование, чтобы сумма всех р и q была равна 1, излишне —
мы можем искать дерево с минимальной ценой с любой данной последовательностью весов (p1,..., рn; q0, …, qn)
Деревья оптимального поиска
p1=0,2, p2= 0,2, p3= 0,1,p4=0,1
q0=0,1, q1=0,1, q2=0,05, q3=0,05, q4=0,1
стоимость дерева = 2,05 стоимость дерева = 2,4
Деревья оптимального поиска
Оптимальные деревья обладают одним важным свойством, которое помогает их обнаруживать: все их поддеревья тоже оптимальны;
любое улучшение поддерева должно приводить к улучшению дерева в целом
(схема метода динамического программирования)
Деревья оптимального поиска
Пусть c(i,j) — цена оптимального поддерева T(i,j) с весами (pi+1,...,pj, qi,…,qj)
и пусть
w(i,j) = pi+1 + … + pj +qi+ … qj — сумма этих весов (0<=i<=j<=n)
Поскольку минимально возможная цена дерева с корнем (k) равна
w(i,j) + c(i, k-1) + c(k,j),
получим
Деревья оптимального поиска
Через R(i,j) при i < j обозначим множество всех k, для которых достигается этот минимум это множество определяет корни оптимальных поддеревьев.
Деревья оптимального поиска
Пусть T(i,j) для 0<=i
для {qi,pi+1,qi+1,…pj,qj}
Пусть r(i,j) корень T(i,j)
T(i,i) будет дерево состоящее из листа bi и
c(i,i) = 0, w(i,j) = qi
цена: w(i,j) + c(i, k-1) + c(k,j),
Деревья оптимального поиска
Алгоритм поиска оптимальных бинарных деревьев поиска).
Даны 2n+1 неотрицательных веса (p1,... ,рп; q0,... qn). Алгоритм строит бинарные деревья t(i,j), имеющие минимальную цену для весов (pi+1,. ..,pj, qi,..., qj). Вычисляются три массива, а именно
c[i,j], 0<=i<=j<=n, цена t(i,j),
r[i,j], 0<=i
w[i,j], 0 <= i <= j <= n, общий вес t(i,j).
Деревья оптимального поиска
Результаты работы алгоритма определяются массивом r:
при i = j t(i,j) пуст;
в противном случае левое поддерево —
t(i, r[i,j]-1),
а правое поддерево — t(r[i,j], j).
Деревья оптимального поиска
Алгоритм Гильберта-Мура
Инициализация:даны p1,p2,..,pn и q0,q1,…qn. Для i=0,1,2,…n положить wij=qi, cii=0, rii=bi
Для l= 1,2,…n выполнить шаг 3
Для i=0,1,2,…n-l выполнить шаг 4
Положить j=i+l, wij=wij-1+pi+qj
Пусть m – значение k (i
Положить cij=wij + cim-1 +cmj; rij= am
Деревья оптимального поиска
Вычислив r(i,j) строим дерево T(0,n)
r(0,n)- корень дерева, если r(0,n)=ak, то левый сын - r(0,к-1), а правый r(к,n)
Если am=rij, то у am левый сын - r(i,m-1), а правый - r(m,j),
пример
Деревья оптимального поиска
С помощью уравнений можно вычислить c(i,j) для j —i= 1,2,..., n;
имеется примерно 1/2n2 таких значений, а операция минимизации выполняется примерно для 1/6 n3 значений k.
те можно определить оптимальное дерево за O(n3) единиц времени с использованием О(п2) ячеек памяти.
частоты баланс оптим
АВЛ- деревья
Г.М.Адельсон -Вельский и Е.М.Ландис (1962).
АВЛ-деревья или сбалансированные деревья.
Высотой поддерева будем считать максимальную длину цепи y[1]..y[n] его вершин такую, что y[i+1] – сын y[i] для всех i.
Высота пустого дерева равна 0. Высота дерева из одного корня – единице.
АВЛ- деревья
Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более, чем на 1.
АВЛ- деревья
Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1.
Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.
АВЛ- деревья
Любая из следующих операций может быть выполнена за t ~ log N:
поиск элемента по заданному ключу;
поиск k-го элемента по заданному k;
вставка элемента в определенное
место;
удаление определенного элемента.
АВЛ- деревья
АВЛ- деревья
PTree = ^TTree;
TTree = record
Item: T; {элемент дерева}
Left, Right: PTree;
{указатели на поддеревья}
Balance: ShortInt;
{показатель сбалансированности}
end;
АВЛ- деревья
возможный вариант представления на С++ или Java
struct node
{ int Key;
int Count;
int bal; // Показатель
//балансированности вершины.
node *Left;
node *Right;
};
АВЛ- деревья
Включение вершины
hL = hR. После включения L и R станут разной высоты, но критерий сбалансированности не будет нарушен;
hL < hR. После включения L и R станут равной высоты, то есть критерий сбалансированности даже улучшится;
hL > hR. После включения критерий сбалансированности нарушится и дерево необходимо перестраивать.
АВЛ- деревья
Например:
АВЛ- деревья
Алгоритм включения вершины в дерево:
проход по дереву, чтобы убедиться, что включаемого значения в дереве нет;
включение новой вершины и определение результирующего показателя сбалансированности;
"отступление" по пути поиска и проверка в каждой вершине показателя сбалансированности. При необходимости - балансировка.
АВЛ- деревья
Алгоритм включения вершины в дерево:
проход по дереву, чтобы убедиться, что включаемого значения в дереве нет;
включение новой вершины и определение результирующего показателя сбалансированности;
"отступление" по пути поиска и проверка в каждой вершине показателя сбалансированности. При необходимости - балансировка.
АВЛ- деревья
АВЛ- деревья
Однократный LL-поворот
Однократный RR-поворот
Двухкратный LR-поворот
Двухкратный RL-поворот
Построение АВЛ-дерева
АВЛ- деревья
АВЛ- деревья
АВЛ- деревья
АВЛ- деревья
Математическое ожидание значения высоты при больших n близко к значению h = log2n + c, где c - малая константа (c ~0.25).
Вероятность того, что при вставке не потребуется дополнительная балансировка, потребуется однократный поворот или двукратный поворот, близка к значениям 2/3, 1/6 и 1/6
Среднее число сравнений при вставке n-го ключа в дерево выражается формулой alog2n+b (a и b - постоянные).
Для АВЛ-дерево операции: поиск, вставка и удаление вершины с заданным ключом имеет временную сложность O(log2n).
2-3-деревья
определение 2-3-дерева:
Каждый узел 2-3-дерева содержит одно или два значения.
Узлы дерева делятся на две категории — листья и промежуточные (внутренние) узлы, причем если промежуточный узел содержит одно значение, то он имеет два непустых поддерева (2-узел), а если он содержит два значения, то он имеет три непустых поддерева (3-узел).
Принцип упорядоченности значений сохраняется для 2-3-дерева . Для 2-узла, как и в случае бинарного дерева поиска, все значения, лежащие в левом поддереве, имеют значения, меньшие значения, хранящегося в узле, а значения, лежащие в правом поддереве, — больше или равны значениям, хранящимся в узле.
2-3-деревья
Для 3-узла упорядоченность означает следующее: если ключи, хранящиеся в нем, имеют значения K1, K2, а поддеревья этого узла обозначены T1, T2 и T3, то справедливо
неравенство
T1 < K1 < Т2 < К2 < Т3
• Все листья лежат на одном и том же уровне.
2-3-деревья
2-3-деревья
2-3-деревья
представление в виде бинарного дерева
Вставка и удаление
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
Свойства КЧД
• Корень черный;
Каждая вершина может быть либо красной, либо чёрной. Бесцветных вершин, или вершин другого цвета быть не может.
Каждый лист (NIL) имеет чёрный цвет.
Если вершина красная, то оба её потомка – чёрные.
Все пути от корня к листьям содержат одинаковое число чёрных вершин.
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
соответствие 2-3 и 2-4 дерева и КЧД
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
Операции вставки и удаления вершин в КЧД могут нарушать свойства КЧД.
Чтобы восстановить эти свойства, надо будет перекрашивать некоторые вершины и менять структуру дерева
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
Вставка
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
Вставка
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
Создание дерева
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
Ввод объекта «ключ-элемент» в красно-черное дерево, хранящее n элементов, выполняется за О(log n) времени и требует
максимум O(log n) перекрашиваний
http://rain.ifmo.ru/cat/view.php/vis/trees
Сильноветвящиеся деревья
B- деревья (B-trees, R.Bayer)
B- деревья (B-trees)
каждый узел имеет не более NumberOfItems сыновей;
каждый узел, кроме корня, имеет не менее NumberOfItems/2 сыновей;
корень, если он не лист, имеет не менее 2-х сыновей;
все листья расположены на одном уровне (дерево сбалансировано);
нелистовой узел с k сыновьями содержит не менее k-1 ключ.
B- деревья (B-trees)
Узел B-дерева, содержащий j ключей и j+1 указатель
K1< K2< ….
Pi указывает на поддерево с ключами между Ki и Ki+1
B- деревья (B-trees)
Type PBTreeNode = ^TBTreeNode; TBTreeNode =
record {узел дерева}
Count: Integer;
PreviousNode: PBTreeNode;
Items: array[0..NumberOfItems ] of record
Value: ItemType;
NextNode: PBTreeNode;
end;
end;
B- деревья (B-trees)
B- деревья (B-trees)
типичный шаблон работы с объектом х B- дерева :
х ← указатель на некоторый объект
Disk_Read(x)
Операции, обращающиеся и/или изменяющие поля х
Disk_Write(x) // Не требуется, если
поля х не изменялись
Прочие операции, не изменяющие поля х
B- деревья (B-trees)
1. Каждый узел x содержит следующие поля:
а) п (х), количество ключей, хранящихся в данный момент в узле х,
б) Собственно ключи, количество которых равно п (х) и которые хранятся в невозрастающем порядке
key1 (х) ≤ key2 (х) ≤ • • • ≤ key п (х) (х)
в)Логическое значение leaf (х), равное true, если х является листом, и false, если х — внутренний узел.
B- деревья (B-trees)
Кроме того, каждый внутренний узел х содержит п (х)+1 указателей
с1 (х), с2 (х), … с п (х)+1 (х)
на дочерние узлы. Листья не имеют дочерних узлов.
B- деревья (B-trees)
Ключи keyi (х)разделяют поддиапазоны ключей, хранящихся в поддеревьях: если ki — произвольный ключ, хранящийся в поддереве с корнем сi(х) то k1 ≤ key1 (х) ≤ k2 ≤ key2 (х) …≤
keyn(х) (х) ≤ k n(х)+1
B- деревья (B-trees)
Все листья расположены на одной и той же глубине, которая равна высоте дерева h.
Имеются нижняя и верхняя границы количества ключей, которые могут содержаться в узле.
Эти границы могут быть выражены с помощью одного фиксированного целого числа t ≥ 2, называемого минимальной степенью (minimum degree) В-дерева:
B- деревья (B-trees)
Каждый узел, кроме корневого, должен содержать как минимум t - 1 ключей.
Каждый внутренний узел, не являющийся корневым, имеет,таким образом, как минимум t дочерних узлов.
Если дерево не является пустым, корень должен содержать как минимум один ключ.
Каждый узел содержит не более 2t — 1 ключей. Таким образом, внутренний узел имеет не более 2t дочерних узлов. Узел заполнен (full), если он содержит ровно
2t — 1 ключей.
B- деревья (B-trees)
Высота В-дерева с n≥1 узлами и степенью t ≥ 2 не превышает
log t (n+1)/2
B- деревья (B-trees)
Алгоритм поиска:
BTreeSearch (x, k);
i:=1;
While i≤ п (х) & k > keyi(x)
i:= i +1;
If i≤ п (х) & k = keyi(x)
then return (x,i);
If leaf (x)
then return null
else DiskRead(ci(х)); return
BTreeSearch (сi (х), k);
B- деревья (B-trees)
Количество дисковых страниц, к которым обращается BTreeSearch
O (h) = O (logt n)
Общее время вычислений
O (t*h) = O (t*logt n)
B- деревья: поиск
B- деревья: создание пустого дерева
BTreeCreate( );
x :=AllocateNode ( );
leaf(x) := true;
n(х) := 0;
DiskWrite (x);
root := x
B- деревья: добавление
Поиск листового узла Node, в который следует произвести добавление элемента Item.
Добавление элемента Item в узел Node.
Если Node содержит больше, чем NumberOfItems элементов (произошло переполнение), то
делим Node на две части, не включая в них средний элемент;
Item=средний элемент Node;
Node=Node.PreviousNode;
Переходим к пункту 2.
B- деревья: добавление
B- деревья: добавление
B- деревья: добавление
BTreeInsert(T,k);
r:= root(T);
if n(r) = 2t-1;
then s:= AllocateNode ( );
root(T) :=s;
leaf (s) := false;
п (s) :=0;
c1(s) :=r;
BTreeSplitChild(s,1,r);
BtreeInsertNonfull(s,k);
else BtreeInsertNonfull(r,k);
B- деревья: добавление
B- деревья: добавление
B- деревья: добавление
B- деревья: добавление
B- деревья: добавление
B- деревья: удаление
Если узeл k находится в узле x и x –лист удаляем k из x
Если узeл k находится в узле x и x –внутренний узел
Если дочерний по отношению к x узел у, предшествующий ключу k, содержит не менее t ключей, то находим k1 – предшественника k в поддереве, корнем которого является y,рекурсивно удаляем k1 и заменяем k на k1
B- деревья: удаление
Если дочерний по отношению к x узел z, следующий за ключом k, содержит не менее t ключей, то находим k1 – следующий за k в поддереве, корнем которого является z, рекурсивно удаляем k1 и заменяем k на k1
B- деревья: удаление
если у и z содержат по t-1 ключей, то осуществляется слияние z в y
из x удаляется k и ссылка на z, y содержит 2t-1 узел
B- деревья: удаление
B- деревья: удаление
B- деревья: удаление
B- деревья: удаление
B- деревья: удаление
страница 1
скачать
Другие похожие работы: