각 노드의 자식은 최대 2개
이진 트리의 순회는 중위(in-order), 전위(pre-order), 후위(post-order)가 있다.
1. in-order : 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지 순서로 방문한다.
위 이미지를 예로 들 경우 : H, D, I, J, E, B, A, F, C, G
2. pre-order : 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지 순서로 방문한다.
위 이미지를 예로 들 경우 : A, D, H, I, B, J, E, F, C, G
3. post-order : 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드 순서로 방문한다.
위 이미지를 예로 들 경우 : H, I, D, J, E, B, F, G, C, A
트리의 모든 레벨에서 노드가 꽉 차 있는 이진 트리이다. 마지막 레벨은 꽉 차 있지 않아도 괜찮지만 왼쪽에서 오른쪽으로 채워져야한다.
배열을 사용해 효과적으로 표현 가능(노드 개수 n, root가 1에서 시작할 경우
i 번째 노드는 parent(i) = i/2, left_child(i) = 2i, right_child(i) = 2i+1의 인덱스)
모든 노드가 0개 혹은 2개의 자식 노드를 가진다.
Complete, Full Binary Tree의 특징을 모두 만족한다.
모든 말단 노드는 같은 레벨에 있어야 하고, 마지막 단게에서 노드의 개수가 최대
모든 내부 노드는 2개의 자식 노드를 가짐
정렬된 이진 트리이다.
힙이란 트리 기반 자료구조로 힙 속성(max 힙의 경우 부모 노드는 반드시 자식 노드보다 값이 큼)을 만족
힙 속성으로 인해 우선순위 큐를 구현하는데 적합
이진 힙은 Tree 중에서도 배열에 기반한 Complete Binary Tree
이다.
힙 속성으로 인해 삽입이나 삭제시 속성을 유지한다. 시간복잡도는 O(logN)
BST이다. 하지만, BST와 다르게 불균형이 생기지 않게 조건이 있다.
즉 트리를 균형상태로 유지한다
삽입, 삭제, 탐색 모두 시간 복잡도가 O(logN)
조건
- 루트 노드는 black
- 모든 이파리 노드는 black이고 NIL이다. (NIL: null leaf)
- 노드의 색이 red 인 경우 자식은 모드 black
- 모든 리프노드에서 루트노드까지 가는 경로에 만나는 black 노드의 수는 같다
삽입
BST의 특성을 유지하며 노드를 삽입. 삽입된 노드의 색은 RED
RED인 이유는 black-height 변경을 최소화
Double Red의 발생 해결하기
위 그림의 경우 3번 조건을 위배(Double Red 문제)
U 노드(삼촌 노드)가 검은색 -> Restructuring
Restructuring 과정
1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순 정렬
2. 중간값을 부모로 만들고 나머지 둘을 자식으로
3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색
U 노드(삼촌 노드)가 빨간색 -> Recoloring
Recoloring 과정
1. 새로운 노드(N)의 부모(P)와 삼촌(U)를 검은색으로 바꾸고 조상(G)를 빨간색
(만약 조상(G)이 루트면 검은색으로, 바꾸고 만약 또 Double Red 발생시 계속 반복)