Лекция 3. Тема 14. Связанные динамические структуры данных

1.

Выделение памяти для строк
Постановка задачи
Записать в итоговую строку последние слова
каждого предложения исходной строки.
Уточнение
Необходимо собрать строку заранее неизвестной
длины из частей (букв или слов).
Способы решения
1) Оценить максимально возможную длину строки и
выделить память
- избыточно по памяти
2) Реализовать алгоритм дважды – первый проход
только считает какой длины строка будет получаться,
второй проход собирает строку
- избыточно по усилиям
программиста
3) При добавлении в строку очередного слова/буквы
перевыделять память…
Левкович Н.В.
2022/2023
1

2.

Выделение памяти для строк
3) При добавлении в строку очередного слова/буквы
перевыделять память…
p e r
p e r
a s p e r a
p e r
a s p e r a
a d
p e r
a s p e r a
a d
a s t r a
Какова сложность сбора строки длины N символов?
(для упрощения оценки считать, что буквы добавляются по одной,
выделением и освобождением памяти пренебречь)
(N2)
Левкович Н.В.
2022/2023
2

3.

Выделение памяти для строк
4) Исходно выделяем память с запасом, а если при очередном
добавлении памяти не хватает – перевыделяем память с избытком:
p e r
a
p e r
a s p e r a
p e r
a s p e r a
Добавление в строку символа
таким способом имеет
константную сложность
(хотя для некоторых символов
времени требуется существенно
больше чем для других)
a d
a s t r a \0
Какова сложность сборки строки длины N символов?
(для упрощения оценки считать, что буквы добавляются по одной,
выделением и освобождением памяти пренебречь) (~N)
Какова сложность
Такой класс сложности называют
добавления 1 символа
в строку в среднем? (~1) амортизированная константная сложность
Левкович Н.В.
2022/2023
3

4.

Раздел 3. Процедурное программирование
Тема 7. Введение в процедурное и структурное программирование
Тема 8. Управляющие инструкции
Тема 9. Базовые структуры данных
Тема 10. Управление памятью
Тема 11. Функции
Тема 12. Асимптотическая оценка сложности алгоритмов
Тема 13. Рекурсия
Тема 14. Связанные динамические
структуры данных
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
4

5.

Связанные динамические
структуры данных
Динамические структуры данных служат для хранения
набора однотипных структур.
Как и обычный массив, они обеспечивают следующие
операции:
• обращение к элементам по индексу
• последовательный перебор всех элементов
• поиск среди набора элементов по какому-либо ключу
В отличии от обычного массива они позволяют:
• работать с коллекциями переменного размера
• добавить новый элемент в произвольную позицию
• удалить произвольной элемент
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
5

6.

Связанные динамические
структуры данных
Разные виды связанных динамических структур
обеспечивают разную скорость выполнения
базовых операций.
Некоторые операции в принципе не
поддерживаются некоторыми динамическими
структурами.
Конкретный тип динамический структуры для
реализации алгоритма выбирается так, чтобы
наиболее часто используемые операции
выполнялись этим типом максимально быстро.
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
6

7.

Связанные динамические
структуры данных: списки
Самая простая реализация списка – на основе массива:
struct MyArray
{
MyPayload* vNodes; // массив в динамической памяти
int nMaxElemCnt; // размер массива vNodes
int nCurElemCnt; // количество используемых ячеек vNodes
};
void Create(MyArray& arr, int maxElemCnt);
void Delete(MyArray& arr);
void Print(const MyArray& arr);
void AddElement(MyArray& arr, const MyPayload& a);
bool DeleteElement(MyArray& arr, MyPayload* p);
MyPayload* FindElement(MyArray& arr, int id);
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
7

8.

Связанные динамические
структуры данных: списки
Payload - "полезная нагрузка", один элемент, хранимый в
нашей динамической структуре:
struct MyPayload
{
int ID;
string sData;
};
void Print(const MyPayload& item)
{
cout << item.ID << ": " << item.sData << endl;
}
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
8

9.

Cписки на основе массива
void Create(MyArray& arr, int maxElemCnt)
{
arr.nMaxElemCnt = maxElemCnt;
arr.vNodes = new MyPayload[maxElemCnt];
arr.nCurElemCnt = 0;
}
void Delete(MyArray& arr)
{
delete[] arr.vNodes;
arr.vNodes = nullptr;
}
void Print(const MyArray& arr)
{
for (int i = 0; i < arr.nCurElemCnt; i++)
Print(arr.vNodes[i]);
}
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
9

