Tree

HyeBin, Park·2022년 6월 10일
0

Tree

  • 비선형 자료구조
  • 계층적 관계를 표현한다.
  • 무방향 그래프 구조
  • 노드가 n개인 트리는 항상 n-1 개의 간선을 가진다.

Tree 구성

  • Node : 트리를 구성하고 있는 각각의 요소
  • Edge : 노드와 노드를 연결하는 선
  • Root Node : 트리 구조에서 최상위에 있는 노드, 부모 노드가 없다.
  • External Node (Leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 노드
  • Internal Node (Branch Node) : 자식 노드를 하나 이상 가진 노드

Tree 용어

  • Depth : 루트에서 어떤 노드까지의 간선 수, 루트의 Depth는 0
  • level : 각 층별로 숫자를 매기는 것 , 루트의 레벨은 0
  • Height : 루트 노드에서 리프 노드까지 가장 긴 경로의 간선 수 (level의 최댓값)
  • Degree : 노드의 자식 수
  • Path : 한 노드에서 다른 노드까지 노드 경로

Tree 구조

이진 트리(Binary Tree)

  • 각 노드가 최대 두 개의 자식을 갖는 트리
  • 루트 노드를 중심으로 두 개의 서브트리로 나뉘어 진다. (서브트리도 이진 트리)

이진 트리 순회

  • 중위 순회 : 왼쪽 가지 -> 노드 -> 오른쪽 가지
    => 4,2,5,1,3
  • 전위 순회 : 노드 -> 왼쪽 가지 -> 오른쪽 가지
    => 1,2,4,5,3
  • 후위 순회 : 왼쪽 가지 -> 오른쪽 가지 -> 노드
    => 4,5,2,3,1

편향 이진 트리

  • 모든 노드가 부모의 왼쪽에 편향되어 있거나 오른쪽에 편향되어있다.

전 이진 트리

  • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

완전 이진 트리

  • 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리
  • 마지막 레벨이 꽉 차 있지 않아도 되지만 왼쪽에서 오른쪽으로 채워져야 한다.

포화 이진 트리

  • 모든 내부 노드가 두 개의 자식을 가지고 모든 Leaf Node가 동일한 깊이가 갖는다.

이진 탐색 트리 (Binary Search Tree)

  • 이진 트리의 일종
  • 탐색 연산은 O(log n) 의 시간 복잡도를 가진다.

데이터 저장 규칙

  • 이진 탐색 트리의 노드에 저장된 키는 유일하다.
  • 부모의 키가 왼쪽 자식 노드의 키보다 크다.
  • 부모의 키가 오른쪽 자식 노드의 키보다 작다.
  • 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

참조

0개의 댓글