자료구조 ] Tree

자료구조 ] Tree

출처: 린큐의 공부한걸 기록하자 (https://blog.geusan.com/32)

정의

Node와 edge(간선)을 이용해서, 사이클을 이루지 않도록 구성한 자료구조이다.

특징 / 특이사항

트리 중에 가장 많이 사용하는 이진트리를 기준으로 특이사항을 정리해 본다.

N개의 노드를 가진 이진트리는 (N-1) 개의 간선을 가진다.

출처: https://medium.com/quantum-ant/%ED%8A%B8%EB%A6%AC-tree-cec69cfddb14

높이가 H인 이진트리의 경우, 최소 H개의 노드를 가지며 최대 2^(H-1)개의 노드를 가진다.

N개의 노드를 가지는 이진트리의 높이는 최대 N이거나 최소 log₂(N+1)가 된다.

출처: https://medium.com/quantum-ant/%ED%8A%B8%EB%A6%AC-tree-cec69cfddb14

용어

이름 설명 node 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 edge 정보 포함) edge 노드를 연결하는 선 (link, branch 라고도 부름) root node 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다 size 자신을 포함한 모든 자손 노드의 개수 depth 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 level 각 층에 번호를 매기는 것으로, 루트의 레벨은 0이며 내려갈 때마다 레벨이 증가한다 degree 각 노드가 지닌 가지의 수

활용

이진트리 형태의 구조로 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.

다음은 이진트리와 정렬된 배 열간의 탐색 시간 비교이다.

출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node

종류

트리는 노드와 간선만 가지고 만들수 있는 구조면 다 트리라고 이름 붙일 수 있기에

가장 많이 언급되는 이진트리, 이진탐색트리, 힙 세 가지를 구분해 보겠다.

1) 이진트리

하나의 노드는 자식 노드를 최대 2개 까지만 가질 수 있는 트리

출처: 미래학자(https://futurists.tistory.com/59)

2) 이진탐색트리

하나의 노드는 자식 노드를 최대 2개까지만 가질 수 있는 이진트리이며,

왼쪽 자식 노드는 부모 노드의 수보다 작은 값 을 가지고, 오른쪽 노드는 부모 노드의 수보다 큰 값 을 가진다.

을 가지고, 을 가진다. 만약 중복되는 값을 가지면 중복된 값은 제거된다.

출처: https://lowelllll.github.io/til/2018/11/17/TIL-BST/

이진 탐색 트리는 아래와 같은 모양으로도 구성될 수 있기 때문에

출처: https://lowelllll.github.io/til/2018/11/17/TIL-BST/

깊이를 조정해서 구현하기도 한다.

3) 힙

이진트리 종류 중 완전 이진트리 형태를 가진 트리이며,

부모 노드가 자식 노드들 보다 크면 최대 힙,

최대 힙, 부모 노드가 자식 노드들 보다 작으면 최소 힙이라 한다.

최소 힙이라 한다. 형제 노드 사이에서는 정렬되지 않은 상태라도 상관없다.

완전 이진트리란?

마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며, 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조

출처: 데이터 사이언스 사용 설명서 (https://dsbook.tistory.com/255?category=802592)

from http://jibsun-i.tistory.com/16 by ccl(A) rewrite - 2021-10-14 16:26:39