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

$\pm1$ .

$h_l$ $h_r$ $|h_l - h_r| \leq 1$ 이여야 한다.

Claim : AVL trees are balanced

Prove

worst case is whenright subtree has height 1 more than left sub tree for every node.

$N_h$ 는 minnimum of number of nodes in a AVL tree of height h.

$N_h = N_{h-1} + N_{h-2} + 1$ 이다. h-2를 left라하고 h-1를 right라고 하자. 풀이를 위해서.

$N_h > F_h$ $F_h$ 는 피보나치 수열이다.

$N_h > F_h = \frac{\varphi^h}{\sqrt{5}}$ $\varphi$ $\varphi = 1.618...$ .

식을 다시 바꾸어서

$\frac{\varphi^h}{\sqrt{5}} < n (= N_h)$

$h - ~ < log_\varphi n \approx 1.440 \; lg \; n$

다른 방식으로

$N_h = 1 + N_{h-1} + N_{h-2}$

$N_h > 1 + 2N_{h-2}$

$N_h > 2N_{h-2}$

$N_h = O(2^{h/2})$

$h < 2 \;lg\;n$

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로 정의된다

\text{BalanceFactor(node) := Height(RightSubtree(node)) - Height(LeftSubtree(node))}

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

\text{BalanceFactor(node)} \in \{-1, 0, 1\}

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

$\text{BalanceFactor(node) < 0}$ $\text{BalanceFactor(node) > 0}$ $\text{BalanceFactor(node) = 0}$ 을 가진 것은 가끔씩 간단히 "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에 있따:

log_2(n+1) - 1 \leq h < log_\varphi(n + 2) + b

$\varphi$ $b \approx -1.3277$ $F_{height + 2} -1$ $\{F_n\}$ $F_1 = 1, F_2 = 1$ 인 Fibonnaci 수열이다.

https://web.archive.org/web/20190731124716/https://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html

(paper?) AVL Trees

Introduction

$O(n)$ $O(lg\;N)$ $O(n)$ 의 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이다. 예를들어,

avl_example_1

이것은 binary search tree이지만, AVL tree는 아니다. 왜냐하면 node 4의 자식들은 heights 0 (empty)와 2를 가진다. 각 노드의 height 그 노드 다음에 쓰여져 있어서, 너는 node 4가 이 케이스에서 AVL 조건을 위반한 유일한 노드라는 것을 알 수 있다. node 4와 그것의 자손을 다시 배치하여, 우리는 이 트리를 같은 데이터를 가진 binary search tree로 바꾼다. 그리고 이것은 AVL condition을 만족시킨다.

avl_example_fixup

$log_2(N + 1)$ $T_h$ $T_0$ $T_1$ $h > 1$ $T_h$ $T_{h-1}$ $T_{h-2}$ $T_4$ 에 대한 그림이 있다:

avl_example_3

$T_h$ $f_n$ $T_n$ $f_0 =0$ $f_1 = 1$ $h > 1$ $f_h = f_{h-1} + f_{h-2}$ $f_h$ Fibonacci numbers $T_h$ Fibonacci trees $T_h$ $2f_n$ $f_h$ $T_h$ $1.44log_2N$ $1 - 1/2$ $O(lg\;N)$ 이다.

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. $O(lg\;n)$ $F_h$ $F_h$ 는 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.BALANCE(x) $|x.right.h - x.left.h| \leq 2$ 라는 것이다. 그리고 그 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.AVL-INSERT $O(lg\;n)$ $O(1)$ 의 rotations을 수행한다는 것을 보여주어라.

chan blog

Post Lists

2020년 10월 17일 토요일

13 Red-black Trees - 13-3 AVL Tree

MIT AVL Trees, AVL sort

AVL trees

Claim : AVL trees are balanced

Prove

AVL insert

AVL 구현 with the above MIT course

(Wikipedia) AVL tree

Definition

Balance factor

Remark

Properties

(paper?) AVL Trees

Introduction

13-3 AVL trees

댓글 없음:

댓글 쓰기