10.

Cписки на основе массива
void AddElement(MyArray& arr, const MyPayload& a)
{
if (arr.nCurElemCnt == arr.nMaxElemCnt)
throw;
arr.vNodes[arr.nCurElemCnt] = a;
arr.nCurElemCnt++;
}
MyPayload* FindElement(MyArray& arr, int id)
{
for (int i = 0; i < arr.nCurElemCnt; i++)
if (arr.vNodes[i].ID == id)
return &arr.vNodes[i];
return nullptr;
}
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
10

11.

Cписки на основе массива
bool DeleteElement(MyArray& arr, MyPayload* p)
{
if (!p)
return;
int index = p - arr.vNodes;
if (index < 0 || index >= arr.nCurElemCnt)
return false; // элемент находится вне массива
for (int i = index + 1; i < arr.nCurElemCnt; i++)
arr.vNodes[i - 1] = arr.vNodes[i];
arr.nCurElemCnt--;
return true; // элемент удалён
}
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
11

12.

Односвязные списки
struct MyList
{
Node* pHead; // указатель на первый элемент
Node* pTail; // указатель на последний элемент
int nNodesCnt; // общее количество элементов
};
// один элемент списка
struct Node
{
MyPayload Payload; // полезная нагрузка
Node* pNext;
};
pHead
(голова
списка)
Левкович Н.В.
pTail
(хвост списка)
Node
Node
Node
Node
Payload
Payload
Payload
Payload
pNext
pNext
pNext
pNext
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
12

13.

Односвязные списки
// методы, необходимые для реализации динамической структуры
void Create(MyList& lst);
void Delete(MyList& lst);
void Print(const MyList& lst);
void AddElement(MyList& lst, const MyPayload& a);
void DeleteElement(Node* pPrevNode);
Node* FindElement(MyList& lst, int id);
// полезная нагрузка такая же, как в прошлом примере
struct MyPayload
{
int ID;
string sData;
};
void Print(const MyPayload& item)
{
cout << item.ID << ": " << item.sData << endl;
}
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
13

14.

Односвязные списки
void Create(MyList& lst)
{
lst.pHead = nullptr;
}
void Delete(MyList& lst)
{
while (lst.pHead)
{
Node* p = lst.pHead;
pHead = p->pNext;
delete p;
}
lst.pHead = nullptr;
}
void Print(const MyList& lst)
{
for (Node* p = lst.pHead; p != nullptr; p = p->pNext)
Print(p->Payload);
}
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
14

15.

Односвязные списки: вставка вершины
в конец списка
новый элемент
Node* pNewNode
предыдущий элемент
Node* pPrevNode
Node
Payload
pNext
pHead
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
nullptr
вставка в конец
списка
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
15

16.

Односвязные списки: вставка вершины
в конец списка
pNewNode->pNext = nullptr;
pPrevNode->pNext = pNewNode;
новый элемент
Node* pNewNode
предыдущий элемент
Node* pPrevNode
Node
Payload
pNext
pHead
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
nullptr
вставка в конец
списка
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
16

17.

Односвязные списки: вставка вершины
в начало списка
новый элемент
Node* pNewNode
Node
Payload
pNext
pHead
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
nullptr
вставка в начало
списка
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
17

18.

Односвязные списки: вставка вершины
в начало списка
pNewNode->pNext = pHead;
pHead = pNewNode;
новый элемент
Node* pNewNode
Node
Payload
pNext
pHead
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
nullptr
вставка в начало
списка
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
18

19.

Односвязные списки: вставка вершины
в произвольную позицию
новый элемент
Node* pNewNode
Node
Payload
предыдущий элемент
Node* pPrevNode
pHead
pNext
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
nullptr
вставка между
этими элементами
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
19

20.

Односвязные списки: вставка вершины
pNewNode->pNext = pPrevNode->pNext;
pPrevNode->pNext = pNewNode;
новый элемент
Node* pNewNode
предыдущий элемент
Node* pPrevNode
Node
Payload
pNext
pHead
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
nullptr
вставка между
этими элементами
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
20

21.

