Similar presentations:
Лекция 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