chan blog

13-3 AVL trees
MIT AVL Trees, AVL sortAVL treesClaim : AVL trees are balancedProveAVL insertAVL 구현 with the above MIT course(Wikipedia) AVL treeDefinitionBalance factorRemarkProperties(paper?) AVL TreesIntroduction13-3 AVL trees
https://www.youtube.com/watch?v=FNeL18KsWPc
MIT AVL Trees, AVL sort
Tree의 Height는 length of longest path 이다 from root to 한 leaf path로 가는.
Tree is balanced if the height of a tree is O(lg n)
 
depth는 root로 부터 count되는 것이고, height는 leaf로부터 계산되는 것이다.
a height of the node in the tree : length of logest path from it down to a leaf
height of a node = max(height(left child), height(right child)) + 1
https://youtu.be/FNeL18KsWPc?t=705 여기에서 좋은 한 가지 팁이 있는데, nullptr에 대한 즉, 자식이 없는 것에 대해 height를 -1로 계산해서 위의 한 노드의 height 계산을 좀 더 편하게 만들어주고 있다.
 
AVL trees
require heights of left & right children of every node to differ by at most 
. 
한 노드에 자식들이 있을 때, 왼쪽 자식의 높이를 
, 오른쪽 자신의 높이를 
이고, 따라서 조건은 
이여야 한다.
 
Claim : AVL trees are balanced
Prove
worst case is whenright subtree has height 1 more than left sub tree for every node.
는 minnimum of number of nodes in a AVL tree of height h.
따라서 
이다. h-2를 left라하고 h-1를 right라고 하자. 풀이를 위해서.
그리고 위의 식은 피보나치이고 
가 된다. 왜냐하면 +1이 붙어있을 테니. 
는 피보나치 수열이다. 

 인데, 피보나치 수열의 값이 왜 저렇게 되는지는 복잡한 내용이므로 그냥 그렇다고 치자. 
는 1보다 크다. 왜 그런지는 아직 알 필요없다. 
. 
식을 다시 바꾸어서

 
다른 방식으로

 
AVL insert
Simple BST insert
fix AVL property  from changed node up
so suppose x is the lowest node violating AVL
assum z = right(x) higher 
if x's right child is right-heavy or balanced, then do the left rotate
else right rotate(z) and then left rotate(x)
 
AVL sort:
xxxxxxxxxx
- insert n items    - $O(n\; lg\; n)$
- in-order traversal - $O(n)$
 
Abstract Data type
xxxxxxxxxx
- insert delete  - priority queue / heap / AVL
- min - priority queue
- successor / predecessor
 