Односвязные списки: удаление вершины
void DeleteElement(Node* pPrevElem)
{
Node* pNextEl = pPrevElem->pNext->pNext;
delete pPrevElem->pNext;
pPrevElem->pNext = pNextEl;
}
удаляемый элемент
pHead
Левкович Н.В.
Node
Node
Node
Node
Payload
Payload
Payload
Payload
pNext
pNext
pNext
pNext
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
21

22.

Односвязные списки: удаление вершины
void DeleteElement(Node* pPrevElem)
{
Node* pNextEl = pPrevElem->pNext->pNext;
delete pPrevElem->pNext;
pPrevElem->pNext = pNextEl;
}
удаляемый элемент
pPrevElem
Node
pNextEl
Payload
pNext
pHead
Левкович Н.В.
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
22

23.

Односвязные списки
void DeleteElement(Node* pPrevElem)
{
Node* pNextEl = pPrevElem->pNext->pNext;
delete pPrevElem->pNext;
pPrevElem->pNext = pNextEl;
}
удаляемый элемент
pPrevElem
Node
pNextEl
Payload
pNext
pHead
Левкович Н.В.
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
23

24.

Односвязные списки
void DeleteElement(Node* pPrevElem)
{
Node* pNextEl = pPrevElem->pNext->pNext;
delete pPrevElem->pNext;
pPrevElem->pNext = pNextEl;
}
pPrevElem
Node
pNextEl
Payload
pNext
pHead
Левкович Н.В.
Node
Node
Node
Payload
Payload
Payload
pNext
pNext
pNext
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
24

25.

Односвязные списки
void DeleteElement(Node* pPrevElem)
{
Node* pNextEl = pPrevElem->pNext->pNext;
delete pPrevElem->pNext;
pPrevElem->pNext = pNextEl;
}
pPrevElem
удаляемый
элемент
pNextEl
Head
Node
Node
Node
Node
Payload
Payload
Payload
Payload
pNext
pHead
pNext
pNext
pNext
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
25

26.

Односвязные списки
void DeleteElement(Node* pPrevElem)
{
Node* pNextEl = pPrevElem->pNext->pNext;
delete pPrevElem->pNext;
pPrevElem->pNext = pNextEl;
}
pPrevElem
удаляемый
элемент
pNextEl
Head
Node
Node
Node
Node
Payload
Payload
Payload
Payload
pNext
pHead
pNext
pNext
pNext
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
26

27.

Односвязные списки
void DeleteElement(Node* pPrevElem)
{
Node* pNextEl = pPrevElem->pNext->pNext;
delete pPrevElem->pNext;
pPrevElem->pNext = pNextEl;
}
pPrevElem
pNextEl
Head
Node
Node
Node
Payload
Payload
Payload
pNext
pHead
pNext
pNext
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
27

28.

Основные виды связанных
динамических структур данных
Кольцевые списки – имеют дополнительную связь между
первым и последним элементами.
Head
Node
Node
Node
Node
Payload
Payload
Payload
Payload
pNext
pNext
pNext
pNext
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
28

29.

Двусвязные списки
(голова списка)
(хвост списка)
Head
Node
Node
Node
Tail
Node
Payload
Payload
Payload
Payload
pPrev
pPrev
pPrev
pPrev
pNext
pNext
pNext
pNext
nullptr
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
29

30.

Основные виды связанных
динамических структур данных
Частные случай линейного списка:
Стек –– разрешено только 2 действия: добавление и удаление
элементов с одного конца (головы) стека.
Очередь – разрешено только 2 действия – добавление элементов
в конец (хвост) и удаление из начала (головы) списка.
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
30

31.

Стек и очередь
pTail
(хвост списка)
pHead
(голова
списка)
Левкович Н.В.
Node
Node
Node
Node
Payload
Payload
Payload
Payload
pNext
pNext
pNext
pNext
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
nullptr
31

32.

Связанные динамические структуры
данных: сложность операций
Массив
Односвязный
список
Двусвязный
список
Добавление элемента
в конец: быстро* O(1)
в середину: долго O(N)
быстро
O(1)
быстро
O(1)
Удаление элемента
долго
O(N)
быстро
O(1)
быстро
O(1)
Обращение по индексу
(для бинарного поиска)
быстро
O(1)
очень долго
O(N)
очень долго
O(N)
Поиск элемента по
ключу
быстро
O(log(N))
очень долго
O(N)
очень долго
O(N)
Реализация стека
возможна
возможна
возможна
Операция
Реализация очереди
Левкович Н.В.
2022/2023
не рациональна
возможна
возможна
* в пределах выделенного размера массива
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
32

