Деревья. Лекция 8

Август 19, 2022

Главная
Информатика
Деревья. Лекция 8

Содержание

2. Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов. Является связным графом,
3. Синтаксическое дерево – это дерево в котором внутренние вершины это операторы языка программирования, а листья операнды
4. Генеалогическое древо
5. Логические файловые системы Деревья используются в файловых системах ОС.
6. Префиксное дерево – это дерево содержащее все суффиксы некоторой строки и позволяют осуществить поиск подстроки в
7. Деревья решений (decition trees) используются в классификации
8. Определения Корневой узел, корень дерева — самый верхний узел дерева. Корень поддерева — одна из вершин,
9. Определения Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой
10. Определения Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов; Внутренний узел — любой
11. Определения Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов; Внутренний узел — любой
12. Определения Глубина дерева – длина самого длинного пути от корня до листа. Каждое дерево обладает следующими
13. Определения Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один
14. Определения Три наиболее часто используемых способа обхода дерева: прямой; симметричный; обратный.
15. Бинарное дерево – это дерево, в котором каждый узел имеет не более двух дочерних элементов, которые
16. Бинарное дерево поиска – это бинарное дерево, в котором справедливо следующее: Оба поддерева — левое и
17. Реализация бинарного дерева поиска
18. Реализация бинарного дерева поиска
19. Реализация бинарного дерева поиска Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right),
20. Реализация бинарного дерева поиска Данные (data) обладают ключом (key), на котором определена операция сравнения «меньше». В
21. Класс узла дерева – TreeNode class TreeNode where T: IComparable { T value; TreeNode left; TreeNode
22. Класс дерева – MyTree Добавление узла в дерево Поиск значения Удаление узла из дерева Вычисление: глубины
23. Класс дерева – MyTree class MyTree where T: IComparable { TreeNode root; public void Add(T value){…}
24. Добавление узла в дерево void Add(T value) public void Add(T value) { TreeNode node = new
25. Добавление узла в дерево void Add(T value) public void Add(T value) { TreeNode node = new
26. Добавление узла в дерево void Add(T value) public void Add(T value) { TreeNode node = new
27. Добавление узла в дерево void Add(T value) public void Add(T value) { TreeNode node = new
28. public void Add(T value) { TreeNode node = new TreeNode (value); if (root == null) root
29. public void Add(T value) { TreeNode node = new TreeNode (value); if (root == null) root
30. Поиск значения public TreeNode Find(T value)
31. Поиск значения public TreeNode Find(T value) public TreeNode Find(T value) { if (root == null) return
32. Поиск значения public TreeNode Find(T value) public TreeNode Find(T value) { return Find(value, root); } private
33. Поиск значения public TreeNode Find(T value) public TreeNode Find(T value) { return Find(value, root); } private
34. Симметричный обход string LNR() 10 20 40 50 60 70
35. Симметричный обход string LNR() public string LNR() { return LNR(root); } private string LNR(TreeNode subroot) {
36. Прямой обход string NLR() 40 20 10 60 50 70
37. Прямой обход string NLR() public string NLR() { return NLR(root); } private string NLR(TreeNode subroot) {
38. Обратный обход string ???() ? ? ? ? ? ?
39. Обратный обход string LRN() 10 20 50 70 60 40
40. Обратный обход string LRN() public string LRN() { return LRN(root); } private string LRN(TreeNode subroot) {
41. Вычисление глубины дерева int GetDeep() 1 1 0
42. Вычисление глубины дерева int GetDeep() 2 1 0 1 1 1 1
43. Вычисление глубины дерева int GetDeep() 2 1 0 1 1 2 1
44. Вычисление глубины дерева int GetDeep() 2 1 0 3 1 2 1
45. 2 1 0 3 1 2 1 Вычисление глубины дерева int GetDeep() public int GetDeep() {
46. Вычисление количества листьев int GetLeafs() public int GetLeafs() { return GetLeafs(root); } private int GetLeafs(TreeNode subroot)
47. Вычисление количества узлов int GetNodes() public int GetNodes() { return GetNodes(root); } private int GetNodes(TreeNode subroot)
48. Если это лист Если у этого узла одно поддерево Если у этого узла два поддерева Удаление
49. Удаление узла дерева Если это лист public void Remove(T value) { return Remove(value, root); } private
50. Удаление узла Если одно поддерево private void Remove(T value, TreeNode subroot) { if (subroot == null)
51. Удаление узла Если два поддерева private void Remove(T value, TreeNode subroot) { if (subroot == null)
52. Удаление узла public void Remove(T value) { return Remove(value, root); } private void Remove(T value, TreeNode
53. Удаление узла Если корень public void Remove(T value) { return Remove(value, root); } private void Remove(T
54. public void Remove(T value) { if (root != null && root.Value == value) { if (root.Left
55. public void Remove(T value) { if (root != null && root.Value == value) { if (root.Left
56. public void Remove(T value) { if (root != null && root.Value == value) { if (root.Left
57. public void Remove(T value) { if (root != null && root.Value == value) { if (root.Left
58. public class TreeNode > { T value; TreeNode left; TreeNode right; TreeNode parent; public TreeNode(T value)
59. public class MyTree > { TreeNode root; public void Delete(T value){ … } private void Delete(???)
60. public void Delete(T value){ if (root == null) return; if (root.getValue() == value) { if (root.getLeft()
61. public void Delete(T value){ if (root == null) return; if (root.getValue() == value) { if (root.getLeft()
62. private void Delete(T value, TreeNode subroot, boolean isLeft) { if (subroot == null) return; if (subroot.getValue()
63. АВЛ-дерево АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух
64. Максимальная высота АВЛ-дерева при заданном числе узлов
65. Дерево Фибоначчи Дерево Фибоначчи — АВЛ-дерево с наименьшим числом вершин при заданной высоте (глубине). Если для
66. Дерево Фибоначчи
67. Балансировка Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев
68. Правый поворот (малое правое вращение) Данное вращение используется тогда, когда: (высота b-поддерева — высота R) =
69. Правый поворот (малое правое вращение) private TreeNode RightRotate(TreeNode subroot) { TreeNode b = subroot.Left; subroot.Left =
70. Левый поворот (малое левое вращение) Данное вращение используется тогда, когда: (высота b-поддерева — высота L) =
71. Левый поворот (малое левое вращение) private TreeNode LeftRotate(TreeNode subroot) { TreeNode b = subroot.Right; subroot.Right =
72. Большой левый поворот (большое левое вращение) Данное вращение используется тогда, когда (высота b-поддерева — высота L)
73. Большой левый поворот (большое левое вращение)
74. Большой левый поворот (большое левое вращение) subroot.Right = RightRotate(subroot.Right); return LeftRotate(subroot);
75. Большой правый поворот (большое правое вращение) Данное вращение используется тогда, когда (высота b-поддерева — высота R)
76. Большой правый поворот (большое правое вращение) subroot.Left = LeftRotate(subroot.Left); return RightRotate(subroot);
77. Балансировка узла TreeNode Balance(TreeNode subroot) // балансировка узла p { if( (GetHeight(subroot.getRight()) - GetHeight(subroot.getLeft()))==2 ) {
78. Удаление узла из АВЛ дерева
79. Удаление узла из АВЛ дерева // поиск узла с минимальным ключом в поддереве TreeNode GetMin(TreeNode subroot)
80. Удаление узла из АВЛ дерева TreeNode Remove(TreeNode subroot, T value) // удаление значения из поддерева {
83. Скачать презентацию

Слайд 2

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных

узлов. Является связным графом, не содержащим циклы.

Слайд 3

Синтаксическое дерево – это дерево в котором внутренние вершины это операторы

языка программирования, а листья операнды

Слайд 4

Генеалогическое древо

Слайд 5

Логические файловые системы
Деревья используются в файловых системах ОС.

Слайд 6

Префиксное дерево – это дерево содержащее все суффиксы некоторой строки и

позволяют осуществить поиск подстроки в строке

Слайд 7

Деревья решений (decition trees) используются в классификации

Слайд 8

Определения
Корневой узел, корень дерева — самый верхний узел дерева.
Корень поддерева — одна из

вершин, по желанию наблюдателя, которая имеет дочерние элементы.

Слайд 9

Определения
Поддерево — часть древообразной структуры данных, которая может быть представлена в виде

отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T.

Слайд 10

Определения
Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов;
Внутренний узел —

любой узел дерева, имеющий потомков, и таким образом, не являющийся листом;

Слайд 11

Определения
Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов;
Внутренний узел —

любой узел дерева, имеющий потомков, и таким образом, не являющийся листом;

Слайд 12

Определения
Глубина дерева – длина самого длинного пути от корня до листа.
Каждое дерево обладает

следующими свойствами:
существует узел, в который не входит ни одной дуги (корень);
в каждую вершину, кроме корня, входит одна дуга.

Слайд 13

Определения
Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только

один раз.
При обходе все вершины дерева должны посещаться в определенном порядке. Существует несколько способов обхода всех вершин дерева.
Три наиболее часто используемых способа обхода дерева:
прямой;
симметричный;
обратный.

Слайд 14

Определения
Три наиболее часто используемых способа обхода дерева:
прямой;
симметричный;
обратный.

Слайд 15

Бинарное дерево – это дерево, в котором каждый узел имеет не

более двух дочерних элементов, которые называются левым дочерним элементом и правым дочерним элементом

Слайд 16

Бинарное дерево поиска – это бинарное дерево, в котором справедливо следующее:
Оба

поддерева — левое и правое — являются двоичными деревьями поиска.
У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X.

Слайд 17

Реализация бинарного дерева поиска

Слайд 18

Реализация бинарного дерева поиска

Слайд 19

Реализация бинарного дерева поиска
Двоичное дерево состоит из узлов (вершин) — записей вида

(data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла — левый и правый сыновья соответственно.
Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) — ссылки на родительский элемент.

Слайд 20

Реализация бинарного дерева поиска
Данные (data) обладают ключом (key), на котором

определена операция сравнения «меньше». В конкретных реализациях это может быть пара (key, value) — (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.
Для любого узла X выполняются свойства дерева поиска:
key[left[X]] < key[X] ≤ key[right[X]],
то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.

Слайд 21

Класс узла дерева – TreeNode
class TreeNode where T: IComparable
{
T

value;
TreeNode left;
TreeNode right;
public TreeNode(T value) {
this.value = value;
}
// добавить public свойства
}

Слайд 22

Класс дерева – MyTree
Добавление узла в дерево
Поиск значения
Удаление узла из

дерева
Вычисление:
глубины дерева
количества листьев, узлов
Обходы дерева

Слайд 23

Класс дерева – MyTree
class MyTree where T: IComparable
{
TreeNode root;
public

void Add(T value){…}
public TreeNode Find(T value){…}
public void Remove(T value){…}
public int GetDeep(){…}
public int GetLeafs(){…}
public int GetNodes(){…}
public string LNR(){…}
public string NLR(){…}
public string ???(){…}
}

Слайд 24

Добавление узла в дерево void Add(T value)
public void Add(T value)
{
TreeNode node

= new TreeNode(value);
if (root == null) root = node;
}

Слайд 25

Добавление узла в дерево void Add(T value)
public void Add(T value)
{
TreeNode node

= new TreeNode(value);
if (root == null) root = node;
else ???
}

Слайд 26

Добавление узла в дерево void Add(T value)
public void Add(T value)
{
TreeNode node

= new TreeNode(value);
if (root == null) root = node;
else
{
if (root.Value <= node.Value)
{
root.Right = node;
}
if (root.Value > node.Value)
{
root.Left = node;
}
}
}

Слайд 27

Добавление узла в дерево void Add(T value)
public void Add(T value)
{
TreeNode node

= new TreeNode(value);
if (root == null) root = node;
else
{
if (root.Value <= node.Value)
{
root.Right = node;
}
if (root.Value > node.Value)
{
root.Left = node;
}
}
}

Слайд 28

public void Add(T value)
{
TreeNode node = new TreeNode(value);
if (root

== null) root = node;
else Add(root, node);
}
private void Add(TreeNode subroot, TreeNode node )
{
if (subroot.Value <= node.Value)
{
if (subroot.Right == null) subroot.Right = node;
else Add(subroot.Right, node);
}
if (subroot.Value > node.Value)
{
if (subroot.Left == null) subroot.Left = node;
else Add(subroot.Left, node);
}
}

Слайд 29

public void Add(T value)
{
TreeNode node = new TreeNode(value);
if (root

== null) root = node;
else Add(root, node);
}
private void Add(TreeNode subroot, TreeNode node )
{
if (subroot.Value.CompareTo( node.Value ) <= 0)
{
if (subroot.Right == null) subroot.Right = node;
else Add(subroot.Right, node);
}
if (subroot.Value.CompareTo( node.Value ) > 0)
{
if (subroot.Left == null) subroot.Left = node;
else Add(subroot.Left, node);
}
}

Слайд 30

Поиск значения public TreeNode Find(T value)

Слайд 31

Поиск значения public TreeNode Find(T value)
public TreeNode Find(T value)
{
if (root ==

null) return null;
if (root.Value == value) return root;
if (value < root.Value) return Find(value, root.Left );
if (value > root.Value) return Find(value, root.Right);
}
private TreeNode Find(T value, TreeNode subroot)
{ if (subroot == null) return null;
if (subroot.Value == value) return subroot;
if (value < subroot.Value) return Find(value, subroot.Left);
if (value > subroot.Value) return Find(value, subroot.Right);
}

Слайд 32

Поиск значения public TreeNode Find(T value)
public TreeNode Find(T value)
{
return Find(value, root);

}
private TreeNode Find(T value, TreeNode subroot)
{ if (subroot == null) return null;
if (value == subroot.Value) return subroot;
if (value < subroot.Value) return Find(value, subroot.Left);
if (value > subroot.Value) return Find(value, subroot.Right);
}

Слайд 33

Поиск значения public TreeNode Find(T value)
public TreeNode Find(T value)
{
return Find(value, root);

}
private TreeNode Find(T value, TreeNode subroot)
{ if (subroot == null) return null;
if (value.CompareTo(subroot.Value) == 0) return subroot;
if (value.CompareTo(subroot.Value) < 0) return Find(value, subroot.Left);
if (value.CompareTo(subroot.Value) > 0) return Find(value, subroot.Right);
}

Слайд 34

Симметричный обход string LNR()
10
20
40
50
60
70

Слайд 35

Симметричный обход string LNR()
public string LNR()
{
return LNR(root);
}
private string LNR(TreeNode

subroot)
{ if (subroot == null) return “”;
return LNR(subroot.Left)
+ “ ”
+ subroot.Value.ToString()
+ “ ”
+ LNR(subroot.Right);
}

Слайд 36

Прямой обход string NLR()
40
20
10
60
50
70

Слайд 37

Прямой обход string NLR()
public string NLR()
{
return NLR(root);
}
private string NLR(TreeNode

subroot)
{ if (subroot == null) return “”;
return subroot.Value.ToString()
+ “ ”
+ NLR(subroot.Left)
+ “ ”
+ NLR(subroot.Right);
}

Слайд 38

Обратный обход string ???()
?
?
?
?
?
?

Слайд 39

Обратный обход string LRN()
10
20
50
70
60
40

Слайд 40

Обратный обход string LRN()
public string LRN()
{
return LRN(root);
}
private string LRN(TreeNode

subroot)
{ if (subroot == null) return “”;
return LRN(subroot.Left)
+ “ ”
+ LRN(subroot.Right)
+ “ ”
+ subroot.Value.ToString();
}

Слайд 41

Вычисление глубины дерева int GetDeep()
1
1
0

Слайд 42

Вычисление глубины дерева int GetDeep()
2
1
0
1
1
1
1

Слайд 43

Вычисление глубины дерева int GetDeep()
2
1
0
1
1
2
1

Слайд 44

Вычисление глубины дерева int GetDeep()
2
1
0
3
1
2
1

Слайд 45

2
1
0
3
1
2
1
Вычисление глубины дерева int GetDeep()
public int GetDeep()
{
return GetDeep(root);
}
private int

GetDeep(TreeNode subroot)
{
if (subroot == null) return 0;
return 1 + Math.Max(GetDeep(subroot.Left),
GetDeep(subroot.Right));
}

Слайд 46

Вычисление количества листьев int GetLeafs()
public int GetLeafs()
{
return GetLeafs(root);
}
private int

GetLeafs(TreeNode subroot)
{
if (subroot == null) return 0;
if (subroot.Left == null &&
subroot.Right == null) return 1;
return GetLeafs(subroot.Left) +
GetLeafs(subroot.Right);
}

Слайд 47

Вычисление количества узлов int GetNodes()
public int GetNodes()
{
return GetNodes(root);
}
private int

GetNodes(TreeNode subroot)
{
if (subroot == null) return 0;
return 1 +
GetNodes(subroot.Left) +
GetNodes(subroot.Right);
}

Слайд 48

Если это лист
Если у этого узла одно поддерево
Если у этого узла

два поддерева

Удаление узла дерева void Remove(T value)

Слайд 49

Удаление узла дерева Если это лист
public void Remove(T value)
{
return

Remove(value, root);
}
private void Remove(T value, TreeNode subroot)
{
if (subroot == null) return;
if (subroot.Left != null && subroot.Left.Value == value)
{
if (subroot.Left.Left == null && subroot.Left.Right == null)
{ subroot.Left = null; return; }
}
if (subroot.Right != null && subroot.Right.Value == value)
{
if (subroot.Right.Left == null && subroot.Right.Right == null)
{ subroot.Right = null; return; }
}
if (subroot.Value < value) Remove(value, subroot.Right);
if (subroot.Value > value) Remove(value, subroot.Left);
}

Слайд 50

Удаление узла Если одно поддерево
private void Remove(T value, TreeNode subroot)
{

if (subroot == null) return;
TreeNode subtree = null;
if (subroot.Left != null && subroot.Left.Value == value)
{
if (subroot.Left.Left == null && subroot.Left.Right == null){…}
if (subroot.Left.Left == null) subtree = subroot.Left.Right;
if (subroot.Left.Right == null) subtree = subroot.Left.Left;
if (subtree != null) { subroot.Left = subtree; return;}
}
if (subroot.Right != null && subroot.Right.Value == value)
{
if (subroot.Right.Left == null && subroot.Right.Right == null){…}
if (subroot.Right.Left == null) subtree = subroot.Right.Right;
if (subroot.Right.Right == null) subtree = subroot.Right.Left;
if (subtree != null) { subroot.Right = subtree; return;}
}
if (subroot.Value < value) Remove(value, subroot.Right);
if (subroot.Value > value) Remove(value, subroot.Left);
}

Слайд 51

Удаление узла Если два поддерева
private void Remove(T value, TreeNode subroot)
{

if (subroot == null) return; TreeNode subtree = null;
if (subroot.Left != null && subroot.Left.Value == value)
{
… //если лист или одно поддерево
subtree = subroot.Left.Left;
subroot.Left = subroot.Left.Right;
TreeNode min = subroot.Left;
while (min.Left!=null) min = min.Left;
min.Left = subtree; return;
}
if (subroot.Right != null && subroot.Right.Value == value)
{
… //если лист или одно поддерево
subtree = subroot.Right.Left;
subroot.Right = subroot.Right.Right;
TreeNode min = subroot.Right;
while (min.Left!=null) min = min.Left;
min.Left = subtree; return;
}
if (subroot.Value < value) Remove(value, subroot.Right);
if (subroot.Value > value) Remove(value, subroot.Left);
}

Слайд 52

Удаление узла
public void Remove(T value)
{
return Remove(value, root);
}
private

void Remove(T value, TreeNode subroot)
{
if (subroot == null) return; TreeNode subtree = null;
if (subroot.Left != null && subroot.Left.Value == value)
{
if (subroot.Left.Left == null && subroot.Left.Right == null)
{ subroot.Left = null; return; }
if (subroot.Left.Left == null) subtree = subroot.Left.Right;
if (subroot.Left.Right == null) subtree = subroot.Left.Left;
if (subtree != null) { subroot.Left = subtree; return;}
subtree = subroot.Left.Left;
subroot.Left = subroot.Left.Right;
TreeNode min = subroot.Left;
while (min.Left!=null) min = min.Left;
min.Left = subtree; return;
}
if (subroot.Right != null && subroot.Right.Value == value)
{
…
}
if (subroot.Value < value) Remove(value, subroot.Right);
if (subroot.Value > value) Remove(value, subroot.Left);
}

Слайд 53

Удаление узла Если корень
public void Remove(T value)
{
return Remove(value, root);

}
private void Remove(T value, TreeNode subroot)
{
if (subroot == null) return; TreeNode subtree = null;
if (subroot.Left != null && subroot.Left.Value == value)
{
if (subroot.Left.Left == null && subroot.Left.Right == null)
{ subroot.Left = null; return; }
if (subroot.Left.Left == null) subtree = subroot.Left.Right;
if (subroot.Left.Right == null) subtree = subroot.Left.Left;
if (subtree != null) { subroot.Left = subtree; return;}
subtree = subroot.Left.Left;
subroot.Left = subroot.Left.Right;
TreeNode min = subroot.Left;
while (min.Left!=null) min = min.Left;
min.Left = subtree; return;
}
if (subroot.Right != null && subroot.Right.Value == value)
{
…
}
if (subroot.Value < value) Remove(value, subroot.Right);
if (subroot.Value > value) Remove(value, subroot.Left);
}

Слайд 54

public void Remove(T value)
{
if (root != null &&

root.Value == value)
{
if (root.Left == null && root.Right == null)
{ root = null; return; }
if (root.Left == null) { root = root.Right; return; }
if (root.Right == null) { root = root.Left; return; }
TreeNode subtree = root.Left;
root = root.Right;
TreeNode min = root;
while (min.Left!=null) min = min.Left;
min.Left = subtree;
return;
}
return Remove(value, root);
}
private void Remove(T value, TreeNode subroot)
{
if (subroot == null) return; TreeNode subtree = null;
if (subroot.Left != null && subroot.Left.Value == value)
{ … }
if (subroot.Right != null && subroot.Right.Value == value)
{ … }
if (subroot.Value < value) Remove(value, subroot.Right);
if (subroot.Value > value) Remove(value, subroot.Left);
}

Слайд 55

public void Remove(T value)
{
if (root != null &&

Слайд 56

public void Remove(T value)
{
if (root != null &&

Слайд 57

public void Remove(T value)
{
if (root != null &&

Слайд 58

public class TreeNode> {
T value; TreeNode left; TreeNode

right; TreeNode parent; public TreeNode(T value) { this.value = value; } public T getValue() { return value; } public TreeNode getLeft() { return left; } public void setLeft(TreeNode left) { this.left = left; } public TreeNode getRight() { return right; } public void setRight(TreeNode right) { this.right = right; } public TreeNode getParent() { return parent; }
public void setParent(TreeNode parent) { this.parent = parent; } }

А если добавить родительский узел? (JAVA)

Слайд 59

public class MyTree> {
TreeNode root; public void Delete(T

value){ … } private void Delete(???) { … } }

Слайд 60

public void Delete(T value){ if (root == null) return; if

(root.getValue() == value) { if (root.getLeft() == null && root.getRight() == null) { root = null; return; } if (root.getLeft() == null) { root = root.getRight(); root.setParent(null); return; } if (root.getRight() == null) { root = root.getLeft(); root.setParent(null); return; } TreeNode subtree = root.getLeft(); root = root.getRight(); root.setParent(null); TreeNode min = root; while (min.getLeft()!=null) min = min.getLeft(); min.setLeft(subtree); subtree.setParent(min); } else … } private void Delete(???) { … }

Слайд 61

public void Delete(T value){ if (root == null) return; if

Слайд 62

private void Delete(T value, TreeNode subroot, boolean isLeft) { if (subroot

== null) return; if (subroot.getValue() == value) { if (subroot.getLeft() == null && subroot.getRight() == null) { if (isLeft) subroot.getParent().setLeft(null); else subroot.getParent().setRight(null); return; } if (subroot.getLeft() == null) { subroot.getRight().setParent(subroot.getParent()); if (isLeft) subroot.getParent().setLeft(subroot.getRight()); else subroot.getParent().setRight(subroot.getRight()); return; } if (subroot.getRight() == null) { subroot.getLeft().setParent(subroot.getParent()); if (isLeft) subroot.getParent().setLeft(subroot.getLeft()); else subroot.getParent().setRight(subroot.getLeft()); return; } TreeNode subtree = subroot.getLeft(); TreeNode min = subroot.getRight(); subroot.getRight().setParent(subroot.getParent()); if (isLeft) subroot.getParent().setLeft(subroot.getRight()); else subroot.getParent().setRight(subroot.getRight()); while (min.getLeft()!=null) min = min.getLeft(); min.setLeft(subtree); subtree.setParent(min); } else if (value.compareTo(subroot.getValue())>=0) Delete(value, subroot.getRight(), false); else if (value.compareTo(subroot.getValue())<0) Delete(value, subroot.getLeft(), true); }

Слайд 63

АВЛ-дерево
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота

её двух поддеревьев различается не более чем на 1.
АВЛ — аббревиатура, образованная первыми буквами фамилий создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича.

Слайд 64

Максимальная высота АВЛ-дерева при заданном числе узлов

Слайд 65

Дерево Фибоначчи
Дерево Фибоначчи — АВЛ-дерево с наименьшим числом вершин при заданной

высоте (глубине).
Если для какой-либо из вершин высота поддерева, для которого эта вершина является корнем, равна h, то правое и левое поддерево этой вершины имеют высоты равные соответственно h-1 и h-2 или h-2 и h-1 . Каждое поддерево дерева Фибоначчи также является деревом Фибоначчи.
Пустое дерево — дерево Фибоначчи высоты 0.
Дерево с одной вершиной — дерево Фибоначчи высоты 1.

Слайд 66

Дерево Фибоначчи

Слайд 67

Балансировка
Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот

левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.

Слайд 68

Правый поворот (малое правое вращение)
Данное вращение используется тогда, когда:
(высота b-поддерева — высота R)

= 2
высота С <= высота L.

Слайд 69

Правый поворот (малое правое вращение)
private TreeNode RightRotate(TreeNode subroot) { TreeNode b =

subroot.Left; subroot.Left = b.Right; b.Right = subroot; return b; }

Слайд 70

Левый поворот (малое левое вращение)
Данное вращение используется тогда, когда:
(высота b-поддерева — высота L)

= 2
высота С <= высота R.

Слайд 71

Левый поворот (малое левое вращение)
private TreeNode LeftRotate(TreeNode subroot) { TreeNode b =

subroot.Right; subroot.Right = b.Left; b.setLeft = subroot; return b; }

Слайд 72

Большой левый поворот (большое левое вращение)
Данное вращение используется тогда, когда
(высота b-поддерева — высота

L) = 2
высота c-поддерева > высота R.

Слайд 73

Большой левый поворот (большое левое вращение)

Слайд 74

Большой левый поворот (большое левое вращение)
subroot.Right = RightRotate(subroot.Right); return LeftRotate(subroot);

Слайд 75

Большой правый поворот (большое правое вращение)
Данное вращение используется тогда, когда
(высота b-поддерева — высота

R) = 2
высота c-поддерева > высота L.

Слайд 76

Большой правый поворот (большое правое вращение)
subroot.Left = LeftRotate(subroot.Left); return RightRotate(subroot);

Слайд 77

Балансировка узла
TreeNode Balance(TreeNode subroot) // балансировка узла p { if( (GetHeight(subroot.getRight()) -

GetHeight(subroot.getLeft()))==2 ) { if( GetHeight(subroot.getRight().getLeft())
> GetHeight(subroot.getRight().getRight()) ) subroot.setRight(RightRotate(subroot.getRight())); return LeftRotate(subroot); } if( (GetHeight(subroot.getRight()) - GetHeight(subroot.getLeft()))==-2 ) { if( GetHeight(subroot.getLeft().getRight())
> GetHeight(subroot.getLeft().getLeft()) ) subroot.setLeft(LeftRotate(subroot.getLeft())); return RightRotate(subroot); } return subroot; // балансировка не нужна }

Слайд 78

Удаление узла из АВЛ дерева

Слайд 79

Удаление узла из АВЛ дерева
// поиск узла с минимальным ключом в

поддереве
TreeNode GetMin(TreeNode subroot) { if (subroot.Left == null) return subroot; return GetMin(subroot.Left); }
// удаление узла с минимальным ключом из поддерева TreeNode RemoveMin(TreeNode subroot) { if( subroot.Left == null ) return subroot.Right; subroot.Left = RemoveMin(subroot.Left); return Balance(subroot); }

Слайд 80

Удаление узла из АВЛ дерева
TreeNode Remove(TreeNode subroot, T value) // удаление

значения из поддерева { if( subroot == null ) return null; if( value.СompareTo(subroot.Value) < 0) subroot.Left = Remove(subroot.Left, value); else if( value.СompareTo(subroot.Value) > 0) subroot.Right = Remove(subroot.Right, value)); else // нашли тот узел, который надо удалить { TreeNode l = subroot.Left; TreeNode r = subroot.Right; if( r == null ) return l; TreeNode min = GetMin(r); min.Right = RemoveMin(r); min.Left = l; return Balance(min); } return Balance(subroot); }

Слайд 81

Деревья. Лекция 8

Содержание

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных

Синтаксическое дерево – это дерево в котором внутренние вершины это операторы

Генеалогическое древо

Логические файловые системыДеревья используются в файловых системах ОС.

Префиксное дерево – это дерево содержащее все суффиксы некоторой строки и

Деревья решений (decition trees) используются в классификации

ОпределенияКорневой узел, корень дерева — самый верхний узел дерева.Корень поддерева — одна из

ОпределенияПоддерево — часть древообразной структуры данных, которая может быть представлена в виде

ОпределенияЛист, листовой или терминальный узел — узел, не имеющий дочерних элементов;Внутренний узел —

ОпределенияЛист, листовой или терминальный узел — узел, не имеющий дочерних элементов;Внутренний узел —

ОпределенияГлубина дерева – длина самого длинного пути от корня до листа.Каждое дерево обладает

ОпределенияОбход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только

ОпределенияТри наиболее часто используемых способа обхода дерева:прямой;симметричный;обратный.

Бинарное дерево – это дерево, в котором каждый узел имеет не

Бинарное дерево поиска – это бинарное дерево, в котором справедливо следующее: Оба

Реализация бинарного дерева поиска

Реализация бинарного дерева поиска

Реализация бинарного дерева поискаДвоичное дерево состоит из узлов (вершин) — записей вида

Реализация бинарного дерева поиска Данные (data) обладают ключом (key), на котором

Класс узла дерева – TreeNode class TreeNode where T: IComparable{ T

Класс дерева – MyTree Добавление узла в деревоПоиск значенияУдаление узла из

Класс дерева – MyTree class MyTree where T: IComparable{ TreeNode root; public

Добавление узла в дерево void Add(T value)public void Add(T value){ TreeNode node

Добавление узла в дерево void Add(T value)public void Add(T value){ TreeNode node

Добавление узла в дерево void Add(T value)public void Add(T value){ TreeNode node

Добавление узла в дерево void Add(T value)public void Add(T value){ TreeNode node

public void Add(T value){ TreeNode node = new TreeNode(value); if (root

public void Add(T value){ TreeNode node = new TreeNode(value); if (root

Поиск значения public TreeNode Find(T value)

Поиск значения public TreeNode Find(T value)public TreeNode Find(T value){ if (root ==

Поиск значения public TreeNode Find(T value)public TreeNode Find(T value){ return Find(value, root);

Поиск значения public TreeNode Find(T value)public TreeNode Find(T value){ return Find(value, root);

Симметричный обход string LNR()102040506070

Симметричный обход string LNR()public string LNR() { return LNR(root); }private string LNR(TreeNode

Прямой обход string NLR()402010605070

Прямой обход string NLR()public string NLR() { return NLR(root); }private string NLR(TreeNode

Обратный обход string ???()??????

Обратный обход string LRN()102050706040

Обратный обход string LRN()public string LRN() { return LRN(root); }private string LRN(TreeNode

Вычисление глубины дерева int GetDeep()110

Вычисление глубины дерева int GetDeep()2101111

Вычисление глубины дерева int GetDeep()2101121

Вычисление глубины дерева int GetDeep()2103121

2103121Вычисление глубины дерева int GetDeep()public int GetDeep() { return GetDeep(root); }private int

Вычисление количества листьев int GetLeafs()public int GetLeafs() { return GetLeafs(root); }private int

Вычисление количества узлов int GetNodes()public int GetNodes() { return GetNodes(root); }private int

Если это листЕсли у этого узла одно поддеревоЕсли у этого узла

Удаление узла дерева Если это листpublic void Remove(T value) { return

Удаление узла Если одно поддеревоprivate void Remove(T value, TreeNode subroot){

Удаление узла Если два поддереваprivate void Remove(T value, TreeNode subroot){

Удаление узла public void Remove(T value) { return Remove(value, root); }private

Удаление узла Если кореньpublic void Remove(T value) { return Remove(value, root);

public void Remove(T value) { if (root != null &&

public void Remove(T value) { if (root != null &&

public void Remove(T value) { if (root != null &&

public void Remove(T value) { if (root != null &&

public class TreeNode> { T value; TreeNode left; TreeNode

public class MyTree> { TreeNode root; public void Delete(T

public void Delete(T value){ if (root == null) return; if

public void Delete(T value){ if (root == null) return; if

private void Delete(T value, TreeNode subroot, boolean isLeft) { if (subroot

АВЛ-деревоАВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота

Максимальная высота АВЛ-дерева при заданном числе узлов

Дерево ФибоначчиДерево Фибоначчи — АВЛ-дерево с наименьшим числом вершин при заданной

Дерево Фибоначчи

БалансировкаОтносительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот

Правый поворот (малое правое вращение)Данное вращение используется тогда, когда:(высота b-поддерева — высота R)

Правый поворот (малое правое вращение)private TreeNode RightRotate(TreeNode subroot) { TreeNode b =

Левый поворот (малое левое вращение)Данное вращение используется тогда, когда:(высота b-поддерева — высота L)

Левый поворот (малое левое вращение)private TreeNode LeftRotate(TreeNode subroot) { TreeNode b =

Большой левый поворот (большое левое вращение)Данное вращение используется тогда, когда (высота b-поддерева — высота

Большой левый поворот (большое левое вращение)

Большой левый поворот (большое левое вращение)subroot.Right = RightRotate(subroot.Right); return LeftRotate(subroot);

Большой правый поворот (большое правое вращение)Данное вращение используется тогда, когда (высота b-поддерева — высота

Логические файловые системы
Деревья используются в файловых системах ОС.

Определения
Корневой узел, корень дерева — самый верхний узел дерева.
Корень поддерева — одна из

Определения
Поддерево — часть древообразной структуры данных, которая может быть представлена в виде

Определения
Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов;
Внутренний узел —

Определения
Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов;
Внутренний узел —

Определения
Глубина дерева – длина самого длинного пути от корня до листа.
Каждое дерево обладает

Определения
Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только

Определения
Три наиболее часто используемых способа обхода дерева:
прямой;
симметричный;
обратный.

Бинарное дерево поиска – это бинарное дерево, в котором справедливо следующее:
Оба

Реализация бинарного дерева поиска
Двоичное дерево состоит из узлов (вершин) — записей вида

Реализация бинарного дерева поиска
Данные (data) обладают ключом (key), на котором

Класс узла дерева – TreeNode
class TreeNode where T: IComparable
{
T

Класс дерева – MyTree
Добавление узла в дерево
Поиск значения
Удаление узла из

Класс дерева – MyTree
class MyTree where T: IComparable
{
TreeNode root;
public

Добавление узла в дерево void Add(T value)
public void Add(T value)
{
TreeNode node

Добавление узла в дерево void Add(T value)
public void Add(T value)
{
TreeNode node

Добавление узла в дерево void Add(T value)
public void Add(T value)
{
TreeNode node

Добавление узла в дерево void Add(T value)
public void Add(T value)
{
TreeNode node

public void Add(T value)
{
TreeNode node = new TreeNode(value);
if (root

public void Add(T value)
{
TreeNode node = new TreeNode(value);
if (root

Поиск значения public TreeNode Find(T value)
public TreeNode Find(T value)
{
if (root ==

Поиск значения public TreeNode Find(T value)
public TreeNode Find(T value)
{
return Find(value, root);

Поиск значения public TreeNode Find(T value)
public TreeNode Find(T value)
{
return Find(value, root);

Симметричный обход string LNR()
10
20
40
50
60
70

Симметричный обход string LNR()
public string LNR()
{
return LNR(root);
}
private string LNR(TreeNode

Прямой обход string NLR()
40
20
10
60
50
70

Прямой обход string NLR()
public string NLR()
{
return NLR(root);
}
private string NLR(TreeNode

Обратный обход string ???()
?
?
?
?
?
?

Обратный обход string LRN()
10
20
50
70
60
40

Обратный обход string LRN()
public string LRN()
{
return LRN(root);
}
private string LRN(TreeNode

Вычисление глубины дерева int GetDeep()
1
1
0

Вычисление глубины дерева int GetDeep()
2
1
0
1
1
1
1

Вычисление глубины дерева int GetDeep()
2
1
0
1
1
2
1

Вычисление глубины дерева int GetDeep()
2
1
0
3
1
2
1

2
1
0
3
1
2
1
Вычисление глубины дерева int GetDeep()
public int GetDeep()
{
return GetDeep(root);
}
private int

Вычисление количества листьев int GetLeafs()
public int GetLeafs()
{
return GetLeafs(root);
}
private int

Вычисление количества узлов int GetNodes()
public int GetNodes()
{
return GetNodes(root);
}
private int

Если это лист
Если у этого узла одно поддерево
Если у этого узла

Удаление узла дерева Если это лист
public void Remove(T value)
{
return

Удаление узла Если одно поддерево
private void Remove(T value, TreeNode subroot)
{

Удаление узла Если два поддерева
private void Remove(T value, TreeNode subroot)
{

Удаление узла
public void Remove(T value)
{
return Remove(value, root);
}
private

Удаление узла Если корень
public void Remove(T value)
{
return Remove(value, root);

public void Remove(T value)
{
if (root != null &&

public void Remove(T value)
{
if (root != null &&

public void Remove(T value)
{
if (root != null &&

public void Remove(T value)
{
if (root != null &&

public class TreeNode> {
T value; TreeNode left; TreeNode

public class MyTree> {
TreeNode root; public void Delete(T

АВЛ-дерево
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота

Дерево Фибоначчи
Дерево Фибоначчи — АВЛ-дерево с наименьшим числом вершин при заданной

Балансировка
Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот

Правый поворот (малое правое вращение)
Данное вращение используется тогда, когда:
(высота b-поддерева — высота R)

Правый поворот (малое правое вращение)
private TreeNode RightRotate(TreeNode subroot) { TreeNode b =

Левый поворот (малое левое вращение)
Данное вращение используется тогда, когда:
(высота b-поддерева — высота L)

Левый поворот (малое левое вращение)
private TreeNode LeftRotate(TreeNode subroot) { TreeNode b =

Большой левый поворот (большое левое вращение)
Данное вращение используется тогда, когда
(высота b-поддерева — высота

Большой левый поворот (большое левое вращение)
subroot.Right = RightRotate(subroot.Right); return LeftRotate(subroot);

Большой правый поворот (большое правое вращение)
Данное вращение используется тогда, когда
(высота b-поддерева — высота