20-21. Бинарное дерево поиска. Поиск элемента по ключу. Рекурсивный вариант. Итеративный вариант
TSearchTree* recursiveSearch(TSearchTree* root, datatype value) {
if (root == nullptr || root->data == value)
return root;
if (root->data > value)
return recursiveSearch(root->left, value);
if (root->data < value)
return recursiveSearch(root->right, value);
}
TSearchTree* iterativeSearch(TSearchTree* root, datatype value) {
while (root != nullptr && root->data != value) {
if (root->data > value)
root = root->left;
else
root = root->right;
}
return root;
}22. AVL-деревья. Деревья Фибоначчи.AVL Адельсон-Вельский Ландис(изобретатели)
Дерево называется сбалансированным, если для каждого узла высота его левого и правого поддеревьев
отличается не более чем на 1
Высота дерева логарифмически зависит от числа его узлов
log2(n+1) < h < log2(n+2) - 0,328
AVL деревья с n узлами могут иметь разную высоту, зависящую от порядка вставки элементов в дерево
Для того чтобы определить максимальную высоту дерева состоящего из n узлов,
зафиксируем h и будем строить дерево с минимальным числом узлов
n = 0 Пустое дерево
n = 1 ->o
n = 2 ->o-o
n = 3 ->o-o-o
\
o
n = 4 ->o-o-o-o
\ \
o o
\
o
(Каждое последущее содержит 2 предыдущих как поддеревья/деревья Фибоначи)
N = N[n-1] + N[n-2] + 1 (N[0] = 0, N[1] = 1) - рекурентное уравнение
Nh - число Леонардо, для которого может реализоваться наихудший случай AVL дерева высоты h
Дерево называется сбалансированным, если для каждого узла высота его левого и правого поддеревьев
отличается не более чем на 1
Высота дерева логарифмически зависит от числа его узлов
log2(n+1) < h < log2(n+2) - 0,328
AVL деревья с n узлами могут иметь разную высоту, зависящую от порядка вставки элементов в дерево
Для того чтобы определить максимальную высоту дерева состоящего из n узлов,
зафиксируем h и будем строить дерево с минимальным числом узлов
n = 0 Пустое дерево
n = 1 ->o
n = 2 ->o-o
n = 3 ->o-o-o
\
o
n = 4 ->o-o-o-o
\ \
o o
\
o
(Каждое последущее содержит 2 предыдущих как поддеревья/деревья Фибоначи)
N = N[n-1] + N[n-2] + 1 (N[0] = 0, N[1] = 1) - рекурентное уравнение
Nh - число Леонардо, для которого может реализоваться наихудший случай AVL дерева высоты h
23. Вставка элемента в сбалансированное дерево. Два случая нарушения баланса
Пусть новый узел вставляется в левое поддерево, тогда возможны 3 исхода
1) hL < hR => Баланс ухудшается hL = hR
2) hL = hR => Баланс не меняется hL = hR +1
3) hL > hR => Баланс нарушается, нужна балансировка
2 случая нарушения баланса
Пусть новый узел вставляется в левое поддерево, тогда возможны 3 исхода
1) hL < hR => Баланс ухудшается hL = hR
2) hL = hR => Баланс не меняется hL = hR +1
3) hL > hR => Баланс нарушается, нужна балансировка
2 случая нарушения баланса
24. Способы хранения информации о сбалансированности дерева
Алгоритм вставки и балансировки зависит от способа хранения информации об сбалансированности дерева
1 способ каждый раз пересчитывать баланс(не хранить)
2 способ хранить в каждом узле доп поле отражающее значение баланса в этом узле
3 способ хранить в узле высоту дерева с корнем в этом узле
Алгоритм вставки и балансировки зависит от способа хранения информации об сбалансированности дерева
1 способ каждый раз пересчитывать баланс(не хранить)
2 способ хранить в каждом узле доп поле отражающее значение баланса в этом узле
3 способ хранить в узле высоту дерева с корнем в этом узле
(Вроде как 3й случай но возможно 2й)
struct TreeNode {
int data;
int height;
TreeNode* left;
TreeNode* right;
};
int height(TreeNode* p)
{
return (p == nullptr) ? 0 : p->height;
}
int balanceFactor(TreeNode* p)
{
return (height(p->right) - height(p->left));
}
void fixHeight(TreeNode* p) {
int left_height = height(p->left);
int right_height = height(p->right);
p->height = ((left_height - right_height) ? left_height : right_height) + 1;
}25-26. Правый и левый простые повороты. Большой поворот
В процессе добавления или удаления узла в AVL дереве возможно возникновение ситуации,
когда баланс фактор некоторых узлов становится равным 2 или -2, т.е. возникает разбалансировка поддерева.
В процессе добавления или удаления узла в AVL дереве возможно возникновение ситуации,
когда баланс фактор некоторых узлов становится равным 2 или -2, т.е. возникает разбалансировка поддерева.
TreeNode* RR_rotate(TreeNode* p) //1 случай
{
TreeNode* q = p->left;
p->left = q->right;
q->right = p;
fixHeight(p); fixHeight(q);
return q;
}
TreeNode* LL_rotate(TreeNode* q) //2 случай
{
TreeNode* p = q->right;
q->right = p->left;
p->left = q;
fixHeight(q); fixHeight(p);
return p;
}
TreeNode* balance(TreeNode* p)
{
fixHeight(p);
if (balanceFactor(p) == 2)
{
if (balanceFactor(p->right) < 0)
p->right = RR_rotate(p->right);
return LL_rotate(p);
}
if (balanceFactor(p) == -2)
{
if (balanceFactor(p->left) > 0)
p->left = LL_rotate(p->left);
return RR_rotate(p);
}
return p;
}
27. Вставка ключей в AVL-дерево
Обобщенный алгоритм вставки
1. Пройти по пути вставки пока не выяснится что вставляемого ключа в дереве еще нет
2. Всавить новый узел и определить получившийся баланс
3. Пройти обратно по пути вставки выполняя баланисровку где требуется
Обобщенный алгоритм вставки
1. Пройти по пути вставки пока не выяснится что вставляемого ключа в дереве еще нет
2. Всавить новый узел и определить получившийся баланс
3. Пройти обратно по пути вставки выполняя баланисровку где требуется
TreeNode* insert(TreeNode* pNode, int elem)
{
if (pNode == nullptr)
{
pNode = new TreeNode;
pNode->left = nullptr;
pNode->right = nullptr;
return balance(pNode);
}
if (elem < pNode->data)
pNode->left = insert(pNode->left, elem);
return balance(pNode);
}
28. Удаление ключей из AVL-дерева
Алгоритм удаления ключа
1) находим узел с заданным ключом k
2) в правом поддереве находим узел min, с наименьшим ключом
и заменяем удаляемый узел на найденный узел min
3) если удаляемый узел p не умеет правого поддерева, то по свойству AVL дерева,
слева может быть только 1 узел либо ни одного
в обоих случаях можно удалить узел p и вернуть в качестве указатель левый дочерний узел узла p
Пусть правое поддерево узла p есть, тогда находим минимальный ключ в этом поддереве
Алгоритм удаления ключа
1) находим узел с заданным ключом k
2) в правом поддереве находим узел min, с наименьшим ключом
и заменяем удаляемый узел на найденный узел min
3) если удаляемый узел p не умеет правого поддерева, то по свойству AVL дерева,
слева может быть только 1 узел либо ни одного
в обоих случаях можно удалить узел p и вернуть в качестве указатель левый дочерний узел узла p
Пусть правое поддерево узла p есть, тогда находим минимальный ключ в этом поддереве
TreeNode* findMin(TreeNode* p)
{
return p->left ? findMin(p->left) : p;
}
TreeNode* removeMin(TreeNode* p)
{
if (p->left == nullptr)
return p->right;
p->left = removeMin(p->left);
return balance(p);
}
TreeNode* remove(TreeNode* p, int elem)
{
if (!p) return nullptr;
if (elem < p->data)
p->left = remove(p->left, elem);
else {
if (elem > p->data)
p->right = remove(p->right, elem);
else
{
TreeNode* q = p->left;
TreeNode* r = r->right;
p->left = nullptr;
p->right = nullptr;
delete p;
p = nullptr;
if (!r) return q;
TreeNode* minNode = findMin(r);
minNode->right = removeMin(r);
minNode->left = q;
return balance(minNode);
}
}
return balance(p);
}
29. Trie-деревья. Структура, применение, основные операции.
Trie - деревья(reTRIEval) префиксные деревья, луч, бор
Trie деревья используются для хранения информации, в случае если ключами являются строки.
Узлы Trie дерева не хранят никаних значений,
ребра соотвествуют буквам(символам) строки
и листовые элементы могут хранит какие-либо значения
Trie - деревья(reTRIEval) префиксные деревья, луч, бор
Trie деревья используются для хранения информации, в случае если ключами являются строки.
Узлы Trie дерева не хранят никаних значений,
ребра соотвествуют буквам(символам) строки
и листовые элементы могут хранит какие-либо значения
30. Различные представления узла trie-дерева.
1 способ:
хранить в каждом узле массив размером d+1 из указателей на такие же узлы(d размер алфавита + корень)
a) можно ввести дополнительное поле типа bool, означающене что узел - конец слова
2 cпособ:
хранить в узле ссылку на sibling и child
1 способ:
хранить в каждом узле массив размером d+1 из указателей на такие же узлы(d размер алфавита + корень)
a) можно ввести дополнительное поле типа bool, означающене что узел - конец слова
2 cпособ:
хранить в узле ссылку на sibling и child
//(1)
const int d = 26;
struct TrieNode
{
TrieNode* alph[d + 1];
};
//(1a)
const int d = 26;
struct TrieNode
{
TrieNode* alph[d];
bool eow;
};
//(2)
struct TrieNode2
{
char symbol;
TrieNode2* child;
TrieNode2* sibling;
//bool eow;
};
31. Алгоритм вставки элемента в trie-дерево.
void insert(TrieNode* root, string str, int i=0)
{
if (i < str.length())
{
if (i == str.length() - 1)
root->eow = true;
else
{
if (root->alph[str[i] - 'a'] == nullptr)
{
root->alph[str[i] - 'a'] = new TrieNode;
insert(root->alph[str[i] - 'a'], str, i + 1);
}
}
}
}
32. Алгоритм удаления элемента из trie-дерева.(это делал чатик так что рискуем)
void remove(string word)
{
removeHelper(word, root, 0);
}
void removeHelper(string& str, TrieNode* current, int i)
{
if (i == str.length())
{
if (current != nullptr)
{
current->isEndOfWord = false;
}
return;
}
if (current->children[str[i] - 'a'] != nullptr)
{
removeHelper(str, current->children[str[i] - 'a'], i + 1);
if (current->children[str[i] - 'a']->isEndOfWord == false)
{
delete current->children[str[i] - 'a'];
current->children[str[i] - 'a'] = nullptr;
}
}
}
void visualizeTree(Node* root, int level = 0)
{
if (root == nullptr) return;
visualizeTree(root->right, level + 1);
for (int i = 0; i < level; i++)
cout << " ";
cout << root->key << endl;
visualizeTree(root->left, level + 1);
}