🗊Презентация B и Красно-Черные деревья

Нажмите для полного просмотра!
B и Красно-Черные деревья, слайд №1B и Красно-Черные деревья, слайд №2B и Красно-Черные деревья, слайд №3B и Красно-Черные деревья, слайд №4B и Красно-Черные деревья, слайд №5B и Красно-Черные деревья, слайд №6B и Красно-Черные деревья, слайд №7B и Красно-Черные деревья, слайд №8B и Красно-Черные деревья, слайд №9B и Красно-Черные деревья, слайд №10B и Красно-Черные деревья, слайд №11B и Красно-Черные деревья, слайд №12B и Красно-Черные деревья, слайд №13B и Красно-Черные деревья, слайд №14B и Красно-Черные деревья, слайд №15B и Красно-Черные деревья, слайд №16B и Красно-Черные деревья, слайд №17B и Красно-Черные деревья, слайд №18B и Красно-Черные деревья, слайд №19B и Красно-Черные деревья, слайд №20B и Красно-Черные деревья, слайд №21B и Красно-Черные деревья, слайд №22B и Красно-Черные деревья, слайд №23B и Красно-Черные деревья, слайд №24B и Красно-Черные деревья, слайд №25B и Красно-Черные деревья, слайд №26B и Красно-Черные деревья, слайд №27B и Красно-Черные деревья, слайд №28B и Красно-Черные деревья, слайд №29B и Красно-Черные деревья, слайд №30B и Красно-Черные деревья, слайд №31B и Красно-Черные деревья, слайд №32B и Красно-Черные деревья, слайд №33B и Красно-Черные деревья, слайд №34B и Красно-Черные деревья, слайд №35B и Красно-Черные деревья, слайд №36B и Красно-Черные деревья, слайд №37B и Красно-Черные деревья, слайд №38B и Красно-Черные деревья, слайд №39B и Красно-Черные деревья, слайд №40B и Красно-Черные деревья, слайд №41B и Красно-Черные деревья, слайд №42B и Красно-Черные деревья, слайд №43B и Красно-Черные деревья, слайд №44B и Красно-Черные деревья, слайд №45B и Красно-Черные деревья, слайд №46B и Красно-Черные деревья, слайд №47B и Красно-Черные деревья, слайд №48B и Красно-Черные деревья, слайд №49B и Красно-Черные деревья, слайд №50B и Красно-Черные деревья, слайд №51B и Красно-Черные деревья, слайд №52

Содержание

Вы можете ознакомиться и скачать презентацию на тему B и Красно-Черные деревья. Доклад-сообщение содержит 52 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации


Слайд 1





B и Красно-Черные деревья
Лекция 19
Описание слайда:
B и Красно-Черные деревья Лекция 19

Слайд 2





План лекции
B деревья
Определение
Вставка и удаление вершины
Красно-черные деревья
Определение
Вставка вершины
Сравнение в АВЛ деревьями
Связь КЧ и B деревьев
Описание слайда:
План лекции B деревья Определение Вставка и удаление вершины Красно-черные деревья Определение Вставка вершины Сравнение в АВЛ деревьями Связь КЧ и B деревьев

Слайд 3





B деревья
B деревья – сбалансированные деревья для
быстрого доступа к информации на устройствах
с прямым доступом
Рудольф Бэйер (R. Bayer)
Эдвард МакКрейт (E. McCreight)
~1970
Страничная организация памяти
Файловые системы, например, Windows NTFS
Обработка больших массивов данных
Описание слайда:
B деревья B деревья – сбалансированные деревья для быстрого доступа к информации на устройствах с прямым доступом Рудольф Бэйер (R. Bayer) Эдвард МакКрейт (E. McCreight) ~1970 Страничная организация памяти Файловые системы, например, Windows NTFS Обработка больших массивов данных

Слайд 4





B деревья
Все листья находятся на одной глубине
Существует целое число t >= 2 -- степень B дерева, что 
Каждая вершина кроме корня имеет от t до 2*t прямых потомков
Корень имеет от 2 до 2*t прямых потомков
Каждая вершина хранит ключи, разграничивающие ключи, хранящиеся в ее поддеревьях
Сколько ключей может хранить вершина В дерева? Корень В дерева?
Все ключи В дерева принадлежат одному линейно упорядоченному множеству
Описание слайда:
B деревья Все листья находятся на одной глубине Существует целое число t >= 2 -- степень B дерева, что Каждая вершина кроме корня имеет от t до 2*t прямых потомков Корень имеет от 2 до 2*t прямых потомков Каждая вершина хранит ключи, разграничивающие ключи, хранящиеся в ее поддеревьях Сколько ключей может хранить вершина В дерева? Корень В дерева? Все ключи В дерева принадлежат одному линейно упорядоченному множеству

