Tree

Tree + (heap)

 

 

 

트리는 매우 중요한 자료구조 중 하나이다.

연결리스트는 노드들이 한 줄로 연결된 선형적인 자료구조인 반면

트리는 부모 - 자식 관계를 계층적으로 표현한 보다 일반적인 자료구조이다.

 

추상적으로 표현하면 연결 리스트처럼 데이터를 저장하고 있는 노드와 노드를 연결하는 에지(또는 링크)로 구성된다.

연결 리스트와 차이점은 에지가 부모 - 자식 관계를 표현한다는 점에서 차이가 있다.

 

트리 용어

 

부모노드 / 자식노드 : 부모노드는 자식 노드를 위에 있는 노드를 말한다.

자식 노드는 1이상의 레벨을 가지는 노드로 부모노드 밑에 있는 노드이다.

 

조상노드 / 자손노드 : 트리 노드간의 레벨간의 관계가 2이상 차이나는 노드를 말한다.

보다 아래면 자손노드 보다 위면 조상노드라고 한다.

 

루트노드 : 모든 노드의 조상 노드를 말한다. 

가장 최상위 계층의 노드로 0단계 노드를 말한다.

 

리프 노드 : 자식이 없는 노드를 말한다. 

leaf에서 따온 것으로 잎사귀같이 더 이상 뻗어나가는 노드가 없는 것을 뜻한다.

 

레벨 노드 : 루트 노드의 레벨 0를 시작으로 한 세데씩 내려가면서 1씩 증가한다.

 

깊이 (depth) : 루트에서 다른 노드를 연결하는 에지 개수 (노드 5의 깊이 = 4)

 

경로 (path) : 두 노드 사이를 연결하는 에지의 시퀀스를 말한다.

 

높이 (height) : 노드의 높이는 자식 노드까지의 가장 큰 깊이를 말한다.

 

트리 높이 : 루트 노드의 높이가 트리 높이와 같다.

 

분지수(degree) : 노드의 분지수는 자신의 자식 수이며,

트리의 분지수는 가장 큰 분지수로 결정된다.

 

부트리 (subtree) : 어떤 노드와 그 노드의 자손노드들로 구성된 부분 트리

 

 

이진 트리(Binary tree) 정의와 표현법

 

이진트리 :

모든 노드의 자식이 2개를 넘지 않는 트리

실제 자료구조에서 사용되는 트리는 이진트리가 대부분이다..

 

힙 :

특별한 성질을 갖고 있는 이진트리 중 하나로,

최대 값 ( 또는 최소 값)을 빠르게 찾을 수 있는 이진트리 자료구조