Tree

yshjft·2022년 6월 16일
0

자료구조

목록 보기
4/6

Tree

그래프와 유사하지만 단방향이며 cycle이 존재하지 않는 자료구조이다.

Tree의 구성 요소

  • Node: 트리를 구성하고 있는 각각의 요소
  • edge: Node와 Node를 연결하는 선
  • Root Node: 트리 구조에서 최상위에 있는 노드를 의미
  • Terminal Node(External Node): 하위에 다른 노드가 연결되어 있지 않은 노드
  • Internal Node: 단말 노드를 제외한 모든 노드

순회 방식

  • 전위 순회
    • (부모 - 좌측 - 우측)
    • 0 → 1 → 3 → 7 → 8 → 4 → 9 → 10 → 2 → 5 → 11 → 6
  • 중위 순회
    • (좌측 - 부모 - 우측)
    • 7 → 3 → 8 → 1 → 9 →4 → 10 → 0 → 11 → 5 → 2 → 6
  • 후위 순회
    • (좌축 - 우측 - 부모)
    • 7 → 8 → 3 → 9 → 10 →4 → 1 → 11 → 5 → 6 → 2 → 0

Binary Tree

  • 이진 트리
  • 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다.
    • 서브 트리 또한 이진 트리어야 한다.
    • 공집합도 이진 트리이다.
  • 트리에서 각 층을 level이라고 한다.
    • level 시작은 0이다. (루트 노드의 레벨은 0이다.)
    • 트리에서 최고의 레벨은 height이다.
  • 중복된 값을 허용하지 않는다.

이진트리 종류

  • Perfect Binary Tree
    • 포화 이진 트리
    • 모든 레벨에 노드들이 채워져 있는 트리
  • Complete Binary Tree
    • 완전 이진 트리
    • 왼쪽부터 차근 차근 채워져 있는 트리
  • Full Binary Tree
    • 정 이진 트리
    • 노드의 자식이 0개 아니면 2개 뿐인 트리

BST

  • Binary Search Tree
  • 특정 규칙을 가지고 이진 트리에 데이터를 저장하여 효율적인 탐색을 할 수 있도록 하는 트리다.
    • 부모를 기준으로 우측과 좌측의 값의 비교가 가능하도록 구성한다.
      • 이진 탐색 트리에 저장된 키는 유일하다
      • 부모의 키가 왼쪽 자식 노드의 키보다 크다.
      • 부모의 키가 오른쪽 자식 노드의 키보다 작다.
    • 탐색 연산은 O(log n)
  • 이진 탐색 트리는 편향 트리가 될 수 있다.
    • 저장 순서에 따라 한 쪽으로만 노드가 추가될 수 있다.
    • 이는 성능에 영향을 미쳐 최악의 경우 O(n)의 시간 복잡도를 가질 수 있게 된다.

BST에서 노드 삭제

왼쪽 자식만 있는 노드에 대한 삭제

서브 트리의 가장 오른쪽 노드를 삭제하려는 노드의 위치로 옮겨주어야 한다.

오른쪽 자식만 있는 노드에 대한 삭제

서브트리의 가장 왼쪽 노드를 삭제하려는 노드의 위치로 옮겨주어야 한다.

왼쪽, 오른쪽 모두 자식이 있는 노드에 대한 삭제

대체 노드를 왼쪽 서브 트리의 가장 오른쪽 노드로 정하거나, 오른쪽 서브 트리의 가장 왼쪽 노드로 정하면 된다.

AVL 트리

이진 탐색 트리 불균형 문제를 해결해주는 트리이다.

삽입

  • 트리의 높이차가 1보다 크면 회전을 통해 불균형을 해결한다.
  • 균현 인수를 사용해야 한다.
    • 균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
  • 회전
    • LL 회전
    • RR 회전
    • LR 회전
      • RR 회전 → LL 회전
    • RL 회전
      • LL 회전 → RR 회전

AVL 트리 삽입 참고1
AVL 트리 삽입 참고2
AVL 트리 삽입 참고3
AVL 트리 삽입 참고4
AVL 트리 삽입 참고5

삭제

  • 이진 탐색 트리 삭제 과정 + 회전
    기본적으로 이진 탐색 트리 삭제 과정과 동일하다
    다만 높이차이가 1보다 크게 되면 회전을 진행한다.
    AVL 트리 삭제 참고

Red Black Tree

  • BST 기반
    • RBT는 Complete Binary Tree이다.
  • Search, insert, Delete에 O(logn)에 가능하도록 한다.
  • Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않다. (balanced 상태)

RBT 특성

  • 각 노드는 빨강색 또는 검정색이라는 색깔만 가진다.
  • 루트 노드의 색깔은 검정
  • 모든 종말(nil) 노드들은 검정색이다
    • nil 노드란?
      • 존재하지 않음을 의미하는 노드
      • 자녀가 없을 때에 자녀 노드를 nil 노드로 표기
      • 일반적인 노드와 동등하게 취급 → leaf node = nil node
  • 빨강 노드의 자식은 검정이다.
  • 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.
    • 자기 자신은 카운트에서 제외한다.
    • 노드 x의 black height
      • 특정 노드에서부터 자손인 단말 노드까지의 단순 경로에 같은 수의 black node들이 있다.
      • RB 트리가 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

삽입

  • 부모 노드가 레드인데 부모 노드의 형제가 없거나 블랙 노드인 경우 → 회전(Restructuring)
    • (1) 새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬
    • (2) 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다
    • (3) 새로 부모가 된 노드를 검은색으로 만들고 자식들을 빨간색으로 만든다.
  • 부모 노드가 레드인데 부모 노드의 형제가 레드 노드인 경우 → 색상 변환(Recoloring)
    • (1) 새로운 노드의 부모 노드와 부모의 형제 노드를 검은색으로 조상 노드를 빨간색으로 변경한다.
      • (1-1) 조상이 루트 노드라면 검은색으로 바꾼다.
      • (1-2) 조상을 빨간색으로 변경하였을 때 또 Red Black Tree의 규칙을 위배한다면 또 다시 회전 또는 색상 변환을 진행한다.(문제가 발생하지 않을 때까지 반복)

Red Black Tree 삽입 참고1
Red Black Tree 삽입 참고2

삭제

  • 이진 탐색 트리 + 추가적인 단계
    • 기본적으로 이진 탐색 트리 삭제 과정을 따른다.
    • 빨간색 노드는 그냥 삭제하면 된다(추가적인 작업이 필요 없다)
    • 삭제된 노드가 검은색인 경우, 그 자리를 대체하는 노드를 검은색으로 칠한다.
      • 대체하는 노드가 빨간색이라면 문제가 되지 않는다.
      • 대체하는 노드가 검은색이라면 이중흑색 노드가 발생하게 된다.
      • 이중 흑색 노드 해결 참고

AVL 트리 VS Red Black 트리

  • AVL 트리는 엄격하게 밸런스를 유지하므로 탐색에 유리
  • Red Black 트리는 탐색에는 불리하지만 삽입, 삭제에 유리
  • 현실에서는 삽입과 삭제가 빈번히 일어나므로 Red Black 트리를 AVL 트리보다 선호

AVL 트리 VS Red Black 트리 참고

profile
꾸준히 나아가자 🐢

0개의 댓글