Post Lists

2020년 10월 17일 토요일

13 Red-black Trees - 13-3 AVL Tree

13-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

  1. Simple BST insert

  2. 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:

 

Abstract Data type

 


AVL 구현 with the above MIT course


 

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이다. 예를들어,

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

perfactly balanced binary tree는 AVL tree이다. 만약 그것이 N개의 노드들을 가진다면, 그것의 높이는 이다. h의 높이를 가진 최악으로 가능한 (가장 unbalanced한) AVL tree는 무엇인가? 그것은 다음으로 정의된 이다 : 는 empty tree이고, 는 단일 노드를 포함하는 트리이다. 에 대해, 는 두 자식을 가진 root에서의 한 노드를 가진다. 그 자식들은 이고 이다. 여기에 에 대한 그림이 있다:

avl_example_3

우리는 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 treeheight 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을 수행한다는 것을 보여주어라.