Дерево AVL, также известное как сбалансированное по высоте дерево двоичного поиска (BST), является гениальным изобретением Адельсона-Вельского и Лэндиса, отсюда и аббревиатура «AVL». Подобно красно-черным деревьям, деревья AVL предназначены для поддержания баланса, что гарантирует стабильную и надежную работу даже при частых изменениях дерева.
Важность этой надежной работы невозможно переоценить. Работая с большими наборами данных или в ситуациях, требующих быстрых операций, мы не можем позволить себе временную сложность O(n), с которой могут столкнуться стандартные BST в своих наихудших сценариях. Деревья AVL берут на себя ответственность за это, предлагая сбалансированную древовидную структуру, которая помогает поддерживать скорость и стабильную производительность для всех важнейших задач.
Тон этой статьи предполагает, что вы уже знакомы с бинарными деревьями поиска. Если нет, я бы порекомендовал вам начать со статьи «Двоичное дерево поиска», перейдя по ссылке ниже, а затем вернуться и продолжить здесь позже:
Глубокое погружение в структуры данных с использованием Javascript — двоичное дерево поиска
Анатомия дерева AVL
AVL Tree — это вариант двоичного дерева поиска (BST), но с дополнительными свойствами для поддержания баланса. Как и BST, деревья AVL имеют узлы с максимум двумя дочерними элементами, где левый дочерний элемент имеет меньшее значение, а правый дочерний элемент имеет большее значение, чем родительский узел.
Ключевой особенностью AVL Tree является способность сохранять баланс после каждой операции, используя свойство высоты в качестве коэффициента баланса. Этот баланс имеет решающее значение, поскольку он гарантирует эффективную работу даже с большими наборами данных или приложениями, чувствительными ко времени.
Каждый узел в дереве AVL имеет пять свойств:
- value: данные или значение, хранящиеся в узле.
- left: ссылка на левый дочерний узел.
- right: ссылка на правый дочерний узел.
- parent: ссылка на родительский узел.
- height: высота узла в древовидной структуре.
Давайте подробнее рассмотрим свойство height и его роль:
Высота
Высота узла в дереве AVL представляет собой самый длинный путь от этого узла до листа. Листовые узлы имеют высоту 0. Свойство высоты необходимо для поддержания баланса в дереве и расчета коэффициента баланса.
Правила дерева АВЛ
Для поддержания баланса в дереве AVL требуется соблюдение набора правил, известных как свойства дерева AVL:
- Пути одинаковой высоты. Поддержание путей одинаковой высоты имеет решающее значение в дереве AVL. Это свойство гарантирует, что все пути от узла к его дочерним листовым узлам имеют одинаковую высоту. Выполнение вращений, когда это необходимо, помогает поддерживать этот баланс.
- Вращение дерева: для исправления любого дисбаланса в дереве AVL выполняются вращения. Повороты обращаются к узлам с коэффициентами баланса за пределами -1, 0 или 1. Существует четыре типа поворотов: левый, правый, левый-правый и правый-левый, используемые на основе определенного обнаруженного дисбаланса.
- Коэффициент баланса. Каждый узел в дереве AVL имеет коэффициент баланса, рассчитанный путем нахождения разницы в высоте между его левым и правым дочерними узлами. Сбалансированное дерево AVL гарантирует, что коэффициент баланса каждого узла равен -1, 0 или 1. Если коэффициент баланса узла выходит за пределы этого диапазона, дерево становится несбалансированным и нуждается в корректировке путем ротации.
- Листовые узлы (пустые узлы): считается, что конечные узлы или нулевые узлы имеют высоту -1. Это соглашение помогает в расчете коэффициента баланса, помогая поддерживать баланс дерева во время операций.
Все эти правила могут показаться запутанными на данный момент, давайте посмотрим на несколько основных примеров того, как все эти вращения, чтобы получить некоторое представление о них.
Вращения дерева AVL в деталях
Вращение дерева AVL — это основные операции, используемые для поддержания баланса дерева AVL после вставки или удаления. Баланс дерева AVL определяется разницей в высоте между левым и правым поддеревьями узла. Если эта разница больше 1 или меньше -1, дерево считается несбалансированным, и для восстановления баланса используются повороты.
Всего существует 4 типа вращения, которые мы можем разделить на одиночные и двойные:
Одиночное вращение
Лево-левое (LL) вращение (также известное как правое вращение):
Вращение влево-влево используется, когда узел несбалансирован влево, а левый дочерний элемент несбалансированного узла сам сбалансирован влево или идеально сбалансирован. Неуравновешенный узел поворачивается вправо для восстановления баланса.
При вращении влево-влево левый дочерний элемент несбалансированного узла становится новым корнем поддерева, а исходный корень становится правым дочерним элементом нового корня. Если у нового корня был правый дочерний элемент до поворота, он становится левым дочерним элементом исходного корня после поворота.
Вращение вправо-вправо (RR) (также известное как вращение влево):
Вращение вправо-вправо является зеркальным отражением вращения LL. Он используется, когда узел несбалансирован с правой стороны, а правый потомок несбалансированного узла сам сбалансирован с правой стороны или идеально сбалансирован.
При вращении вправо-вправо правый дочерний элемент несбалансированного узла становится новым корнем поддерева, а исходный корень становится левым дочерним элементом нового корня. Если у нового корня был левый дочерний элемент до поворота, он становится правым дочерним элементом исходного корня после поворота.
Двойное вращение
Вращение влево-вправо (LR) (сначала влево, затем вправо):
Вращение влево-вправо используется, когда узел несбалансирован влево, но левый дочерний элемент несбалансированного узла сбалансирован вправо.
Вращение влево-вправо выполняется в два этапа: вращение RR на левом дочернем элементе несбалансированного узла с последующим вращением LL на исходном несбалансированном узле. Это эффективно уравновешивает дерево, перемещая правый дочерний элемент левого дочернего элемента на место несбалансированного узла и соответствующим образом перестраивая другие узлы.
Вращение вправо-влево (RL) (сначала вправо, затем влево):
Вращение вправо-влево является зеркальным отражением вращения влево-вправо. Он используется, когда узел несбалансирован с правой стороны, а правый потомок несбалансированного узла сбалансирован с левой стороны.
Вращение вправо-влево выполняется в два этапа: вращение LL правого потомка несбалансированного узла с последующим вращением RR исходного несбалансированного узла. Это эффективно уравновешивает дерево, перемещая левый дочерний элемент правого дочернего элемента на место несбалансированного узла и соответствующим образом перестраивая другие узлы.
Когда использовать дерево AVL
Давайте начнем с рассмотрения большого O общих операций в AVL Tree:
Если вы окажетесь в ситуации, когда вам может понадобиться использовать дерево AVL, скорее всего, вы будете искать вариант самобалансирующегося двоичного дерева поиска. Существуют различные самобалансирующиеся деревья, но наиболее распространенными вариантами являются AVL Tree и Red-Black Tree.
Несмотря на то, что оба они являются самобалансирующимися, в некоторых случаях предпочтение отдается одному из них. Подробнее о сравнении см. в разделе Red-Black Tree vs AVL Tree” в статье Red-Black Tree:
Глубокое погружение в структуры данных с использованием Javascript — Red-Black Tree
Основной палец или правило:
- Используйте AVL Tree, если у вас есть сценарий с интенсивным поиском.
- Используйте Red-Black Tree, если у вас есть сценарий интенсивной вставки/удаления.
Причина, по которой деревья AVL более эффективны для приложений с интенсивным поиском, заключается в том, что они более строго сбалансированы (логика баланса следует за высотой, а не за цветами) и, следовательно, имеют меньшую высоту, что приводит к более быстрому поиску.
Некоторые конкретные сценарии, в которых вы можете захотеть использовать дерево AVL:
Базы данных и файловые системы с интенсивным поиском. Для определенных типов баз данных, особенно с большим объемом операций чтения и меньшим количеством операций записи, деревья AVL могут быть предпочтительнее красно-черных деревьев. Например, в системе, где вы постоянно извлекаете информацию о профиле пользователя (операция чтения), но информация о профиле пользователя обновляется реже (операция записи), превосходная производительность поиска дерева AVL была бы выгодна.
Системы управления словарями и библиотеками. Деревья AVL идеально подходят для таких сценариев, как словарь, где основной операцией является поиск слова и его значения. Точно так же в управлении библиотекой поиск книг по разным параметрам происходит чаще, чем вставка или удаление книг в/из системы.
Наборы данных малого и среднего размера. Деревья AVL могут быть хорошим выбором для сценариев, в которых набор данных имеет относительно небольшой или средний размер. Свойство самобалансировки деревьев AVL обеспечивает эффективность операций поиска, что делает их подходящими, когда набор данных может удобно разместиться в памяти, не вызывая чрезмерного использования памяти.
Обратите внимание, что при работе с большими наборами данных или когда возникает проблема с ограничениями по объему памяти, могут оказаться более подходящими другие структуры индексации, такие как B-деревья, которые предназначены для дисковых или больших наборов данных. B-деревья оптимизируют шаблоны доступа к диску и хорошо работают с большими объемами данных, что делает их предпочтительным выбором для сценариев, когда данные не могут быть полностью сохранены в памяти.
Мы будем использовать классы ES6 для построения нашего дерева AVL. Вот список методов, которые мы собираемся реализовать:
insert(value)— этот метод используется для вставки нового значения в дерево AVL. Метод начинается с создания нового узла и размещения его в правильном положении в соответствии со стандартными правилами двоичного дерева поиска. После вставки узла вызываются методыupdateHeightиbalanceдля восстановления свойств дерева AVL.delete(value)— Этот метод удаляет узел с заданным значением из дерева. Сначала он находит узел с помощью метода поиска, а затем удаляет его, сохраняя свойства дерева AVL. После удаления узла вызываются методыupdateHeightиbalanceдля восстановления свойств дерева AVL.search(value)— этот метод находит узел в дереве, соответствующий заданному значению._balance(node)— это вспомогательный метод, используемый для балансировки дерева. В зависимости от коэффициента баланса данного узла этот метод решит, необходимо ли вращение и какой тип вращения следует применить._updateHeight(node)— это вспомогательный метод, используемый для обновления высоты узла после вставки или удаления._getNodeHeight(node) and getBalanceFactor(node)— эти вспомогательные методы используются для расчета высоты узла и коэффициента баланса соответственно. Они используются во время операций вставки, удаления и поворота для сохранения свойств дерева AVL._leftRotation(node) and _rightRotation(node)- Эти вспомогательные методы используются для выполнения поворотов влево-вправо и вправо-влево. Эти повороты используются, когда дерево находится в состоянии, когда простого поворота влево или вправо недостаточно для восстановления свойств дерева AVL._leftRightRotation(node) and _rightLeftRotation(node)— эти вспомогательные методы используются для выполнения поворотов влево-вправо и вправо-влево. Эти повороты используются, когда дерево находится в состоянии, когда простого поворота влево или вправо недостаточно для восстановления свойств дерева AVL._findMin(node)— этот метод находит узел с наименьшим значением в дереве. Он используется во время операции удаления для поиска преемника удаляемого узла.levelOrderTraversal()— Отображение дерева AVL в виде многомерного массива с порядком уровней, используя «обход по порядку уровней». Конечный выходной массив будет представлять дерево, где каждый подмассив представляет уровень дерева.
Я хотел бы отметить, что понимание AVL Trees в первый раз будет сложной задачей. Они находятся на продвинутом и сложном конце спектра структур данных. Чтобы полностью понять все концепции, потребуется потратить время на эксперименты и исследования. Готовая самобалансировка — это мощное волшебство, но за это приходится платить сложностью реализации.
При изучении методов вставки и удаления вы столкнетесь с различными условиями и шагами в сочетании со специфическими операциями AVL Tree, такими как повороты. Понимание этих операций имеет решающее значение, поскольку они формируют основную механику того, как дерево AVL сохраняет свой баланс во время модификаций.
Повороты, особенно левые и правые повороты, играют жизненно важную роль в перебалансировке дерева, когда его свойства нарушаются из-за вставки или удаления. Они перестраивают узлы, чтобы восстановить свойства дерева AVL. Твердое понимание этих поворотов поможет вам лучше понять сложные методы вставки и удаления.
Чтобы улучшить ваше понимание и визуализировать механику деревьев AVL, я настоятельно рекомендую поиграть с этим удивительным визуализатором деревьев AVL по ссылке ниже:
Кроме того, я также включил построчные объяснения для каждого метода в реализации, чтобы вы могли следить за тем, что происходит в коде. Практические занятия с визуализатором — хорошая отправная точка для углубления вашего понимания.
Я надеюсь, что эта статья помогла вам получить хорошее представление о том, что такое деревья AVL и как они работают! Я хотел бы призвать вас поэкспериментировать с приведенной ниже реализацией в вашем любимом редакторе кода. Спасибо за прочтение!
Реализация дерева AVL в Javascript
class AVLTreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
this.height = 0;
}
}
class AVLTree {
constructor() {
this.root = null;
}
insert(value) {
// Define an inner helper function for the recursive insertion
const insertHelper = (node, parent = null) => {
// If the current node is null, this means we've found the place to insert the new value
if (!node) {
// Create a new node with the value
const newNode = new AVLTreeNode(value);
// Set the parent of the new node to be the passed in parent node
newNode.parent = parent;
// Return the newly created node
return newNode;
}
// If the value to insert is less than the value of the current node
if (value < node.value) {
// Recursively call 'insertHelper' on the left child, passing in the current node as the parent
node.left = insertHelper(node.left, node);
} else if (value > node.value) {
// If the value to insert is greater than the value of the current node
// Recursively call 'insertHelper' on the right child, passing in the current node as the parent
node.right = insertHelper(node.right, node);
}
// After the recursive calls, update the height of the current node
// This is done after because the node's height may change due to the insert
this._updateHeight(node);
// Balance the node and return it. This is to ensure that AVL tree properties are maintained
return this._balance(node);
};
// Call the 'insertHelper' function on the root node
this.root = insertHelper(this.root);
// Ensure that the root node's parent is null after insertions
if (this.root.parent) {
this.root.parent = null;
}
}
delete(value) {
// Define an inner helper function for the recursive deletion
const deleteNode = (value, node) => {
// If the current node is null, this means the value is not found in the tree
if (!node) {
return null;
}
// If the value to delete is less than the value of the current node
if (value < node.value) {
// Recursively call 'deleteNode' on the left child
node.left = deleteNode(value, node.left);
} else if (value > node.value) {
// If the value to delete is greater than the value of the current node
// Recursively call 'deleteNode' on the right child
node.right = deleteNode(value, node.right);
} else {
// If the value is found
// Case 1: Node is a leaf node
if (!node.left && !node.right) {
return null;
} else if (!node.left) {
// Case 2: Node has only right child
// Assign the parent of the node to be deleted to its right child
node.right.parent = node.parent;
// Return right child
return node.right;
} else if (!node.right) {
// Case 3: Node has only left child
// Assign the parent of the node to be deleted to its left child
node.left.parent = node.parent;
// Return left child
return node.left;
} else {
// Case 4: Node has two children
// Find the in-order successor (minimum value in right subtree)
const successor = this._findMin(node.right);
// Replace the value of the node to be deleted with the value of the successor
node.value = successor.value;
// Delete the successor
node.right = deleteNode(successor.value, node.right);
}
}
// After the recursive calls, update the height of the current node
// This is done after because the node's height may change due to the delete
this._updateHeight(node);
// Balance the node and return it. This is to ensure that AVL tree properties are maintained
return this._balance(node);
};
// Call the 'deleteNode' function on the root node
this.root = deleteNode(value, this.root);
// Ensure that the root node's parent is null after deletions
// because root node parent should always be null.
if (this.root && this.root.parent) {
this.root.parent = null;
}
}
search(value, node = this.root) {
// Check if the current node is null (reached a leaf node or an empty tree)
if (!node) {
// Value not found, return false
return false;
}
// Check if the current node's value matches the search value
if (value === node.value) {
// Value found, return the node
return node;
}
// If the search value is less than the current node's value, go to the left subtree
if (value < node.value) {
// Recursively call the search function on the left child node
return this.search(value, node.left);
}
// If the search value is greater than the current node's value, go to the right subtree
// This assumes the tree follows the convention of left child nodes having lesser values and right child nodes having greater values
return this.search(value, node.right);
}
_balance(node) {
// The balance function is used to restore the balance of an AVL tree
// after an insertion or deletion operation that might have caused imbalance.
// If the node is null, simply return the null node
if (!node) {
return node;
}
// Compute the balance factor of the node
// The balance factor of a node is the difference in height between its left and right subtrees
const nodeBF = this._getBalanceFactor(node);
// Check if the left subtree is heavy (balance factor > 1)
if (nodeBF > 1) {
// Check if the left subtree is right heavy
// This is the case of Left-Right imbalance
// which requires a Left-Right rotation to fix
if (this._getBalanceFactor(node.left) < 0) {
return this._leftRightRotation(node);
}
// If the left subtree is left heavy, a simple Right rotation is enough to restore balance
return this._rightRotation(node);
}
// Check if the right subtree is heavy (balance factor < -1)
else if (nodeBF < -1) {
// Check if the right subtree is left heavy
// This is the case of Right-Left imbalance
// which requires a Right-Left rotation to fix
if (this._getBalanceFactor(node.right) > 0) {
return this._rightLeftRotation(node);
}
// If the right subtree is right heavy, a simple Left rotation is enough to restore balance
return this._leftRotation(node);
}
// If the node is already balanced, no rotation is required, simply return the node
return node;
}
_updateHeight(node) {
// To update the height of a node in an AVL tree, we first calculate the height of its left and right subtrees using the '_getNodeHeight' method
const leftSubtreeHeight = this._getNodeHeight(node.left);
const rightSubtreeHeight = this._getNodeHeight(node.right);
// The height of a node is defined as 1 plus the maximum height of its left or right subtree
// This is based on the definition of the height of a node in a binary tree (the number of edges on the longest downward path from the node to a leaf)
// We use the built-in 'Math.max' function to find the maximum between the heights of the left and right subtrees
// Then, we add 1 to this maximum height to calculate the new height of the node
node.height = Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1;
}
_getNodeHeight(node) {
// Check if the node is null
// This is important because we may call this method on a leaf node's child, which is null
if (!node) {
// If the node is null, return -1, as by convention, the height of a null node is considered -1
return -1;
}
// If the node is not null, return its height property
// The height of a node is stored in its 'height' property in our AVL Tree implementation
return node.height;
}
_getBalanceFactor(node) {
// Get the height of the left subtree of the given node
// We use the '_getNodeHeight' method, which takes a node as an argument and returns its height
// If the left child of the node is null, '_getNodeHeight' returns -1
const leftSubtreeHeight = this._getNodeHeight(node.left);
// Similarly, get the height of the right subtree of the given node
const rightSubtreeHeight = this._getNodeHeight(node.right);
// The balance factor of a node in an AVL tree is the difference between the height of its left subtree and the height of its right subtree
// So, we calculate the balance factor by subtracting the height of the right subtree from the height of the left subtree
// This can result in a negative number, zero, or a positive number
// According to the AVL tree property, this value should always be -1, 0, or 1 for all nodes in a balanced AVL tree
return leftSubtreeHeight - rightSubtreeHeight;
}
_leftRotation(node) {
// A left rotation is performed when the right child of a node has a greater height than its left child
// We start the rotation by creating a temporary reference to the node's right child because this node will become the new parent node after rotation
const temp = node.right;
// The right child of the current node is then replaced by the left child of the 'temp' node (i.e., the node's right grandchild becomes its new right child)
node.right = temp.left;
// If the 'temp' node had a left child, we update its parent to be the 'node'
if (temp.left) {
temp.left.parent = node;
}
// The 'node' becomes the left child of the 'temp' node
temp.left = node;
// The parent of the 'temp' node becomes the parent of the 'node', which maintains the binary search tree property
temp.parent = node.parent;
// The parent of the 'node' is updated to be the 'temp' node because 'temp' is the new parent after rotation
node.parent = temp;
// If the 'temp' node has a parent (i.e., it's not the root of the tree), we update the parent's child reference to point to 'temp'
if (temp.parent) {
if (temp.parent.left === node) {
temp.parent.left = temp;
} else if (temp.parent.right === node) {
temp.parent.right = temp;
}
}
// After the rotation, we update the height of the 'node' and 'temp' nodes because their subtrees might have changed
this._updateHeight(node);
this._updateHeight(temp);
// The 'temp' node is returned because it's the new parent node after the left rotation
return temp;
}
_rightRotation(node) {
// A right rotation is performed when the left child of a node has a greater height than its right child
// We start the rotation by creating a temporary reference to the node's left child because this node will become the new parent node after rotation
const temp = node.left;
// The left child of the current node is then replaced by the right child of the 'temp' node (i.e., the node's left grandchild becomes its new left child)
node.left = temp.right;
// If the 'temp' node had a right child, we update its parent to be the 'node'
if (temp.right) {
temp.right.parent = node;
}
// The 'node' becomes the right child of the 'temp' node
temp.right = node;
// The parent of the 'temp' node becomes the parent of the 'node', which maintains the binary search tree property
temp.parent = node.parent;
// The parent of the 'node' is updated to be the 'temp' node because 'temp' is the new parent after rotation
node.parent = temp;
// If the 'temp' node has a parent (i.e., it's not the root of the tree), we update the parent's child reference to point to 'temp'
if (temp.parent) {
if (temp.parent.left === node) {
temp.parent.left = temp;
} else if (temp.parent.right === node) {
temp.parent.right = temp;
}
}
// After the rotation, we update the height of the 'node' and 'temp' nodes because their subtrees might have changed
this._updateHeight(node);
this._updateHeight(temp);
// The 'temp' node is returned because it's the new parent node after the right rotation
return temp;
}
_leftRightRotation(node) {
// A left-right rotation is performed when the right child of the left child of a node has a greater height than its left child
// This situation creates an imbalance that cannot be fixed by a simple rotation
// First, a left rotation is performed on the left child of the node
// The purpose of this step is to convert the imbalance into a form that can be fixed by a simple rotation
node.left = this._leftRotation(node.left);
// After converting the imbalance, we perform a right rotation on the original node
// This step fixes the imbalance and restores the AVL tree property
return this._rightRotation(node);
}
_rightLeftRotation(node) {
// A right-left rotation is performed when the left child of the right child of a node has a greater height than its right child
// This situation creates an imbalance that cannot be fixed by a simple rotation
// First, a right rotation is performed on the right child of the node
// The purpose of this step is to convert the imbalance into a form that can be fixed by a simple rotation
node.right = this._rightRotation(node.right);
// After converting the imbalance, we perform a left rotation on the original node
// This step fixes the imbalance and restores the AVL tree property
return this._leftRotation(node);
}
_findMin(node = this.root) {
// The _findMin method is used to find the node with the smallest value in a binary search tree.
// By the properties of a binary search tree, the smallest node is the leftmost node.
// We start from the given node, defaulting to the root of the tree if no node is provided.
let currentNode = node;
// While there is a node to inspect and that node has a left child
while (currentNode && currentNode.left) {
// Move to the left child of the current node
// This is because in a binary search tree, all values in the left subtree are less than the value of the node
currentNode = currentNode.left;
}
// When there are no more left children to move to, we've found the smallest value node
// Return this node
return currentNode;
}
// Displays an array that will represent the tree
// in level-order, with each sub-array representing a level of the tree.
levelOrderTraversal() {
// Create an empty array to store the traversed nodes
const temp = [];
// Create an array to keep track of the current level of nodes
const queue = [];
// If the tree has a root, add it to the queue
if (this.root) {
queue.push(this.root);
}
// Keep traversing the tree while there are nodes in the queue
while (queue.length) {
// Create an array to store the nodes of the current level
const subTemp = [];
// Store the number of nodes in the current level
const len = queue.length;
// Iterate through the current level of nodes
for (let i = 0; i < len; i += 1) {
// Dequeue the first node in the queue
const node = queue.shift();
// Push the node's value to the subTemp array
subTemp.push(node.value);
// If the node has a left child, add it to the queue
if (node.left) {
queue.push(node.left);
}
// If the node has a right child, add it to the queue
if (node.right) {
queue.push(node.right);
}
}
// Push the subTemp array to the temp array
temp.push(subTemp);
}
// Return the final temp array
return temp;
}
}
export default AVLTree;
Первоначально опубликовано на https://www.sahinarslan.tech.