33.

Связанные динамические
структуры данных
Графы
линейные
списки
деревья
односвязные
двусвязные
стек
очередь
Левкович Н.В.
2022/2023
бинарные
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
M-арные
33

34.

Связанные динамические
структуры данных: деревья
Вершина (vertex) или узел (node) — это простой объект, который
может иметь имя и содержать другую связанную с ним
информацию.
Ребро (edge) — это связь между двумя вершинами.
Путь (path) в графе — это список отдельных вершин, в котором
следующие друг за другом вершины соединяются ребрами.
Дерево (tree) — это непустая коллекция вершин и ребер, при этом
для любых двух узлов должен существовать единственный
соединяющий их путь.
Если между какой-либо парой узлов существует более одного пути
или если между какой-либо парой узлов путь отсутствует, мы
имеем граф, а не дерево.
Несвязанный набор деревьев называется бором (forest).
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
34

35.

Связанные динамические
структуры данных: деревья
Дерево с корнем (единственным, rooted) —
это дерево, в котором один узел назначен
корнем (root) дерева.
В дереве с корнем любой узел является
корнем поддерева, состоящего из него и
расположенных под ним узлов.
корень
Чаще всего термин дерево применяется к
деревьям с корнем, а термин свободное
дерево (free tree) — к более общим
структурам.
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
35

36.

Связанные динамические
структуры данных: деревья
Обычно корень дерева изображается сверху,
а под ним его дочерние узлы:
корень
узел
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
36

37.

Связанные динамические
структуры данных: деревья
Генеалогическая терминология:
узлы предки
корень
родительский
узел
узел
дочерние
узлы
Левкович Н.В.
2022/2023
родственные узлы
(на том же уровне)
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
37

38.

Связанные динамические
структуры данных: деревья
Узлы, не имеющие дочерних узлов, называются листьями
(leaves) или терминальными (оконечными, terminal) узлами.
корень
листья
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
38

39.

Связанные динамические
структуры данных: деревья
Уровень расположения узла – длина пути от него до корня
корень
2
узел
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
39

40.

Связанные динамические
структуры данных: деревья
высота дерева - число ребер в пути от корня до самого дальнего
из листьев
корень
4
узел
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
40

41.

Связанные динамические
структуры данных: деревья
Упорядоченное (ordered) дерево — это дерево с корнем,
в котором для каждого узла определен порядок следования
дочерних узлов.
Какое из приведенных деревьев упорядоченное?
корень
4
корень
20
2
1
1
6
3
2
Левкович Н.В.
3
5
4
2022/2023
5
9
7
6
2
7
1
5
6
7
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
41

42.

Связанные динамические
структуры данных: деревья
Бинарное дерево — дерево в котором каждый узел имеет
строго 2 потомков.
(некоторые из потомков могут быть заменены фиктивными
оконечными узлами - nullptr)
М-арное дерево — дерево в котором каждый узел имеет строго
M потомков
корень
Левкович Н.В.
2022/2023
корень
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
42

43.

Поиск узла дерева по ключу
корень
4
2
1
7
3
5
8
6
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
43

44.

Удаление узла дерева
Удаление листа – тривиально – просто заменяем указатель на
nullptr
корень
4
2
1
7
3
5
8
6
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
44

45.

Удаление узла дерева
Для удаления произвольного узла дерева:
1) сначала надо найти, чем его заменить, это может быть:
корень
4
2
7
1
1
Левкович Н.В.
2022/2023
3
2
3
5
4
5
8
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
45

46.

Удаление узла дерева
Для удаления произвольного узла дерева:
1) сначала найти чем его заменить, это может быть:
1.1) либо самый правый элемент левого поддерева
1.2) либо самый левый элемент правого поддерева
корень
4
2
7
1
1
Левкович Н.В.
2022/2023
3
2
3
5
4
5
8
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
46

47.

Удаление узла дерева
Для удаления произвольного узла дерева:
1) сначала найти чем его заменить, это может быть:
1.1) либо самый правый элемент левого поддерева
1.2) либо самый левый элемент правого поддерева
корень
4
2
7
1
1
Левкович Н.В.
2022/2023
3
2
3
5
4
5
8
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
47