AVL 구현 with the above MIT course
xxxxxxxxxx
#pragma once
#ifndef __AVL_TREE_H__
#define __AVL_TREE_H__
​
#include "precompiled.h"
​
template<typename avl_t_key, typename avl_t_value>
class avl_tree
{
public:
​
    struct node
    {
        node* parent;
        node* left;
        node* right;
        avl_t_key key;
        avl_t_value value;
        int height;
    };
​
    avl_tree() 
        : m_nil(allocate_node(avl_t_key(), avl_t_value(), 0))
        , m_root(m_nil)
        , m_node_count(0)
    {}
​
    ~avl_tree() 
    { 
        if (m_nil != nullptr && m_root != m_nil)
        {
            free_node_recursive(m_root);
            m_root = nullptr;
        }
​
        if (m_nil != nullptr)
        {
            free_node(m_nil);
            m_nil = nullptr;
        }
    }
​
    void insert(const avl_t_key& key, const avl_t_value& value)
    {
        node* n = allocate_node(key, value, 1);
        n->parent = m_nil;
        n->left = m_nil;
        n->right = m_nil;
        avl_insert(n);
        ++m_node_count;
    }
​
    void erase(const avl_t_key& key)
    {
        node* n = m_root;
        while (n != m_nil && key != n->key)
        {
            if (key < n->key)
                n = n->left;
            else
                n = n->right;
        }
​
        if (is_nil(*n) == false)
        {
            avl_delete(n);
            free_node(n);
            --m_node_count;
        }
    }
​
    const node& find(const avl_t_key& key) const
    {
        node* x = m_root;
        while (x != m_nil && key != x->key)
        {
            if (key < x->key)
                x = x->left;
            else
                x = x->right;
        }
        return *x;
    }
​
    bool is_nil(const node& n) const
    {
        return &n == m_nil;
    }
​
private:
​
    node* m_nil;
    node* m_root;
    int m_node_count;
​
    node* allocate_node(const avl_t_key& key, const avl_t_value& value, int height)
    {
        node* n = new node();
        n->parent = nullptr;
        n->left = nullptr;
        n->right = nullptr;
        n->key = key;
        n->value = value;
        n->height = height;
        return n;
    }
​
    void free_node(node* n)
    {
        CHASSERT(n, "node to be deleted is nullptr");
        delete n;
    }
​
    void free_node_recursive(node* node)
    {
        CHASSERT(node, "node to be deleted is nullptr");
        if (node->left != m_nil)
            free_node_recursive(node->left);
        if (node->right != m_nil)
            free_node_recursive(node->right);
        delete node;
    }
​
    node* get_minimum(node* x)
    {
        while (x->left != m_nil)
            x = x->left;
        return x;
    }
​
    void avl_left_rotate(node* x)
    {
        node* y = x->right;
        
        if (y != m_nil)
        {
            int x_height = x->height;
            int y_height = y->height;
​
            x->right = y->left;
​
            if (y->left != m_nil)
            {
                y->left->parent = x;
            }
​
            y->parent = x->parent;
​
            if (x->parent == m_nil)
            {
                m_root = y;
            }
            else if (x == x->parent->left)
            {
                x->parent->left = y;
            }
            else
            {
                x->parent->right = y;
            }
​
            y->left = x;
            x->parent = y;
​
            swap_value(x->height, y->height);
        }
    }
​
    void avl_right_rotate(node* y)
    {
        node* x = y->left;
​
        if (x != m_nil)
        {
            y->left = x->right;
​
            if (x->right != m_nil)
            {
                x->right->parent = y;
            }
​
            x->parent = y->parent;
​
            if (y->parent == m_nil)
            {
                m_root = x;
            }
            else if (y == y->parent->left)
            {
                y->parent->left = x;
            }
            else
            {
                y->parent->right = x;
            }
​
            x->right = y;
            y->parent = x;
​
            swap_value(x->height, y->height);
        }
    }
​
    // node z is the inserted node
    void avl_rebalance(node* z)
    {
        node* current_node = z;
        while (current_node != m_nil)
        {
            node* current_parent = current_node->parent;
            node* current_left = current_node->left;
            node* current_right = current_node->right;
            int balance = current_right->height - current_left->height;
            if (abs(balance) >= 2)
            {
                // avl property violation
                if (balance > 0)
                {
                    // right heavy
                    int child_balance = current_right->right->height - current_right->left->height;
​
                    if (child_balance >= 0)
                    {
                        // also child is right heavy
                        // then LEFT_ROTATE
                        avl_left_rotate(current_node);
                    }
                    else
                    {
                        // child is left heavy 
                        // RIGHT_ROTATE(child)
                        // LEFT_ROTATE(parent)
                        avl_right_rotate(current_right);
                        avl_left_rotate(current_node);
                    }
                }
                else
                {
                    // left heavy
                    int child_balance = current_left->right->height - current_left->left->height;
​
                    if (child_balance >= 0)
                    {
                        // child right heavy
                        // LEFT_ROTATE(child)
                        // RIGHT_ROTATE(parent)
                        avl_left_rotate(current_left);
                        avl_right_rotate(current_node);
                    }
                    else
                    {
                        // also child is left heavy
                        // then RIGHT_ROTATE
                        avl_right_rotate(current_node);
                    }
                }
            }
            current_node->height = 1 + get_max(current_node->left->height, current_node->right->height);
            current_node = current_parent;
        }
​
        m_root->height = 1 + get_max(m_root->left->height, m_root->right->height);
    }
​
    void avl_insert(node* z)
    {
        node* y = m_nil;
        node* x = m_root;
         
        while (x != m_nil)
        {
            y = x;
            
            if (z->key < x->key)
                x = x->left;
            else
                x = x->right;
        }
​
        z->parent = y;
​
        if (y == m_nil)
            m_root = z;
        else if (z->key < y->key)
            y->left = z;
        else
            y->right = z;
​
        avl_rebalance(z->parent);
    }
​
    void avl_transplant(node* u, node* v)
    {
        if (u->parent == m_nil)
        {
            m_root = v;
        }
        else if (u == u->parent->left)
        {
            u->parent->left = v;
        }
        else
        {
            u->parent->right = v;
        }
​
        if (v != m_nil)
            v->parent = u->parent;
    }
​
    void avl_delete(node* z)
    {
        node* x = m_nil;
        node* y = z;
​
        if (z->left == m_nil)
        {
            x = z->right;
            avl_transplant(z, z->right);
​
            if (x == m_nil)
            {
                x = z->parent;
            }
        }
        else if (z->right == m_nil)
        {
            x = z->left;
            avl_transplant(z, z->left);
​
            if (x == m_nil)
            {
                x = z->parent;
            }
        }
        else
        {
            y = get_minimum(z->right);
            x = y;
​
            if (y->parent != z)
            {
                x = x->parent;
​
                avl_transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
​
            avl_transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
        }
​
        avl_rebalance(x);
    }
};
​
#endif
​
 
https://en.wikipedia.org/wiki/AVL_tree
(Wikipedia) AVL tree
Definition
Balance factor
binary tree에서, 한 node의 balance factor는 height difference로 정의된다

그 노드의 child sub-trees에 대해. 한 binary tree는 AVL tree라고 정의되는데, 만약 그 invariant가

트리에 있는 모든 노드에 유효하다면.

인 한 노드는 "left-heavy"하다고 불려지고, 

을 가진 것은 "right-heavy"하다고 불려지고, 

을 가진 것은 가끔씩 간단히 "balanced"라고 불려진다.
 
Remark
다음에 나오는 것들 중에서, nodes들과 그 노드들을 root로하는 sub-trees사이의 1:1 대응이 있기 때문에, 한 오브젝트의 이름은 가끔씩 노드를 가리키기 위해 사용되거나, 가끔씩 그 sub-tree를 언급하기 위해 사용된다.
 
Properties
Balance factors는 이전의 balance factors와 height의 변화를 알고나서 최신으로 유지될 수 있다 - absolute height를 알 필요는 없다. AVL balance information을 전통적인 방식으로 유지하기 위해, node마다 두 개의 비트가 충분하다. 그러나, 최신의 연구는 만약 AVL tree가 1또는 2가 허용되는 delta ranks를 가진 - "위로 올라갈 때, 높이 1 또는 2의 추가 증가가 있다"라는 것을 의미하는 - rank balanced tree로서 구현된다면, 이것은 1비트로 될 수 있다는 것을 보여주었다.
n개의 노드들을 가진 AVL tree의 그 높이 h는 (longest path에서 edges의 개수로 세어지는),  다음의 interval에 있따:

여기에서 
는 황금비이고, 
이다. 이것은 왜냐하면 AVL tree height가 적어도 

노드들을 포함하기 때문이다. 여기에서 
은 seed values 
인 Fibonnaci 수열이다.
 
 
 
 
 
 
 
 
 
https://web.archive.org/web/20190731124716/https://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html
(paper?) AVL Trees
Introduction
특별한 사전 경고 없이, binary search trees는 임의로 unbalanced하게 될 수 있고, 이것은 N개의 노드들을 가진 한 트리에 대해 연산을 실행하면 
의  worst-case times을 이끌 수 있다. 만약 우리가 binary tree 완전하게 balanced하게 유지한다면, lookup은 
의 복잡도를 가지게 된다. 하지만 삽입 또는 삭제는 balance를 유지하기 위해 그 트리를 완전히 재배치 하는 것을 요구할지도 모른다. 그리고 이것은 
의 worst time을 이끌 게 된다. 2-3 tree는 완전히 balanced되도록 요구된다 (root에서 leaves로 가는 모든 paths들이 정확히 같은 길이를 가진다), 그러나 내부 노드들이 2개 또는 3개의 자식들을 가지게 하여 어떤 느슨한 부분이 만들어진다. 이 느슨한 부분은 balance condition이 유지되게 하는데, 추가되거나 제거될 root에서 leaf로가는 경로 에서 또는 그 가까운 곳에서 adjustments를 요구하면서.
다른 접근법은 AVL trees (그것의 발명자들의 이름을 따서)에 의해 취해진다. AVL treesms "거의" balanced한 binary search tree이다. 한 tree의 height가 root에서 한 leaf로 가는 가장 긴 path에 있는 nodes들의 개수라는 것을 상기하자. 우리는 empty tree는 height가 0이라고 말할 것이다. 이 컨벤션으로, 비어있지 않은 empty tree의 높이는 그것의 두 개의 subtrees의 최대 높이보다 하나 더 크다. 만약 height에서 1돠 더 차이가는 subtrees를 가진 노드가 없다면, 그 binary search tree는 AVL tree이다. 예를들어,
이것은 binary search tree이지만, AVL tree는 아니다. 왜냐하면 node 4의 자식들은 heights 0 (empty)와 2를 가진다. 각 노드의 height 그 노드 다음에 쓰여져 있어서, 너는 node 4가 이 케이스에서 AVL 조건을 위반한 유일한 노드라는 것을 알 수 있다. node 4와 그것의 자손을 다시 배치하여, 우리는 이 트리를 같은 데이터를 가진 binary search tree로 바꾼다.  그리고 이것은 AVL condition을 만족시킨다.
perfactly balanced binary tree는 AVL tree이다. 만약 그것이 N개의 노드들을 가진다면, 그것의 높이는 

이다. h의 높이를 가진 최악으로 가능한 (가장 unbalanced한)  AVL tree는 무엇인가? 그것은 다음으로 정의된 
이다 : 
는 empty tree이고, 
는 단일 노드를 포함하는 트리이다. 
에 대해, 
는 두 자식을 가진 root에서의 한 노드를 가진다. 그 자식들은 
이고 
이다. 여기에 
에 대한 그림이 있다:
우리는 keys를 생략했지만, subtrees의 heights를 표기했다. 각 non-leaf node는 그것의 right subtree보다 한 level이 더 높은 left subtree를 가지고 있다. 
에 얼마나 많은 노드들이 있는가? 처음에 leaves들을 세어보자. 만약 
이 
에 있는 leaves의 개수라면, 그러면 
, 
, 이고, 
에 대해, 
. 따라서, 
 숫자들은 유명한 Fibonacci numbers이다. 사실, 위에서 정의한 trees 
는 가끔씩 Fibonacci trees라고 불려진다. binary tree에서 internal nodes의 개수는 항상 leaves의 개수보다 한 개 더 작다 (너는 왜 그런지 알 수 있는가? @chan : 이게 맞는 주장인지 모르겠다.), 그래서 
에 있는 노드들의 개수는 대략 
이다. 그 Fibonacci numbers 
는 h에 대해 exponential function으로 늘어난다는 것으로 알려져있다. 그래서 
의 height는 nodes들의 개수와 함께 logarithmically하게 증가한다. 사실, N개의 노드들을 가진 AVL tree의 높이가 
로 제한된다는 것이 보여질 수 있다. 다시 말해서, 최악의 가능한 AVL tree는 최상으로 가능한 것 보다 
배 더 작은 높이를 갖는다 (@chan : 더 높은 아닌가). 특히, size N의 AVL tree에서의 lookup를 위한 시간은 
이다.
 
 
 
Introduction to Algorithms
13-3 AVL trees
한 AVL tree는 height balanced인 binary search tree이다; 각 node x에 대해, x의 left와 right subtrees의 높이는 최대 1만큼 차이가 난다. AVL tree를 구현하기 위해, 우리는 각 노드에서 extra attribute를 유지한다: x.h는 node x의 height이다. 어떤 다른 binary search tree T에 대해, 우리는 T.root가 root node를 가리킨다고 가정한다.
a. n개의 nodes를 가진 AVL tree가 높이 
를 가진다는 것을 증명해라. (Hint: height h인 AVL tree가 적어도 
 nodes들을 가진다는 것을 증명해라. 여기에서 
는 h번째 Fibonacci number이다.)
x가 root node라고 가정하면, x의 left와 right child를 root로 하는 subtree의 높이 차는 최대 1이다. 즉, left subtree가 a의 height를 가진다면, right subtree는 a-1, a, a+1의 height를 가질 수 있다는 것이다.
 
b. AVL tree에 insert하기 위해, 우리는 처음에 한 노드를 binary search tree order로 적절한 장소에 배치한다. 그 이후에, 그 트리는 더 이상 height balanced하지 않을지도 모른다. 구체적으로, 어떤 노드의 left and right children의 높이가 2정도 차이날 수 있을지도 모른다. procedure BALANCE(x)를 설명해라. 이것은 x를 root로 하는 subtree를 받는데, 그 노드의 left and right children은 height balanced이고, 최대로 2정도 차이나는 height를 가지고 있다, 즉 

라는 것이다. 그리고 그 subtree를 가진 채, x를 root로 하는 subtree가 height balanced 되도록 변경한다 (Hint: Use rotations.)
c. part(b)를 사용하여, AVL tree내에서 nodeㅌ를 취하고, 새롭게 생성된 node z를 (그 key는 이미 채워져 있다)  취하고, x를 root로 하는 subtree에 z를 추가하는 recursive procedure AVL_INSERT(x, z)를 설명해라. 그리고 그것은 x가 AVL tree의 root인 특성을 유지한다. section 12.3에서의 TREE-INSERT에서 처럼, z.key가 이미 채워져있고, z.left = NIL이고 z.right = NIL이라고 가정해라; 또한 z.h = 0이라고 가정해라. 따라서, node z를 AVL tree T를 넣기 위해, 우리는 AVL-INSERT(T.root, z)를 호출한다.
d. n개의 노드의 AVL tree에서 작동되는 AVL-INSERT가 
 시간이 걸리고, 
의 rotations을 수행한다는 것을 보여주어라.

13 Red-black Trees - 13-3 AVL Tree

댓글