AVL Tree, Red Black Tree

AVL Tree, Red Black Tree

-

AVL 과 Red Black Tree 는 모두 Self balancing B-Tree 이며, Self balancing 을 최적화하여 유지하는 알고리즘이 적용된 Tree 라고 보면 된다.

Red Black Tree 가 AVL 보다 성능이 좋아 Red Black Tree 가 잘 쓰인다.

AVL Tree

-

가장 초기에 나온 balanced B-Tree.

-

각각의 노드마다 왼쪽과 오른쪽 sub-tree 의 높이차이에 대한 정보를 가지며, sub-tree 의 높이 차이가 1보다 크지 않은 성질을 가진다.

-

O(log n) 으로 검색, 삽입, 삭제를 할 수 있다.

-

삽입, 삭제를 할 때 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 Red Black B-Tree 만큼 효율이 좋지 않아 자주 쓰이지는 않는다.

Red Black Tree

-

balanced B-Tree 로 자료구조는 복잡하지만 효율적이고, 최악의 경우에도 우수한 performance 를 보인다.

-

각 노드는 레드 또는 블랙의 속성을 가지고 있다.

    1. 루트 노드는 블랙

    2. 모든 리프 노드는 블랙

    3. 레드 노드의 자식 노드 양쪽은 언제나 블랙. ( 레드 노드는 연달아 나타날 수 없고, 블랙 노마든이 레드 노드의 부모가 될 수 있음 )

    4. 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 같은 개수의 블랙 노드가 있다.

-

AVL 은 Red Black Tree 보다 더 엄격하게 균형 잡혀 있어, 삽입과 삭제 시 더 많은 rotations 이 필요하다.

O(log n)으로 검색, 삽입, 삭제를 할 수 있다.

avl tree, big O, binary tree, o log n, red black b tree, Red Black Tree, self balancing b tree, self balancing optimization, worst case performance