48.

Удаление узла дерева
Для удаления произвольного узла дерева:
1) сначала найти чем его заменить, это может быть:
1.1) либо самый левый элемент правого поддерева
1.2) либо самый правый элемент левого поддерева
2) вставить вместо удаляемого элемента найденный в пункте 1
3) окончательно удалить удаляемый элемент
корень
4
2
7
1
1
Левкович Н.В.
2022/2023
3
2
3
5
4
5
8
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
48

49.

Удаление узла дерева
Для удаления произвольного узла дерева:
1) сначала найти чем его заменить, это может быть:
1.1) либо самый левый элемент правого поддерева
1.2) либо самый правый элемент левого поддерева
2) вставить вместо удаляемого элемента найденный в пункте 1
3) окончательно удалить удаляемый элемент
4
корень
5
2
7
1
1
Левкович Н.В.
2022/2023
3
2
3
8
5
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
49

50.

Удаление узла дерева
Для удаления произвольного узла дерева:
Усложним задачу – найденный
1) сначала найти чем его заменить, это может
быть:не лист.
элемент
1.1) либо самый левый элемент правого
поддерева
Как модифицировать
алгоритм?
1.2) либо самый правый элемент левого поддерева
2) вставить вместо удаляемого элемента найденный в пункте 1
3) окончательно удалить удаляемый элемент
корень
4
2
7
1
3
5
8
6
1
Левкович Н.В.
2022/2023
2
3
4
5
6
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
50

51.

Удаление узла дерева
Для удаления произвольного узла дерева:
1) сначала найти чем его заменить, это может быть:
1.1) либо самый левый элемент правого поддерева
1.2) либо самый правый элемент левого поддерева
2) удалить найденный в пункте 1 элемент из дерева рекурсивно
3) вставить вместо удаляемого элемента найденный в пункте 1
4) окончательно удалить удаляемый элемент
корень
4
2
7
1
3
5
8
6
1
Левкович Н.В.
2022/2023
2
3
4
5
6
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
51

52.

Удаление узла дерева
Для удаления произвольного узла дерева:
1) сначала найти чем его заменить, это может быть:
1.1) либо самый левый элемент правого поддерева
1.2) либо самый правый элемент левого поддерева
2) удалить найденный в пункте 1 элемент из дерева рекурсивно
3) вставить вместо удаляемого элемента найденный в пункте 1
4) окончательно удалить удаляемый элемент
корень
4
2
7
1
1
Левкович Н.В.
2022/2023
3
2
3
4
5
6
5
6
8
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
52

53.

Удаление узла дерева
Для удаления произвольного узла дерева:
1) сначала найти чем его заменить, это может быть:
1.1) либо самый левый элемент правого поддерева
1.2) либо самый правый элемент левого поддерева
2) удалить найденный в пункте 1 элемент из дерева рекурсивно
3) вставить вместо удаляемого элемента найденный в пункте 1
4) окончательно удалить удаляемый элемент
корень
5
2
7
1
1
Левкович Н.В.
2022/2023
3
2
3
6
5
6
8
7
8
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
53

54.

Вставка элемента в дерево
Для добавлении элемента в упорядоченное бинарное дерево:
1) его значение сравнивают со значением корневого узла, и
определяют в каком поддереве он должен находится
2) если выбранное поддерево пустое, на это место добавляется
новый элемент
3) если выбранное дерево не пустое, то алгоритм повторяют с
первого пункта для выбранного поддерева
4
2
1
Левкович Н.В.
5
6
3
2022/2023
7
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
54

55.

Вставка элемента в дерево
Для добавлении элемента в упорядоченное бинарное дерево:
1) его значение сравнивают со значением корневого узла, и
определяют в каком поддереве он должен находится
2) если выбранное поддерево пустое, на это место добавляется
новый элемент
3) если выбранное дерево не пустое, то алгоритм повторяют с
первого пункта для выбранного поддерева
4
2
1
Левкович Н.В.
5
6
3
2022/2023
4<5
=> правое поддерево
7
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
55

56.