Слайд 5





Пример B дерева

Какая степень этого В дерева?
Описание слайда:
Пример B дерева Какая степень этого В дерева?

Слайд 6





Пример использования – страничная организация памяти
Лист B дерева = физический блок памяти
Физическая страница памяти или кластер диска
Совокупность внутренних вершин В дерева = «таблица трансляции адресов»
Хранится в специальных регистрах процессора и специальной области памяти
Ключи = логические адреса нулевых байтов физических блоков
Описание слайда:
Пример использования – страничная организация памяти Лист B дерева = физический блок памяти Физическая страница памяти или кластер диска Совокупность внутренних вершин В дерева = «таблица трансляции адресов» Хранится в специальных регистрах процессора и специальной области памяти Ключи = логические адреса нулевых байтов физических блоков

Слайд 7





Пример использования – управление страничной памятью
Поиск физического блока, хранящего байт с логическим адресом А
Он же «трансляция логического адреса А в физический адрес»
Поиск листа В дерева с ключом, равным остатку от деления А на размер физического блока
Добавление нового физического блока в пространство логических адресов
Вставка листа в В дерево
Описание слайда:
Пример использования – управление страничной памятью Поиск физического блока, хранящего байт с логическим адресом А Он же «трансляция логического адреса А в физический адрес» Поиск листа В дерева с ключом, равным остатку от деления А на размер физического блока Добавление нового физического блока в пространство логических адресов Вставка листа в В дерево

Слайд 8





B деревья -- определения
Вершина В дерева называется полной, если число ее непосредственных потомков равно удвоенной степени В дерева
В дерево степени 2 называется 2-3-4 деревом 
Каждая внутренняя вершина кроме корня имеет 2, 3 или 4 потомка
Описание слайда:
B деревья -- определения Вершина В дерева называется полной, если число ее непосредственных потомков равно удвоенной степени В дерева В дерево степени 2 называется 2-3-4 деревом Каждая внутренняя вершина кроме корня имеет 2, 3 или 4 потомка

Слайд 9





Теорема о высоте B дерева
Для любого B дерева высоты h и минимальной степени t ≥ 2, хранящего n ≥ 1 ключей, выполнено неравенство
	
Высота B дерева с n-вершинами есть O(log n), но основание логарифма для B дерева гораздо больше, что примерно в log t раз сокращает количество обращений к диску
Что такое глубина вершины?
Что такое высота (уровень) вершины?
Описание слайда:
Теорема о высоте B дерева Для любого B дерева высоты h и минимальной степени t ≥ 2, хранящего n ≥ 1 ключей, выполнено неравенство Высота B дерева с n-вершинами есть O(log n), но основание логарифма для B дерева гораздо больше, что примерно в log t раз сокращает количество обращений к диску Что такое глубина вершины? Что такое высота (уровень) вершины?

Слайд 10





