AVL树
大约 3 分钟
AVL树
在计算机科学中，AVL树（以发明者Adelson-Velsky和Landis的姓氏命名）是一种自平衡的二叉搜索树。它是第一种这样的数据结构。在AVL树中，任何节点的两个子树的高度最多相差一；如果它们的高度相差超过一，就会进行重新平衡以恢复这个性质。查找、插入和删除在平均情况和最坏情况下都需要 O(log n) 的时间，其中n是操作之前树中的节点数。插入和删除可能需要通过一个或多个树旋转来重新平衡树。
动画展示了将多个元素插入AVL树中的过程。它包括左旋、右旋、左右旋和右左旋。
带有平衡因子的AVL树（绿色）
AVL树的旋转操作
左-左旋转
右-右旋转
左-右旋转
右-左旋转
完整代码
import BinarySearchTree from '../binary-search-tree/BinarySearchTree';
export default class AvlTree extends BinarySearchTree {
/**
* @param {*} value
*/
insert(value) {
// Do the normal BST insert.
super.insert(value);
// Let's move up to the root and check balance factors along the way.
let currentNode = this.root.find(value);
while (currentNode) {
this.balance(currentNode);
currentNode = currentNode.parent;
}
}
/**
* @param {*} value
* @return {boolean}
*/
remove(value) {
// Do standard BST removal.
super.remove(value);
// Balance the tree starting from the root node.
this.balance(this.root);
}
/**
* @param {BinarySearchTreeNode} node
*/
balance(node) {
// If balance factor is not OK then try to balance the node.
if (node.balanceFactor > 1) {
// Left rotation.
if (node.left.balanceFactor > 0) {
// Left-Left rotation
this.rotateLeftLeft(node);
} else if (node.left.balanceFactor < 0) {
// Left-Right rotation.
this.rotateLeftRight(node);
}
} else if (node.balanceFactor < -1) {
// Right rotation.
if (node.right.balanceFactor < 0) {
// Right-Right rotation
this.rotateRightRight(node);
} else if (node.right.balanceFactor > 0) {
// Right-Left rotation.
this.rotateRightLeft(node);
}
}
}
/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateLeftLeft(rootNode) {
// Detach left node from root node.
const leftNode = rootNode.left;
rootNode.setLeft(null);
// Make left node to be a child of rootNode's parent.
if (rootNode.parent) {
rootNode.parent.setLeft(leftNode);
} else if (rootNode === this.root) {
// If root node is root then make left node to be a new root.
this.root = leftNode;
}
// If left node has a right child then detach it and
// attach it as a left child for rootNode.
if (leftNode.right) {
rootNode.setLeft(leftNode.right);
}
// Attach rootNode to the right of leftNode.
leftNode.setRight(rootNode);
}
/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateLeftRight(rootNode) {
// Detach left node from rootNode since it is going to be replaced.
const leftNode = rootNode.left;
rootNode.setLeft(null);
// Detach right node from leftNode.
const leftRightNode = leftNode.right;
leftNode.setRight(null);
// Preserve leftRightNode's left subtree.
if (leftRightNode.left) {
leftNode.setRight(leftRightNode.left);
leftRightNode.setLeft(null);
}
// Attach leftRightNode to the rootNode.
rootNode.setLeft(leftRightNode);
// Attach leftNode as left node for leftRight node.
leftRightNode.setLeft(leftNode);
// Do left-left rotation.
this.rotateLeftLeft(rootNode);
}
/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateRightLeft(rootNode) {
// Detach right node from rootNode since it is going to be replaced.
const rightNode = rootNode.right;
rootNode.setRight(null);
// Detach left node from rightNode.
const rightLeftNode = rightNode.left;
rightNode.setLeft(null);
if (rightLeftNode.right) {
rightNode.setLeft(rightLeftNode.right);
rightLeftNode.setRight(null);
}
// Attach rightLeftNode to the rootNode.
rootNode.setRight(rightLeftNode);
// Attach rightNode as right node for rightLeft node.
rightLeftNode.setRight(rightNode);
// Do right-right rotation.
this.rotateRightRight(rootNode);
}
/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateRightRight(rootNode) {
// Detach right node from root node.
const rightNode = rootNode.right;
rootNode.setRight(null);
// Make right node to be a child of rootNode's parent.
if (rootNode.parent) {
rootNode.parent.setRight(rightNode);
} else if (rootNode === this.root) {
// If root node is root then make right node to be a new root.
this.root = rightNode;
}
// If right node has a left child then detach it and
// attach it as a right child for rootNode.
if (rightNode.left) {
rootNode.setRight(rightNode.left);
}
// Attach rootNode to the left of rightNode.
rightNode.setLeft(rootNode);
}
}