Вставка элемента в дерево
Для добавлении элемента в упорядоченное бинарное дерево:
1) его значение сравнивают со значением корневого узла, и
определяют в каком поддереве он должен находится
2) если выбранное поддерево пустое, на это место добавляется
новый элемент
3) если выбранное дерево не пустое, то алгоритм повторяют с
первого пункта для выбранного поддерева
4
2
1
Левкович Н.В.
5
6
3
2022/2023
7
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
56

57.

Вставка элемента в дерево
Для добавлении элемента в упорядоченное бинарное дерево:
1) его значение сравнивают со значением корневого узла, и
определяют в каком поддереве он должен находится
2) если выбранное поддерево пустое, на это место добавляется
новый элемент
3) если выбранное дерево не пустое, то алгоритм повторяют с
первого пункта для выбранного поддерева
4
2
1
Левкович Н.В.
5
6
3
2022/2023
5<6
=> левое поддерево
7
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
57

58.

Вставка элемента в дерево
Для добавлении элемента в упорядоченное бинарное дерево:
1) его значение сравнивают со значением корневого узла, и
определяют в каком поддереве он должен находится
2) если выбранное поддерево пустое, на это место добавляется
новый элемент
3) если выбранное дерево не пустое, то алгоритм повторяют с
первого пункта для выбранного поддерева
4
2
1
5
6
3
7
больше узлов нет
=> нашли позицию
для вставки
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
58

59.

Вставка элемента в дерево
Для добавлении элемента в упорядоченное бинарное дерево:
1) его значение сравнивают со значением корневого узла, и
определяют в каком поддереве он должен находится
2) если выбранное поддерево пустое, на это место добавляется
новый элемент
3) если выбранное дерево не пустое, то алгоритм повторяют с
первого пункта для выбранного поддерева
4
2
1
Левкович Н.В.
6
3
5
2022/2023
7
Алгоритм вставки элемента в
дерево, по сути, полностью
совпадает с алгоритмом поиска
элемента в дереве, и очень похож
на алгоритм бинарного поиска.
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
59ё

60.

Вставка элемента в дерево
В зависимости от порядка вставки элементов, можно получить
деревья разной высоты
1
1
4
2
6
2
6
3
3
7
1 3
5 7
4
2
5
5
4
6
Какова минимальная и максимальная высота
бинарного дерева в зависимости от количества узлов N?
7
Hmin = floor( log2(N) )
Левкович Н.В.
2022/2023
Hmax = N - 1
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
60

61.

Сбалансированные деревья
Бинарное дерево сбалансировано, если для каждого узла
высота двух его поддеревьев отличается не более чем на 1.
Сбалансированное дерево не обязательно имеет минимальную
возможную высоту, но близко к этому.
Поддержание минимальной высоты дерева при операциях
вставки и удаления узлов требует существенных ресурсов
(каждое действие имеет сложность O(N)), поэтому чаще всего
ограничиваются субоптимальностью, например, как описано в
определении выше (тогда сложность O(log2(N)).
5
3
2
7
4
6
Сбалансировано
ли это дерево?
(да)
1
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
61

62.

Малый поворот дерева
левый
поворот
правый
поворот
d
b
b
d
E
A
A
C
C
E
A<b<C<d<E
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
62

63.

Малый поворот дерева
левый
поворот
правый
поворот
d
b
b
d
E
A
C
изменение высоты поддеревьев:
Левкович Н.В.
A
2022/2023
-1
C
E
0
+1
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
63

64.

Вращение дерева: упражнение
d
b
b
d
E
A
C
A
C
E
7
5
3
1
6
4
2
Левкович Н.В.
9
2022/2023
8
Сбалансировано ли это дерево?
В какую сторону будем
вращать?
Попробуйте повернуть
вправо?
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
64

65.

Вращение дерева: упражнение
d
b
b
d
E
C
A
C
5
1
4
3
9
6
E
5
7
3
A
8
1
7
4
2
9
6
8
2
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
65

66.

Большой поворот дерева
Большой поворот – это комбинация двух малых поворотов.
Большой правый поворот = малый левый + малый правый.
f
f
d
b
G
d
G
b
E
A
С
A
E
С
1) малый
левый поворот
A<b<C<d<E<f<G
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
66

67.

Большой поворот дерева
Большой поворот – это комбинация двух малых поворотов.
Большой правый поворот = малый левый + малый правый.
d
f
f
b
d
b
G
d
G
b
E
A
С
A
E
1) малый
левый поворот
f
A
С
E
С
2) малый
правый поворот
A<b<C<d<E<f<G
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
67
G

