Tree구조

Tree구조

naver

트리는 2차원적 비 선형구조이다. 

나무의 모양을 거꾸로 뒤집어 놓은 모양이다. 

뿌리가 가장 위에 있으며 가지(link)들은 밑으로 벌어지며 향한다.

트리구조에서 쓰는 용어

노드 :  어떤 정보를 담고 있다

링크 :  노드간의 연결을 나타냄

경로 : 나무 내에서 링크에 의해 연결된 일년의 노드의 집합

루트(root) : 나무의 제일 위에 있는 있는 노드, 뿌리노드라고 하며 이 뿌리 노드로부터 다른 노드에 이르는 경로는 오직 하나 밖에 존재하지 않는다. ex 위 그림에서는 0노드가 루트(뿌리)노드

부모자식관계  :  노드 1(부모)과 3,4(1노드의 자식)은 부모 자식관계이다.

조부모노드 : 두 단계 위에있는 노드를 가리킬때 ex 노드1은 노드7의 조부모

레벨 : 뿌리 노드로부터 현재 노드까지 의 경로를 거치는 동안의 노드 수를 말한다. 즉 뿌리노드로부터 얼마나 떨어져 있는가 ex 밑에서 부터 4레벨(7,8,9,10,11,12,13,14),3레벨(3,4,5,6),2레벨(1,2),1레벨(0) 올라감

형제관계 :같은 레벨에 있는 노드들은 형제 관계이다. ex (1, 2)노드들은 형제관계 (3 , 4 , 5 , 6 )노드들은 형제관계

종료 노드 : 자식이 없는 노드 ex (7,8,9,10,11,12,13,14)노드

트리의 성질

-나무 구조에서 한 노드에서 다른 노드로 가는 경로는 유일하다.

(나무를 타는 경로가 중복되지않고, 되돌아감이 없다면)

나무구조의 임의의 두 노드는 최소 공통 선조(두 노드가 갖는 가장까운 부모 노드)를 갖는다. 

-N개의 노드를 갖는 나무는 N-1개의 링크를 가진다.

트리구조는 뿌리 노드를 제외하고 모든 노드가 자신의 선조를 향해 하나의 링크를 갖는다.

그래서 N개의 노드를 가진 나무는 N-1개의 링크를 가진다

-꽉 찬 이진트리는 레벨이 d라고 할때 노드의 수는 N이 다음과 같은 조건을 만족한다.

학습참고 : C로배우는 알고리즘_이재규