[자료구조] 트리

이창민·2022년 8월 10일
0

자료구조

목록 보기
3/5

Tree

  • 트리는 스택과 큐와 같은 선형 구조가 아닌 비선형 자료구조
  • 트리는 계층 관계를 나타내는 자료구조
  • 트리는 노드로 이뤄진 자료구조이다.
    - 트리는 하나의 루트 노드를 가짐
    - 루트 노드는 0개 이상의 자식 노드를 갖고 자식 노드들 또한 0개 이상의 자식 노드를 가짐(반복)

이진 트리(Binary Tree)

  • 각 노드의 자식은 최대 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

이진 트리 종류

Complete Binary Tree

트리의 모든 레벨에서 노드가 꽉 차 있는 이진 트리이다. 마지막 레벨은 꽉 차 있지 않아도 괜찮지만 왼쪽에서 오른쪽으로 채워져야한다.
배열을 사용해 효과적으로 표현 가능(노드 개수 n, root가 1에서 시작할 경우
i 번째 노드는 parent(i) = i/2, left_child(i) = 2i, right_child(i) = 2i+1의 인덱스)

Full Binary Tree

모든 노드가 0개 혹은 2개의 자식 노드를 가진다.

Perfect Binary Tree

Complete, Full Binary Tree의 특징을 모두 만족한다.
모든 말단 노드는 같은 레벨에 있어야 하고, 마지막 단게에서 노드의 개수가 최대
모든 내부 노드는 2개의 자식 노드를 가짐

BST(Binary Search Tree)

정렬된 이진 트리이다.

  • 현재 노드의 왼쪽 하위 트리에는 현재 노드보다 작은 값을 가지는 노드만 포함
  • 현재 노드의 오른쪽 하위 트리에는 현재 노드보다 큰 값을 가지는 노드만 포함
  • 중복 값 허용x
  • 위의 특징을 이용해 in-order 순회시 정렬된 순서로 값을 가져올 수 있음
  • 트리가 균형상태이면 탐색시간은 O(logN) 불균형시 최대 O(n)

Binary Heap

힙이란 트리 기반 자료구조로 힙 속성(max 힙의 경우 부모 노드는 반드시 자식 노드보다 값이 큼)을 만족
힙 속성으로 인해 우선순위 큐를 구현하는데 적합

이진 힙은 Tree 중에서도 배열에 기반한 Complete Binary Tree이다.

힙 속성으로 인해 삽입이나 삭제시 속성을 유지한다. 시간복잡도는 O(logN)

Red-Black Tree

BST이다. 하지만, BST와 다르게 불균형이 생기지 않게 조건이 있다.
즉 트리를 균형상태로 유지한다
삽입, 삭제, 탐색 모두 시간 복잡도가 O(logN)

조건

  1. 루트 노드는 black
  2. 모든 이파리 노드는 black이고 NIL이다. (NIL: null leaf)
  3. 노드의 색이 red 인 경우 자식은 모드 black
  4. 모든 리프노드에서 루트노드까지 가는 경로에 만나는 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 발생시 계속 반복)

참고자료

  1. https://genius-dev.tistory.com/entry/Kotlin%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Tree%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC-1
  2. https://code-lab1.tistory.com/62
profile
android 를 공부해보아요

0개의 댓글