68.

Большой поворот дерева
Большой поворот – это комбинация двух малых поворотов.
Большой правый поворот = малый левый + малый правый.
d
f
b
b
G
d
A
A
С
С
E
G
-1
-1
+1
E
изменение высоты поддеревьев:
Левкович Н.В.
f
2022/2023
0
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
68

69.

Большой поворот дерева
Большой поворот – это комбинация двух малых поворотов.
Большой левый поворот = малый правый + малый левый.
d
b
b
f
A
d
G
С
A
С
E
G
+1
-1
-1
0
E
изменение высоты поддеревьев:
Левкович Н.В.
f
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
69

70.

Изменение высоты при вращении
1) Обозначим высоту левого поддерева как HL, а высоту правого как HR
2) При простой вставке (удалении) одного узла высота всех
поддеревьев бинарного дерева меняется не более чем на 1.
3) Если |HL - HR| ≤ 1,
то балансировка
вершины d не требуется.
d
b
A
Левкович Н.В.
2022/2023
f
С
E
G
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
70

71.

Изменение высоты при вращении
1) Обозначим высоту левого поддерева как HL, а высоту правого как HR
2) При вставке (как и при удалении) одного узла без балансировки
высота всех поддеревьев бинарного дерева меняется не более чем
на 1.
3) Если |HL - HR| ≤ 1,
то балансировка
вершины d не требуется.
d
b
A
f
С
E
G
Тип поворота
ΔHA ΔHC ΔHE ΔHG
Когда применяется
малый правый
-1
HL - HR = 2 и HA ≥ H C
Левкович Н.В.
2022/2023
0
+1
+1
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
71

72.

Изменение высоты при вращении
1) Обозначим высоту левого поддерева как HL, а высоту правого как HR
2) При вставке (как и при удалении) одного узла без балансировки
высота всех поддеревьев бинарного дерева меняется не более чем
на 1.
3) Если |HL - HR| ≤ 1,
то балансировка
вершины d не требуется.
d
b
A
f
С
E
G
Тип поворота
ΔHA ΔHC ΔHE ΔHG
Когда применяется
малый правый
-1
0
+1
+1
малый левый
+1
+1
0
-1
HL - HR = 2 и HA ≥ H C
HL - HR = -2 и HE ≤ HG
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
72

73.

Изменение высоты при вращении
1) Обозначим высоту левого поддерева как HL, а высоту правого как HR
2) При вставке (как и при удалении) одного узла без балансировки
высота всех поддеревьев бинарного дерева меняется не более чем
на 1.
f
b
G
d
A
С
3) Если |HL - HR| ≤ 1,
то балансировка
вершины d не требуется.
E
Тип поворота
ΔHA ΔHC ΔHE ΔHG
Когда применяется
малый правый
-1
0
+1
+1
малый левый
+1
+1
0
-1
HL - HR = 2 и HA ≥ H C
HL - HR = -2 и HE ≤ HG
большой правый
0
-1
-1
+1
HL - HR = 2 и HA < Hd
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
73

74.

Изменение высоты при вращении
1) Обозначим высоту левого поддерева как HL, а высоту правого как HR
2) При вставке (как и при удалении) одного узла без балансировки
высота всех поддеревьев бинарного дерева меняется не более чем
на 1.
b
3) Если |HL - HR| ≤ 1,
то балансировка
вершины d не требуется.
f
A
d
C
G
E
Тип поворота
ΔHA ΔHC ΔHE ΔHG
Когда применяется
малый правый
-1
0
+1
+1
малый левый
+1
+1
0
-1
HL - HR = 2 и HA ≥ H C
HL - HR = -2 и HE ≤ HG
большой правый
0
-1
-1
+1
большой левый
+1
-1
-1
0
Левкович Н.В.
2022/2023
HL - HR = 2 и HA < Hd
HL - HR = -2 и Hd > HG
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
74

75.

