Содержание
- 2. План лекции B деревья Определение Вставка и удаление вершины Красно-черные деревья Определение Вставка вершины Сравнение в
- 3. B деревья – сбалансированные деревья для быстрого доступа к информации на устройствах с прямым доступом Рудольф
- 4. Все листья находятся на одной глубине Существует целое число t >= 2 -- степень B дерева,
- 5. Какая степень этого В дерева? M D H Q T X B C F G N
- 6. Лист B дерева = физический блок памяти Физическая страница памяти или кластер диска Совокупность внутренних вершин
- 7. Поиск физического блока, хранящего байт с логическим адресом А Он же «трансляция логического адреса А в
- 8. Вершина В дерева называется полной, если число ее непосредственных потомков равно удвоенной степени В дерева В
- 9. Теорема о высоте B дерева Для любого B дерева высоты h и минимальной степени t ≥
- 10. typedef struct b_tree_t { int n; // количество ключей int *key; // key[0] struct b_tree_t **child;
- 11. Поиск в В дереве Дано В дерево и ключ К Найти вершину, содержащую К В каждой
- 12. Поиск в B дереве похож на поиск в двоичном дереве Разница в том, что в вершине
- 13. B_tree_search(x,k) { int i = 0; while (i keyi(x)) i++; if (i if (leaf(x)) return NULL;
- 14. Процедура B_tree_insert (T, k) – добавляет элемент k в B дерево T, пройдя один раз от
- 15. Добавление элемента в B дерево – более сложная операция по сравнению с бинарными деревьями Ключевым местом
- 16. Разбиение вершины B дерева …N W… P Q R S T U V … N S
- 17. // Входные данные // неполная внутренняя вершина х, число i и // полная вершина y: y
- 18. for (j = n(x)+1; j ≤ i; j--) Cj+1(x) = Cj(x); Ci+1[x] = z; for (j
- 19. // добавление в дерево с корнем B_tree_insert (T, k) { r = root(T); if (n(r)== 2t-1)
- 20. B_tree_insert_nonfull (r, k) рекурсивно вызывает себя, при необходимости, выполнив разделение Если вершина x – лист, то
- 21. B_tree_insert_nonfull(x, k) { i = n(x); if (leaf(x)) { // ключ вставляется в лист while (i
- 22. i = i+1; if (n(Ci(x)) == 2t-1) { // если ребенок–полная вершина B_tree_split_child (x, i, Ci(x));
- 23. Удаление элемента из B дерева
- 24. (в) удалена M из внутренней вершины, ребенок которой имеет не менее t элементов Если ребенок, следующий
- 25. (г) удалена G, ее дети имеют по t-1 ключу
- 26. (д) удалена D, в вершине х нет ключа D и t = 2
- 28. B деревья Определение Вставка и удаление вершины Красно-черные деревья Определение Вставка вершины Сравнение в АВЛ деревьями
- 29. Красно-чёрное дерево Rudolf Bayer 1972 Симметричные двоичные B деревья Леонидас Гибас и Роберт Седжвик 1978 КЧ
- 30. Пример КЧ дерева (Википедия)
- 31. Высота и число узлов в КЧ дереве Если h - чёрная высота дерева, то количество узлов
- 32. Вставка узла в КЧ дерево -- схема Чтобы вставить узел Находим двоичным поиском место, куда его
- 33. Вставка узла -- лист Вставка красного узла с двумя черными NULL-потомками Все листья чёрные – сохраняется
- 34. Вставка узла – красные отец и дядя Цвет отца и дяди меняется на черный Цвет деда
- 35. Красно-красный конфликт устраняется перекрашиванием После перекраски нужно проверить деда нового узла (узел B), поскольку он может
- 36. Вставка узла – отец красный, дядя черный Новый узел -- левый сын своего отца Цвет отца
- 37. Вставка узла – отец красный, дядя черный, левый сын отец дядя
- 38. Вставка узла – отец красный, дядя черный, правый сын Далее как на пред. слайде X B
- 39. Сравнение с АВЛ деревом Обозначим N(h) = минимальное число узлов в дереве высоты h N(h) для
- 40. Сравнение с АВЛ деревом Поиск и вставка для АВЛ дерева м.б. быстрее, чем для КЧ дерева
- 41. B деревья с t=2 можно перестроить в КЧ деревья так Каждый узел окрашен либо в красный,
- 42. Использование в библиотеке стандартных шаблонов С++ (STL) АВЛ-деревья 1961 -- первые сбалансированные деревья Красно-чёрные деревья 1978
- 43. Заключение B деревья Определение Вставка и удаление вершины Красно-черные деревья Определение Вставка вершины Сравнение в АВЛ
- 44. Удаление узла из КЧ дерева Если удаляемый узел красный все правила сохраняются и все прекрасно Если
- 45. При высоте 2 и размере страницы 8Кб это дерево содержит > миллиарда ключей и позволяет адресовать
- 46. I am occasionally asked what the B in B-Tree means. I recall it as a lunchtime
- 47. У таких деревьев, как правило, только корень находится в ОП, остальное дерево – на диске Диск
- 48. В каждой вершине x хранятся n - количество ключей, в данной вершине сами ключи k0 ≤
- 49. Ключи keyi[x] служат границами, разделяющими значения ключей в поддеревьях: k0 ≤ key0[x] ≤ k1 ≤ key2[x]
- 50. B_tree *B = (B_tree*) malloc (sizeof(*B)); B->n = 1; B->key = (int*) malloc (B->n*sizeof(int)); B->key[0] =
- 51. 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; // Аналогичные действия для вершины:
- 53. Скачать презентацию