Пример определения на Си
typedef struct b_tree_t {
	int n;			  // количество ключей
	int *key; 			  // key[0]<key[1]<…<key[n-1]
	struct b_tree_t **child; // непосредств. потомки
} b_tree;
Обозначим x->child[i] через Ci(x)
Описание слайда:
Пример определения на Си typedef struct b_tree_t { int n; // количество ключей int *key; // key[0]<key[1]<…<key[n-1] struct b_tree_t **child; // непосредств. потомки } b_tree; Обозначим x->child[i] через Ci(x)

Слайд 11





Поиск в В дереве
Дано В дерево и ключ К
Найти вершину, содержащую К
В каждой вершине х сравниваем К с n(x) ключами из x и продолжаем поиск в соотв. n(x)+1 потомков
Описание слайда:
Поиск в В дереве Дано В дерево и ключ К Найти вершину, содержащую К В каждой вершине х сравниваем К с n(x) ключами из x и продолжаем поиск в соотв. n(x)+1 потомков

Слайд 12





Алгоритм поиска
Поиск в B дереве похож на поиск в двоичном  дереве
Разница в том,  что в вершине x мы  выбираем один вариант из n(x)+1, а не из двух
Процедура поиска получает на вход указатель х на корень поддерева и ключ k, который мы ищем в этом поддереве 
Если процедура обнаруживает в дереве ключ k, то она возвращает пару  (y, i), где у - вершина, i - порядковый номер указателя, для которого keyi(y) = k
Иначе операция возвращает NULL
Описание слайда:
Алгоритм поиска Поиск в B дереве похож на поиск в двоичном дереве Разница в том, что в вершине x мы выбираем один вариант из n(x)+1, а не из двух Процедура поиска получает на вход указатель х на корень поддерева и ключ k, который мы ищем в этом поддереве Если процедура обнаруживает в дереве ключ k, то она возвращает пару (y, i), где у - вершина, i - порядковый номер указателя, для которого keyi(y) = k Иначе операция возвращает NULL

Слайд 13





Поиск в В дереве
B_tree_search(x,k)
{
  int i = 0;
	while (i < n(x) && k > keyi(x)) i++;
	if (i<n(x)&&k==keyi(x)) return(x,i); 
	if (leaf(x)) return NULL;
	else
  {	
		return B_tree_search(Ci(x),k);
	}
}
Описание слайда:
Поиск в В дереве B_tree_search(x,k) { int i = 0; while (i < n(x) && k > keyi(x)) i++; if (i<n(x)&&k==keyi(x)) return(x,i); if (leaf(x)) return NULL; else { return B_tree_search(Ci(x),k); } }

Слайд 14





Добавление элемента в B дерево
Процедура  B_tree_insert (T, k) – добавляет элемент k в B дерево T, пройдя один раз от корня к листу
На это требуется время O(h), если высота дерева равна h
По ходу дела с помощью процедуры B_tree_Split_child разделяются вершины, которые являются полными и которые имеют неполного родителя
В результате, доходим до неполного листа, куда и добавляем новый элемент
Описание слайда:
Добавление элемента в B дерево Процедура B_tree_insert (T, k) – добавляет элемент k в B дерево T, пройдя один раз от корня к листу На это требуется время O(h), если высота дерева равна h По ходу дела с помощью процедуры B_tree_Split_child разделяются вершины, которые являются полными и которые имеют неполного родителя В результате, доходим до неполного листа, куда и добавляем новый элемент

Слайд 15





Разбиение вершины B дерева 
Добавление элемента в B дерево – более сложная операция по сравнению с бинарными деревьями
Ключевым местом является разбиение полной (с 2t-1 ключами ) вершины на две вершины, имеющие по t-1 ключей в каждой
При этом ключ-медиана keyt1(y) отправляется к родителю x вершины y и становится разделителем двух полученных вершин
Это возможно, если вершина х неполна
Если y – корень, то высота дерева увеличивается на 1
Описание слайда:
Разбиение вершины B дерева Добавление элемента в B дерево – более сложная операция по сравнению с бинарными деревьями Ключевым местом является разбиение полной (с 2t-1 ключами ) вершины на две вершины, имеющие по t-1 ключей в каждой При этом ключ-медиана keyt1(y) отправляется к родителю x вершины y и становится разделителем двух полученных вершин Это возможно, если вершина х неполна Если y – корень, то высота дерева увеличивается на 1

Слайд 16





Разбиение вершины B дерева
Описание слайда:
Разбиение вершины B дерева

Слайд 17






// Входные данные
// неполная внутренняя вершина х, число i и
// полная вершина y: y = Сi(x)
// (cчитаем, что x и y уже в ОП)
B_tree_SPLIT_Child (x, i, y)
{
// z – создать узел;(файл, отвести место)
leaf(z) = leaf(y);
n(z) = t-1;
for(j = 0; j < t-1; j++) keyj(z) = keyj+t(y);
if (!leaf(y))
		for(j = 0; j < t; j++) Cj(z) = Cj+t(y);
n(y) = t-1;
Описание слайда:
// Входные данные // неполная внутренняя вершина х, число i и // полная вершина y: y = Сi(x) // (cчитаем, что x и y уже в ОП) B_tree_SPLIT_Child (x, i, y) { // z – создать узел;(файл, отвести место) leaf(z) = leaf(y); n(z) = t-1; for(j = 0; j < t-1; j++) keyj(z) = keyj+t(y); if (!leaf(y)) for(j = 0; j < t; j++) Cj(z) = Cj+t(y); n(y) = t-1;

Слайд 18






	for (j = n(x)+1; j ≤ i; j--) Cj+1(x) = Cj(x); 
	Ci+1[x] = z;
	for (j = n(x); j ≤ i; j--) keyj+1(x) = keyj(x);
	keyi(x) = keyj(y);
	n(x) = n(x)+1;
	//  Переписать вершины: y, z, x
}
// Вершина y имела 2t детей
// после разбиения в ней осталось t детей
// Остальные t детей стали детьми новой вершины z
Описание слайда:
for (j = n(x)+1; j ≤ i; j--) Cj+1(x) = Cj(x); Ci+1[x] = z; for (j = n(x); j ≤ i; j--) keyj+1(x) = keyj(x); keyi(x) = keyj(y); n(x) = n(x)+1; // Переписать вершины: y, z, x } // Вершина y имела 2t детей // после разбиения в ней осталось t детей // Остальные t детей стали детьми новой вершины z

Слайд 19






// добавление в дерево с корнем 
B_tree_insert (T, k)
{	
	r = root(T);
if (n(r)== 2t-1) { 
		// s = выделяем память/файл для нового узла;
		root(T)= s;		//он становится корнем	  	leaf(s)= 0;
		n(s)= 0;
		C1(s)= r;
		B_tree_split_child (S, 1, r);
		B_tree_insert_nonfull (s, k);//добавляет 
	} else
		// элемент в k в поддерево с корнем в неполной вершине 
		B_tree_insert_nonfull (r, k);
}
Описание слайда:
// добавление в дерево с корнем B_tree_insert (T, k) { r = root(T); if (n(r)== 2t-1) {  // s = выделяем память/файл для нового узла; root(T)= s; //он становится корнем leaf(s)= 0; n(s)= 0; C1(s)= r; B_tree_split_child (S, 1, r); B_tree_insert_nonfull (s, k);//добавляет } else // элемент в k в поддерево с корнем в неполной вершине B_tree_insert_nonfull (r, k); }

Слайд 20





Добавление элемента в неполную вершину
B_tree_insert_nonfull (r, k) рекурсивно вызывает себя, при необходимости, выполнив разделение 
Если вершина x – лист, то ключ k в него добавляется 
Иначе k добавляется к поддереву, корень которого является ребенком x
Для этого определяется нужный ребенок вершины x
Если ребенок – полная вершина, то он разделяется
Описание слайда:
Добавление элемента в неполную вершину B_tree_insert_nonfull (r, k) рекурсивно вызывает себя, при необходимости, выполнив разделение Если вершина x – лист, то ключ k в него добавляется Иначе k добавляется к поддереву, корень которого является ребенком x Для этого определяется нужный ребенок вершины x Если ребенок – полная вершина, то он разделяется

Слайд 21






B_tree_insert_nonfull(x, k)
{
i = n(x);
if (leaf(x)) { // ключ вставляется в лист
	while (i ≥ 0 && k < keyi(x)){
			keyi+1(x)=keyi(x);
			i--;
		}
  	keyi+1(x) = k; 
	n(x) = n(x)+1;
	} else {
		// поиск нужного ребенка
		while( i ≥ 0 && k < keyi(x)) i--;
Описание слайда:
B_tree_insert_nonfull(x, k) { i = n(x); if (leaf(x)) { // ключ вставляется в лист while (i ≥ 0 && k < keyi(x)){ keyi+1(x)=keyi(x); i--; }    keyi+1(x) = k; n(x) = n(x)+1; } else { // поиск нужного ребенка while( i ≥ 0 && k < keyi(x)) i--;

Слайд 22






	   i = i+1;
	   if (n(Ci(x)) == 2t-1) {
			// если ребенок–полная вершина 
			B_tree_split_child (x, i, Ci(x));
			// разделение
   		if (k > keyi(x)) i = i+1;
	}
   B_tree_ insert_nonfull (Ci(x), k);
 }
Описание слайда:
  i = i+1;    if (n(Ci(x)) == 2t-1) { // если ребенок–полная вершина B_tree_split_child (x, i, Ci(x)); // разделение     if (k > keyi(x)) i = i+1; }    B_tree_ insert_nonfull (Ci(x), k); }

Слайд 23





Удаление элемента из B дерева
Описание слайда:
Удаление элемента из B дерева

Слайд 24


B и Красно-Черные деревья, слайд №24
Описание слайда:

Слайд 25


B и Красно-Черные деревья, слайд №25
Описание слайда:

Слайд 26


B и Красно-Черные деревья, слайд №26
Описание слайда:

Слайд 27


B и Красно-Черные деревья, слайд №27
Описание слайда:

Слайд 28






B деревья
Определение
Вставка и удаление вершины
Красно-черные деревья
Определение
Вставка вершины
Сравнение в АВЛ деревьями
Связь КЧ и B деревьев
Описание слайда:
B деревья Определение Вставка и удаление вершины Красно-черные деревья Определение Вставка вершины Сравнение в АВЛ деревьями Связь КЧ и B деревьев

Слайд 29





Красно-чёрное дерево
Rudolf Bayer 1972
Симметричные двоичные B деревья
Леонидас Гибас и Роберт Седжвик 1978
КЧ деревья
Красно-чёрное дерево – это дерево двоичного
поиска, обладающее следующими
КЧ свойствами
Все листья чёрные и не содержат данных
Все потомки красных узлов чёрные – 
нет двух красных узлов подряд
На всех путях от корня к листьям число 
чёрных узлов одинаково и равно чёрной
высоте дерева
Описание слайда:
Красно-чёрное дерево Rudolf Bayer 1972 Симметричные двоичные B деревья Леонидас Гибас и Роберт Седжвик 1978 КЧ деревья Красно-чёрное дерево – это дерево двоичного поиска, обладающее следующими КЧ свойствами Все листья чёрные и не содержат данных Все потомки красных узлов чёрные – нет двух красных узлов подряд На всех путях от корня к листьям число чёрных узлов одинаково и равно чёрной высоте дерева

Слайд 30





Пример КЧ дерева (Википедия)
Описание слайда:
Пример КЧ дерева (Википедия)

Слайд 31





Высота и число узлов в КЧ дереве
Если h - чёрная высота дерева, то количество узлов не менее 2h − 1
Почему?
Что останется от КЧ дерева, если красные вершины "втянутся" в черных предков?
Как выглядит двоичное дерево, у которого все листья находятся на одной глубине?
Если h - высота дерева, то количество узлов не менее 2(h−1)/2
Если количество узлов N, высота дерева не больше 2log2N + 1
Описание слайда:
Высота и число узлов в КЧ дереве Если h - чёрная высота дерева, то количество узлов не менее 2h − 1 Почему? Что останется от КЧ дерева, если красные вершины "втянутся" в черных предков? Как выглядит двоичное дерево, у которого все листья находятся на одной глубине? Если h - высота дерева, то количество узлов не менее 2(h−1)/2 Если количество узлов N, высота дерева не больше 2log2N + 1

Слайд 32





Вставка узла в КЧ дерево -- схема
Чтобы вставить узел
Находим двоичным поиском место, куда его следует добавить 
Новый узел добавляем как красный узел с двумя чёрными листьями
После этого восстанавливаем красно-чёрные свойства -- перекрашиваем узлы и поворачиваем поддеревья, если необходимо
Описание слайда:
Вставка узла в КЧ дерево -- схема Чтобы вставить узел Находим двоичным поиском место, куда его следует добавить Новый узел добавляем как красный узел с двумя чёрными листьями После этого восстанавливаем красно-чёрные свойства -- перекрашиваем узлы и поворачиваем поддеревья, если необходимо

Слайд 33





Вставка узла -- лист
Вставка красного узла с двумя черными NULL-потомками
Все листья чёрные – сохраняется
Все потомки красных узлов чёрные – нет двух красных узлов подряд – может нарушиться
На всех путях от корня к листьям число чёрных узлов одинаково – сохраняется
Описание слайда:
Вставка узла -- лист Вставка красного узла с двумя черными NULL-потомками Все листья чёрные – сохраняется Все потомки красных узлов чёрные – нет двух красных узлов подряд – может нарушиться На всех путях от корня к листьям число чёрных узлов одинаково – сохраняется

Слайд 34





Вставка узла – красные отец и дядя
Цвет отца и дяди меняется на черный
Цвет деда меняется на красный
КЧ свойства (возможно) нарушились на 2 уровня выше -- повторяем уже для деда узла
В самом конце корень красим в черный цвет
Если он был красным, то увеличится черная высота дерева
Описание слайда:
Вставка узла – красные отец и дядя Цвет отца и дяди меняется на черный Цвет деда меняется на красный КЧ свойства (возможно) нарушились на 2 уровня выше -- повторяем уже для деда узла В самом конце корень красим в черный цвет Если он был красным, то увеличится черная высота дерева

Слайд 35





Вставка узла – красные отец и дядя
Красно-красный конфликт устраняется перекрашиванием
После перекраски нужно проверить деда нового узла (узел B), поскольку он может оказаться красным
Описание слайда:
Вставка узла – красные отец и дядя Красно-красный конфликт устраняется перекрашиванием После перекраски нужно проверить деда нового узла (узел B), поскольку он может оказаться красным

Слайд 36





Вставка узла – отец красный, дядя черный
Новый узел -- левый сын своего отца
Цвет отца меняется на черный
Цвет деда меняется на красный
Дерево поворачивается направо вокруг отца нового узла
КЧ свойство восстановлено, вставка закончена
Новый узел -- правый сын своего отца
Дерево поворачивается налево вокруг отца нового узла
Далее см. пред. случай
Описание слайда:
Вставка узла – отец красный, дядя черный Новый узел -- левый сын своего отца Цвет отца меняется на черный Цвет деда меняется на красный Дерево поворачивается направо вокруг отца нового узла КЧ свойство восстановлено, вставка закончена Новый узел -- правый сын своего отца Дерево поворачивается налево вокруг отца нового узла Далее см. пред. случай

Слайд 37





Вставка узла – отец красный, дядя черный,
левый
сын
Описание слайда:
Вставка узла – отец красный, дядя черный, левый сын

Слайд 38





Вставка узла – отец красный, дядя черный,
правый
сын
Далее как на пред. слайде
Описание слайда:
Вставка узла – отец красный, дядя черный, правый сын Далее как на пред. слайде

Слайд 39





Сравнение с АВЛ деревом
Обозначим N(h) = минимальное число узлов в дереве высоты h
N(h) для АВЛ дерева
N(h) = N(h − 1) + N(h − 2) + 1, N(0) = 1, N(1) = 2
N(h) растёт как последовательность Фибоначчи – почему?
Следовательно, N(h) = Θ(λh), где 
N(h) для красно-чёрного дерева
Свойство 3 красно-чёрных деревьев  ==> 
При том же количестве узлов КЧ дерево м. б. выше АВЛ дерева, но не более чем в 			      раз
Описание слайда:
Сравнение с АВЛ деревом Обозначим N(h) = минимальное число узлов в дереве высоты h N(h) для АВЛ дерева N(h) = N(h − 1) + N(h − 2) + 1, N(0) = 1, N(1) = 2 N(h) растёт как последовательность Фибоначчи – почему? Следовательно, N(h) = Θ(λh), где N(h) для красно-чёрного дерева Свойство 3 красно-чёрных деревьев ==> При том же количестве узлов КЧ дерево м. б. выше АВЛ дерева, но не более чем в раз

Слайд 40





Сравнение с АВЛ деревом
Поиск и вставка для АВЛ дерева м.б. быстрее, чем для КЧ дерева
Высота КЧ дерева м. б. на 40% больше высоты АВЛ дерева при одинаковом числе узлов
Удаление из КЧ дерева м. б. быстрее, чем из АВЛ дерева
КЧ дерево – достаточно 2 или менее поворотов
АВЛ дерево – возможно понадобится поворот в каждом узле на пути от удаляемого листа до корня
Описание слайда:
Сравнение с АВЛ деревом Поиск и вставка для АВЛ дерева м.б. быстрее, чем для КЧ дерева Высота КЧ дерева м. б. на 40% больше высоты АВЛ дерева при одинаковом числе узлов Удаление из КЧ дерева м. б. быстрее, чем из АВЛ дерева КЧ дерево – достаточно 2 или менее поворотов АВЛ дерево – возможно понадобится поворот в каждом узле на пути от удаляемого листа до корня

Слайд 41





Связь КЧ и B деревьев
B деревья с t=2 можно перестроить в КЧ деревья так 
Каждый узел окрашен либо в красный, либо в чёрный цвет
Вершина с двумя потомками черная и переносится в КЧ дерево без изменений -- почему нет вершин с одним потомком?
Вершина с тремя потомками черная, первый потомок черный и присоединяется непосредственно, а другие два -- через соединительный красный узел
Вершина с четырьмя потомками черная, черные потомки присоединяются через два красных соединительных узла
В исходном B дереве (так как оно сбалансировано) все пути от корня до любого листа имеют одинаковую длину
По построению очевидно, что длина любого пути в КЧ дереве возрастает не более чем в два раза
Описание слайда:
Связь КЧ и B деревьев B деревья с t=2 можно перестроить в КЧ деревья так Каждый узел окрашен либо в красный, либо в чёрный цвет Вершина с двумя потомками черная и переносится в КЧ дерево без изменений -- почему нет вершин с одним потомком? Вершина с тремя потомками черная, первый потомок черный и присоединяется непосредственно, а другие два -- через соединительный красный узел Вершина с четырьмя потомками черная, черные потомки присоединяются через два красных соединительных узла В исходном B дереве (так как оно сбалансировано) все пути от корня до любого листа имеют одинаковую длину По построению очевидно, что длина любого пути в КЧ дереве возрастает не более чем в два раза

Слайд 42





Использование в библиотеке стандартных шаблонов С++ (STL)
АВЛ-деревья 1961 -- первые сбалансированные деревья
Красно-чёрные деревья 1978
Библиотека стандартных шаблонов STL 
языка C++ использует сбалансированные деревья для реализации множества и ассоциативного массива
Описание слайда:
Использование в библиотеке стандартных шаблонов С++ (STL) АВЛ-деревья 1961 -- первые сбалансированные деревья Красно-чёрные деревья 1978 Библиотека стандартных шаблонов STL языка C++ использует сбалансированные деревья для реализации множества и ассоциативного массива

Слайд 43





Заключение
B деревья
Определение
Вставка и удаление вершины
Красно-черные деревья
Определение
Вставка вершины
Сравнение в АВЛ деревьями
Связь КЧ и B деревьев
Описание слайда:
Заключение B деревья Определение Вставка и удаление вершины Красно-черные деревья Определение Вставка вершины Сравнение в АВЛ деревьями Связь КЧ и B деревьев

Слайд 44





Удаление узла из КЧ дерева
Если удаляемый узел красный все правила сохраняются и все прекрасно
Если же удаляемый узел черный, требуется значительное количество кода, для поддержания дерева частично сбалансированным
Как и в случае вставки в красно-черное дерево, здесь также существует несколько различных случаев
Описание слайда:
Удаление узла из КЧ дерева Если удаляемый узел красный все правила сохраняются и все прекрасно Если же удаляемый узел черный, требуется значительное количество кода, для поддержания дерева частично сбалансированным Как и в случае вставки в красно-черное дерево, здесь также существует несколько различных случаев

Слайд 45






При высоте 2 и размере страницы 8Кб это дерево содержит > миллиарда ключей и позволяет адресовать 8Тб данных
Описание слайда:
При высоте 2 и размере страницы 8Кб это дерево содержит > миллиарда ключей и позволяет адресовать 8Тб данных

Слайд 46





B деревья
I am occasionally asked what the B in B-Tree means.  I recall it as a lunchtime discussion that you never in your wildest dreams imagine will one day have deep historical significance.  We wanted the name to be short, quick to type, easy to remember.  It honored our employer, Boeing Airplane Company, but we wouldn't have to request permission to use the name.  It suggested Balance.  Rudolf Bayer was the senior researcher of the two of us.  We had been admiring the elegant natural balance of AVL Trees, but for reasons clear to American English speakers, the name BM Tree was a non-starter.  I don't recall one meaning standing out above the others that day.  Rudolf is fond of saying that the more you think about what the B could mean, the more you learn about B-Trees, and that is good. (2012)
Описание слайда:
B деревья I am occasionally asked what the B in B-Tree means.  I recall it as a lunchtime discussion that you never in your wildest dreams imagine will one day have deep historical significance.  We wanted the name to be short, quick to type, easy to remember.  It honored our employer, Boeing Airplane Company, but we wouldn't have to request permission to use the name.  It suggested Balance.  Rudolf Bayer was the senior researcher of the two of us.  We had been admiring the elegant natural balance of AVL Trees, but for reasons clear to American English speakers, the name BM Tree was a non-starter.  I don't recall one meaning standing out above the others that day.  Rudolf is fond of saying that the more you think about what the B could mean, the more you learn about B-Trees, and that is good. (2012)

Слайд 47






У таких деревьев, как правило, только корень находится в ОП, остальное дерево – на диске
Диск разбит на сектора (дорожки на сектора)
Обычно записывают или считывают сектор целиком
Время доступа, чтобы подвести головку к нужному месту на диске, может быть достаточно большим
Как только головка диска установлена, запись или чтение происходит довольно быстро
Часто получается, что обработка прочитанного занимает меньше времени, чем поиск нужного сектора
Важно количество обращений к диску!
Описание слайда:
У таких деревьев, как правило, только корень находится в ОП, остальное дерево – на диске Диск разбит на сектора (дорожки на сектора) Обычно записывают или считывают сектор целиком Время доступа, чтобы подвести головку к нужному месту на диске, может быть достаточно большим Как только головка диска установлена, запись или чтение происходит довольно быстро Часто получается, что обработка прочитанного занимает меньше времени, чем поиск нужного сектора Важно количество обращений к диску!

Слайд 48





Определение B дерева 1/3
В каждой вершине x хранятся
n - количество ключей, в данной вершине
сами ключи k0 ≤ k1 ≤ … ≤ kn-1 в неубывающем порядке
булевское значение leaf[x], истинное, если вершина x - лист
Если x – внутренняя вершина, то она также содержит n(x)+1-указателей: C0, C1,…, Cn(x) на ее детей
Описание слайда:
Определение B дерева 1/3 В каждой вершине x хранятся n - количество ключей, в данной вершине сами ключи k0 ≤ k1 ≤ … ≤ kn-1 в неубывающем порядке булевское значение leaf[x], истинное, если вершина x - лист Если x – внутренняя вершина, то она также содержит n(x)+1-указателей: C0, C1,…, Cn(x) на ее детей

Слайд 49





Определение B дерева 2/3
Ключи keyi[x] служат границами, разделяющими значения ключей в поддеревьях: 
	k0 ≤ key0[x] ≤ k1 ≤ key2[x] ≤... ≤ keyn[x]-1[x] ≤ Kn[x],
где ki - множество ключей, хранящихся в поддереве с корнем Ci[x]
Описание слайда:
Определение B дерева 2/3 Ключи keyi[x] служат границами, разделяющими значения ключей в поддеревьях: k0 ≤ key0[x] ≤ k1 ≤ key2[x] ≤... ≤ keyn[x]-1[x] ≤ Kn[x], где ki - множество ключей, хранящихся в поддереве с корнем Ci[x]

Слайд 50





Создание корня B дерева 
B_tree *B = (B_tree*) malloc (sizeof(*B));
B->n = 1;
B->key = (int*) malloc (B->n*sizeof(int));
B->key[0] = 'M';
B->child = NULL;
Описание слайда:
Создание корня B дерева B_tree *B = (B_tree*) malloc (sizeof(*B)); B->n = 1; B->key = (int*) malloc (B->n*sizeof(int)); B->key[0] = 'M'; B->child = NULL;

Слайд 51





Создание  B дерева
B->child = (B_tree**)malloc(sizeof(B_tree*)*2);
B->child[0]=(B_tree*)malloc(sizeof(B_tree));
B->child[1]=(B_tree*)malloc(sizeof(B_tree));
x=B->child[0];
x->n=2;
x->key=(int*)malloc(x->n*sizeof(int));
x->key[0]='D';
x->key[1]='H';
X->child=NULL;
// Аналогичные действия для вершины: QTX
// Как это сделать цивилизованно?
Описание слайда:
Создание B дерева B->child = (B_tree**)malloc(sizeof(B_tree*)*2); B->child[0]=(B_tree*)malloc(sizeof(B_tree)); B->child[1]=(B_tree*)malloc(sizeof(B_tree)); x=B->child[0]; x->n=2; x->key=(int*)malloc(x->n*sizeof(int)); x->key[0]='D'; x->key[1]='H'; X->child=NULL; // Аналогичные действия для вершины: QTX // Как это сделать цивилизованно?

Слайд 52






Возможна реализация,  где каждая вершина является отдельным файлом
	
В общем случае имеются операции
Disk_READ(x) – чтение с диска
Disk_Write(x) – запись на диск
Описание слайда:
Возможна реализация, где каждая вершина является отдельным файлом В общем случае имеются операции Disk_READ(x) – чтение с диска Disk_Write(x) – запись на диск



Похожие презентации
Mypresentation.ru
Загрузить презентацию