Изменение высоты при вращении
1) Обозначим высоту левого поддерева как HL, а высоту правого как HR
2) При вставке (как и при удалении) одного узла без балансировки
высота всех поддеревьев бинарного дерева меняется не более чем
на 1.
3) Если |HL - HR| ≤ 1,
то балансировка
вершины d не требуется.
d
b
A
f
С
E
G
Тип поворота
ΔHA ΔHC ΔHE ΔHG
Когда применяется
малый правый
-1
0
+1
+1
малый левый
+1
+1
0
-1
HL - HR = 2 и HA ≥ H C
HL - HR = -2 и HE ≤ HG
большой правый
0
-1
-1
+1
большой левый
+1
-1
-1
0
Левкович Н.В.
2022/2023
HL - HR = 2 и HA < H C
HL - HR = -2 и HE > HG
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
75

76.

Связанные динамические
структуры данных: деревья
В коде бинарное дерево обычно представляют следующим
образом:
struct TreeNode
{
MyPayload Item;
TreeNode* pLeft;
TreeNode* pRight;
};
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
76

77.

Связанные динамические
структуры данных: деревья
Что делает эта программа?
Выполняет обход бинарного дерева:
для каждого узла дерева вызывается
функция visitFunc
struct TreeNode
{
MyPayload Item;
TreeNode* pLeft;
TreeNode* pRight;
};
void Traverse(TreeNode* pNode,
void (*visitFunc)(TreeNode* pNode))
{
if (pNode == nullptr)
return;
Traverse(pNode->pLeft, visitFunc);
visitFunc(pNode);
Traverse(pNode->pRight, visitFunc);
}
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
77

78.

Связанные динамические
структуры данных: деревья
Обход бинарного дерева
Прямой обход (сверху вниз), при котором мы посещаем узел, а
затем левое и правое поддеревья
Поперечный обход (слева направо), при котором мы посещаем
левое поддерево, затем узел, а затем правое поддерево
Обратный обход (снизу вверх), при котором мы посещаем
левое и правое поддеревья, а затем узел.
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
78

79.

Связанные динамические
структуры данных: деревья
Перебор узлов дерева(а также поиск решения в задачах на графах)
может быть осуществлён:
в глубину
Левкович Н.В.
2022/2023
в ширину
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
79

80.

Связанные динамические
структуры данных: деревья
в глубину
o для каждого узла начиная с
корня обходим сперва левое
поддерево, и только потом
правое
o чтобы можно было найти
следующий элемент в
указанном порядке нужно
постоянно хранить полный
путь от текущего узла до корня
o Путь удобно хранить в виде стека
o => такой обход удобно реализуется в рекурсивной форме
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
80

81.

Связанные динамические
структуры данных: деревья
в ширину
o все элементы перебираются по
уровням
o нужно где-то хранить ВСЕ узлы
предыдущего уровня
=> повышенный расход памяти
o реализуется только в
нерекурсивной форме
o для деревьев такой способ позволяет, например,
вывести на экран дерево в обычном виде: корень сверху
o при решении задач на поиск пути в графах позволяет быстрее
находить решение благодаря тому, что в первую очередь
перебираются короткие пути и только если среди них нет
решения – более длинные
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
81

82.

Связанные динамические
структуры данных: деревья
какой из способов обхода был в примере обхода дерева?
(в глубину)
в глубину
Левкович Н.В.
2022/2023
в ширину
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
82

83.

Связанные динамические
структуры данных: деревья
Подсчёт количества узлов и высоты бинарного дерева в
рекурсивной форме
int CountNodes(TreeNode* pNode)
{
if (pNode == nullptr)
return 0;
return CountNodes(pNode->pLeft) +
CountNodes(pNode->pRight) + 1;
}
int CountHeight(TreeNode* pNode)
{
if (pNode == nullptr)
return -1;
int leftHeight = CountHeight(pNode->pLeft);
int rightHeight = CountHeight(pNode->pRight);
return max(leftHeight, rightHeight) + 1;
}
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
83

84.

Связанные динамические
структуры данных
Дерево
Добавление
элемента
Удаление
элемента
Поиск элемента
по ключу
Левкович Н.В.
2022/2023
Сбалансированное
дерево (max)
min
max
O(1)
O(N)
O(log2(N))
O(1)
O(N)
O(log2(N))
O(1)
O(N)
O(log2(N))
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
84

85.

Вопросы
7. Алгоритмы с амортизированной константной сложностью.
8. Связанные динамические структуры данных.
Организация связанных динамических структур данных.
Основные виды связанных структур данных.
Левкович Н.В.
2022/2023
СВЯЗАННЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ДАННЫХ
85