[자료구조] AVL 트리

출처 : internet512.chonbuk.ac.kr/.../AVL/avl.html

    

높이 균형 트리(Hieght-Balanced Tree)라고도 부르며, 탐색 시간을 줄이기 위해서 좌,우측 부 트리의 높이가 1 이상 차이가 나지 않도록 균형을 유지해 주는 이진 트리로 동적 탐색 트리(Dynamic Search Tree)이다.     탐색시 비교 횟수가 작고, 노드 삽입시 트리의 균형이 크게 변하지 않는 성질을 만족하는 트리이다. T가 좌측과 우측 부트리인 TL과 TR을 가진 이진 트리라 할 때 아래의 조건을 만족하면 T는 높이가 균형을 이룬다. TL과 TR의 높이가 균형을 이루며 |HL-HR| ≤ 1 (HL, HR은 TL과 TR의 높이)

AVL 트리	AVL 트리가 아닌 경우

　　

높이 균형 트리를 구성하는데 있어서, 각 노드에 그 노드의 좌측, 우측 부트리 사이의 높이차를 나타내는 균형 인수(Balance Factor : BF)를 두어 어떠한 노드에 대해서도 BF는 -1, 0, +1 중의 한 개의 값을 취하여 만약 BF가 ±2가 되면 진행이 되지 않기 때문에 다음 4가지 회전을 수행해서 균형을 맞도록 유지한다. LL : 삽입된 새 노드 X는 X에 가장 가까운 조상 노드 A의 좌측 부트리의 좌측 부트리에 삽입한다. LR : X는 A의 좌측 부트리의 우측 부트리에 삽입한다. RR : X는 A의 우측 부트리의 우측 부트리에 삽입한다. RL : X는 A의 우측 부트리의 좌측 부트리에 삽입한다.

출처 : 위키피디아

Operations

The basic operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree, but modifications are preceded or followed by one or more operations called tree rotations, which help to restore the height balance of the subtrees.

[edit]Lookup

Lookup in an AVL tree is performed exactly as in an unbalanced binary search tree. Because of the height-balancing of the tree, a lookup takes O(log n) time. No special actions need to be taken, and the tree's structure is not modified by lookups. (This is in contrast to splay tree lookups, which do modify their tree's structure.)

If each node additionally records the size of its subtree (including itself and its descendants), then the nodes can be retrieved by index in O(log n) time as well.

Once a node has been found in a balanced tree, the next or previous nodes can be explored in amortized constant time. A few cases require traversing up to 2×log(n) links. However exploring all n nodes in the tree in this manner would use each link exactly twice, and there are n−1 links, so the amortized cost is 2×(n−1)/n, approximately 2.

[edit]Insertion

Pictorial description of how rotations cause rebalancing tree, and then retracing one's steps toward the root updating the balance factor of the nodes. The numbered circles represent the nodes being balanced. The lettered triangles represent subtrees which are themselves balanced BSTs

After inserting a node, it is necessary to check each of the node's ancestors for consistency with the rules of AVL (in what order? bottom-up, right?). For each node checked, if the balance factor remains −1, 0, or +1 then no rotations are necessary. However, if the balance factor becomes ±2 then the subtree rooted at this node is unbalanced. If insertions are performed serially, after each insertion, at most one tree rotation is needed to restore the entire tree to the rules of AVL.

There are four cases which need to be considered, of which two are symmetric to the other two. Let P be the root of the unbalanced subtree. Let R be the right child of P. Let L be the left child of P.

Right-Right case and Right-Left case: If the balance factor of P is −2, then the right subtree outweighs the left subtree of the given node, and the balance factor of the right child (R) must be checked. If the balance factor of R is < 0, a left rotation is needed with P as the root. If the balance factor of R is +1, a double left rotation (with respect to P) is needed. The first rotation is a right rotation with R as the root. The second is a left rotation with P as the root.

Left-Left case and Left-Right case: If the balance factor of P is +2, then the left subtree outweighs the right subtree of the given node, and the balance factor of the left child (L) must be checked. If the balance factor of L is > 0, a right rotation is needed with P as the root. If the balance factor of L is −1, a double right rotation(with respect to P) is needed. The first rotation is a left rotation with L as the root. The second is a right rotation with P as the root.

Algorithms for all the above four cases can be found here.

[edit]Deletion

If the node is a leaf or has only one child, remove it. Otherwise, replace it with either the largest in its left subtree (inorder predecessor) or the smallest in its right subtree (inorder successor), and remove that node. The node that was found as a replacement has at most one subtree. After deletion, retrace the path back up the tree (parent of the replacement) to the root, adjusting the balance factors as needed.

As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.

In addition to the balancing described above for insertions, if the balance factor for the tree is 2 and that of the left subtree is 0, a right rotation must be performed on P. The mirror of this case is also necessary.

The retracing can stop if the balance factor becomes −1 or +1 indicating that the height of that subtree has remained unchanged. If the balance factor becomes 0 then the height of the subtree has decreased by one and the retracing needs to continue. If the balance factor becomes −2 or +2 then the subtree is unbalanced and needs to be rotated to fix it. If the rotation leaves the subtree's balance factor at 0 then the retracing towards the root must continue since the height of this subtree has decreased by one. This is in contrast to an insertion where a rotation resulting in a balance factor of 0 indicated that the subtree's height has remained unchanged.

The time required is O(log n) for lookup, plus a maximum of O(log n) rotations on the way back to the root, so the operation can be completed in O(log n) time.