tgoop.com/csharpproglib/5946
Create:
Last Update:
Last Update:
Проблема: при работе с большими наборами данных обычное бинарное дерево поиска (BST) может деградировать в линейную структуру, что снижает скорость поиска до O(n).
Решение: В книге Algorithms and Data Structures for OOP With C# автор предлагает использовать AVL-дерево — сбалансированное дерево, которое поддерживает балансировку после каждой операции вставки или удаления. Это гарантирует сложность поиска, вставки и удаления за O(log n).
Пример кода:
public class AVLNode
{
public int Key;
public AVLNode Left, Right;
public int Height;
public AVLNode(int key)
{
Key = key;
Height = 1;
}
}
public class AVLTree
{
private AVLNode root;
int Height(AVLNode node) => node?.Height ?? 0;
int BalanceFactor(AVLNode node) => Height(node.Left) - Height(node.Right);
AVLNode RightRotate(AVLNode y)
{
var x = y.Left;
var T2 = x.Right;
x.Right = y;
y.Left = T2;
y.Height = Math.Max(Height(y.Left), Height(y.Right)) + 1;
x.Height = Math.Max(Height(x.Left), Height(x.Right)) + 1;
return x;
}
AVLNode LeftRotate(AVLNode x)
{
var y = x.Right;
var T2 = y.Left;
y.Left = x;
x.Right = T2;
x.Height = Math.Max(Height(x.Left), Height(x.Right)) + 1;
y.Height = Math.Max(Height(y.Left), Height(y.Right)) + 1;
return y;
}
public AVLNode Insert(AVLNode node, int key)
{
if (node == null)
return new AVLNode(key);
if (key < node.Key)
node.Left = Insert(node.Left, key);
else if (key > node.Key)
node.Right = Insert(node.Right, key);
else
return node;
node.Height = 1 + Math.Max(Height(node.Left), Height(node.Right));
int balance = BalanceFactor(node);
if (balance > 1 && key < node.Left.Key)
return RightRotate(node);
if (balance < -1 && key > node.Right.Key)
return LeftRotate(node);
if (balance > 1 && key > node.Left.Key)
{
node.Left = LeftRotate(node.Left);
return RightRotate(node);
}
if (balance < -1 && key < node.Right.Key)
{
node.Right = RightRotate(node.Right);
return LeftRotate(node);
}
return node;
}
}
Преимущества:
— Обеспечение сбалансированного дерева с высотой O(log n)
— Быстрый поиск и обновление данных
— Подходит для систем, требующих высокопроизводительных операций поиска