오늘은 optimal tree 구조에 대해서 정리해 보겠습니다.
일반적인 binary tree 가 잘못 만들어 질 경우 sequenced data 와 별반 차이가 없습니다.
O(n) 이 되지요
잘 분산 된 binary tree는 항상 O(logn)을 보장 합니다.
여기서는 잘 분산된 tree (optimal tree)를 만드는 알고리즘인 AVL, 2-3 tree, optimal tree 에 대해 정리해 보겠습니다.
AVL tree
insertion example
자료구조 : binary tree 와 동일
BF = balance factor = h(left node) - h(rirhgt node) = -1,0,1 이 되어야 한다.
BF의 범위가 -1.0.1 을 넘어 가면 rotaion 이 이루어 진다.
이때 , BF > 1 then 시계방향 rotation DB < -1 반시계 방향 rotation
이렇게 해서 각각 LL, LR, RR,RL 의 4개 rotation 이 발생 하게 된다.
2-3 tree
insertion example
동영상으로 친절하게 설명 된 예제 입니다. 우선 감을 잡아 보죠
자료구조 : 2 data, 3node link
AVL에서 발생하는 입력 삭제를 좀더 쉽게 하기 위한 구조 입니다.
AVL과는 다르게 tree가 위로 커진다고 보면 됩니다.
time complexity 는 동일해요
rotation, combine 이 이루어 집니다.
- 바이너리 탐색을 통해 노드를 추가 한다.
- 2data가 모두 저장된 경우는 데이터를 split. 이때 가장 큰 값을 새로운 노드에 넣고 중간 값이 부모에 추가 된다.
- 부모가 없을 때는 새로운 부모 노드가 만들어 진다.
- 부모가 있을 때는 2단계를 반복 한다.
red-black tree
- 노드는 레드 혹은 블랙 중의 하나이다. (A node is either red or black.)
- 루트 노드(시작점)은 블랙이다. (The root is black.)
- 모든 leaf node는 블랙이다. (All leaves are black. (The leaves are the NIL children.))
- 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. 한편 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다. (Both children of every red node are black. Therefore, a black node is the only possible parent for a red node.)
- 어떤 노드로부터 시작되어 leaf node에 도달하는 모든 경로에는 leaf node를 제외하면 모두 같은 개수의 블랙 노드가 있다.(Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.))
추가 되는 과정
- 바이너리 비교를 통해 추가 된다.
- 추가된 노드는 레드가 된다.
- 자신의 부모와 삼촌이 모두 레드이면 블랙을 바뀌고 할아버지가 레드가 된다.(recoloring)
- 자기의 부모 만이 레드 이면 rotation이 일어 난다. 로테이션 된 자식들은 레드가 된다.
- 이과정을 root에 도달 할때 까지 반복 한다.
연습 문제
2 12 3 9 10 13 4 0 11 6 8 5 14 1 을 AVL 과 red-black 으로 그려보기
정리
AVL 은 훨씬 엄격 하게 binary 규칙을 준수 합니다.
red-black tree는 AVL에 비해 서는 느슨한 체크가 이루어 집니다. 전체 노드를 다 들출 필요도 없구요
red 냐 black 이냐의 판별이 중요 하지 시빌링의 숫자 계산을 할필요가 없다는 장점이 있습니다.
최근 덧글