1. Въведение
В този урок ще представим AVL Tree и ще разгледаме алгоритми за вмъкване, изтриване и търсене на стойности.
2. Какво е AVL Tree?
Дървото AVL, кръстено на изобретателите си Adelson-Velsky и Landis, е самобалансиращо се двоично дърво за търсене (BST).
Самобалансиращо се дърво е двоично дърво за търсене, което балансира височината след вмъкване и изтриване съгласно някои правила за балансиране.
Сложността на BST в най-лошия случай е функция от височината на дървото. По-конкретно, най-дългият път от корена на дървото до възел. За BST с N възли, нека кажем, че всеки възел има само нула или едно дете. Следователно височината му е равна на N, а времето за търсене в най-лошия случай е O (N). Така че нашата основна цел в BST е да поддържаме максималната височина близо до log (N).
Балансният фактор на възел N е височина (вдясно (N)) - височина (вляво (N)) . В AVL дърво коефициентът на баланс на възел може да бъде само една от стойностите 1, 0 или -1.
Нека дефинираме обект Node за нашето дърво:
public class Node { int key; int height; Node left; Node right; ... }След това нека дефинираме AVLTree :
public class AVLTree { private Node root; void updateHeight(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); } int height(Node n) { return n == null ? -1 : n.height; } int getBalance(Node n) { return (n == null) ? 0 : height(n.right) - height(n.left); } ... }3. Как да балансираме AVL дърво?
Дървото AVL проверява коефициента на баланс на своите възли след вмъкването или изтриването на възел. Ако коефициентът на баланс на възел е по-голям от един или по-малък от -1, дървото се ребалансира.
Има две операции за ребалансиране на дърво:
- дясно въртене и
- ляво въртене.
3.1. Право въртене
Нека започнем с правилната ротация.
Да приемем, че имаме BST, наречен T1, с Y като корен възел, X като ляво дете на Y и Z като дясно дете на X. Като се имат предвид характеристиките на BST, знаем, че X <Z <Y.
След дясно завъртане на Y имаме дърво, наречено T2 с X като корен и Y като дясно дете на X и Z като ляво дете на Y. T2 все още е BST, тъй като поддържа реда X <Z <Y .
Нека да разгледаме правилната операция на въртене за нашия AVLTree :
Node rotateRight(Node y) { Node x = y.left; Node z = x.right; x.right = y; y.left = z; updateHeight(y); updateHeight(x); return x; }3.2. Операция на ляво въртене
Имаме и операция на ляво въртене.
Да приемем BST, наречен T1, с Y като основен възел, X като дясно дете на Y и Z като ляво дете на X. Като се има предвид това, знаем, че Y <Z <X.
След ляво завъртане на Y, имаме дърво, наречено T2 с X като корен и Y като ляво дете на X и Z като дясно дете на Y. T2 все още е BST, защото поддържа реда Y <Z <X .
Нека да разгледаме операцията за ляво въртене за нашия AVLTree :
Node rotateLeft(Node y) { Node x = y.right; Node z = x.left; x.left = y; y.right = z; updateHeight(y); updateHeight(x); return x; }3.3. Техники за ребалансиране
Можем да използваме операциите за дясно въртене и ляво въртене в по-сложни комбинации, за да поддържаме балансирано AVL Tree след всяка промяна в неговите възли . В небалансирана структура поне един възел има коефициент на баланс, равен на 2 или -2. Нека да видим как можем да балансираме дървото в тези ситуации.
Когато коефициентът на баланс на възел Z е 2, поддървото с Z като корен е в едно от тези две състояния, разглеждайки Y като дясното дете на Z.
За първия случай височината в дясното дете на Y (X) е по-голяма от височината на лявото дете (T2). Можем да ребалансираме дървото лесно чрез ляво завъртане на Z.
За втория случай височината на дясното дете на Y (T4) е по-малка от височината на лявото дете (X). Тази ситуация се нуждае от комбинация от операции на ротация.
В този случай първо завъртаме Y надясно, така че дървото получава същата форма като предишния случай. Тогава можем да балансираме дървото чрез ляво завъртане на Z.
Също така, когато коефициентът на баланс на възел Z е -2, неговото поддърво е в едно от тези две състояния, така че ние разглеждаме Z като корен и Y като негово ляво дете.
Височината в лявото дете на Y е по-голяма от тази на дясното му дете, така че балансираме дървото с дясното завъртане на Z.
Или във втория случай, дясното дете на Y има по-голяма височина от лявото си дете.
И така, първо, ние го трансформираме в предишната форма с ляво завъртане на Y, след което балансираме дървото с дясното завъртане на Z.
Нека да разгледаме операцията по ребаланс за нашия AVLTree :
Node rebalance(Node z) { updateHeight(z); int balance = getBalance(z); if (balance > 1) { if (height(z.right.right) > height(z.right.left)) { z = rotateLeft(z); } else { z.right = rotateRight(z.right); z = rotateLeft(z); } } else if (balance height(z.left.right)) z = rotateRight(z); else { z.left = rotateLeft(z.left); z = rotateRight(z); } } return z; }Ще използваме ребаланс след вмъкване или изтриване на възел за всички възли в пътя от променения възел до корена.
4. Поставете възел
Когато ще вмъкнем ключ в дървото, трябва да намерим правилното му положение, за да предадем правилата BST. Затова започваме от корена и сравняваме стойността му с новия ключ. Ако ключът е по-голям, ние продължаваме надясно - в противен случай отиваме на лявото дете.
След като намерим правилния родителски възел, тогава добавяме новия ключ като възел отляво или отдясно, в зависимост от стойността.
След вмъкване на възела имаме BST, но може да не е AVL дърво. Следователно проверяваме факторите на баланса и ребалансираме BST за всички възли в пътя от новия възел до корена.
Нека да разгледаме операцията за вмъкване:
Node insert(Node node, int key) { if (node == null) { return new Node(key); } else if (node.key > key) { node.left = insert(node.left, key); } else if (node.key < key) { node.right = insert(node.right, key); } else { throw new RuntimeException("duplicate Key!"); } return rebalance(node); }Важно е да запомните, че ключът е уникален в дървото - нито един възел не споделя един и същ ключ.
Сложността във времето на алгоритъма за вмъкване е функция на височината. Тъй като нашето дърво е балансирано, можем да приемем, че сложността на времето в най-лошия случай е O (log (N)).
5. Изтрийте възел
За да изтрием ключ от дървото, първо трябва да го намерим в BST.
След като намерим възела (наречен Z), трябва да представим новия кандидат, който да бъде негов заместител в дървото. Ако Z е лист, кандидатът е празен. Ако Z има само едно дете, това дете е кандидатът, но ако Z има две деца, процесът е малко по-сложен.
Assume the right child of Z called Y. First, we find the leftmost node of the Y and call it X. Then, we set the new value of Z equal to X ‘s value and continue to delete X from Y.
Finally, we call the rebalance method at the end to keep the BST an AVL Tree.
Here is our delete method:
Node delete(Node node, int key) { if (node == null) { return node; } else if (node.key > key) { node.left = delete(node.left, key); } else if (node.key < key) { node.right = delete(node.right, key); } else { if (node.left == null || node.right == null) { node = (node.left == null) ? node.right : node.left; } else { Node mostLeftChild = mostLeftChild(node.right); node.key = mostLeftChild.key; node.right = delete(node.right, node.key); } } if (node != null) { node = rebalance(node); } return node; }The time complexity of the delete algorithm is a function of the height of the tree. Similar to the insert method, we can assume that time complexity in the worst case is O(log(N)).
6. Search for a Node
Searching for a node in an AVL Tree is the same as with any BST.
Start from the root of the tree and compare the key with the value of the node. If the key equals the value, return the node. If the key is greater, search from the right child, otherwise continue the search from the left child.
Сложността във времето на търсенето е функция на височината. Можем да приемем, че сложността на времето в най-лошия случай е O (log (N)).
Нека видим примерния код:
Node find(int key) { Node current = root; while (current != null) { if (current.key == key) { break; } current = current.key < key ? current.right : current.left; } return current; }7. Заключение
В този урок внедрихме AVL дърво с операции за вмъкване, изтриване и търсене.
Както винаги, можете да намерите кода на Github.