트리(Tree)의 구조

트리는 사이클이 없고 노드와 간선(edge)로 이루어진 자료 구조 입니다.

트리가 나오게 된 이유는 배열과 비교해서 [삽입/삭제/탐색]이 O(logN) 이 걸리기 때문에 빨라 사용하게 되었습니다.
(단, 탐색의 경우 편향 트리이면 O(N)의 시간이 걸린다)

• 노드(Node) : 트리의 최소단위로 값과 자식 노드의 주소를 가지고 있다.
• 간선(Edge) : 노드와 노드를 연결해주는 선
• 루트(Root) : 트리의 최상위에 있는 노드. 근노드라고도 한다.
• 단말 노드 : 자식 노드가 없는 노드. 리프 노드, 말단 노드라고도 한다.
• 내부 노드 : 부모와 자식 노드를 가진 노드.
• 트리의 부모 자식 형제 관계 : A의 하위에 B와 C가 연결되어 있을 때 A는 B의 부모노드,  B는 A의 자식노드, B와 C는 형제 노드 라 한다.
• 레벨(Level) : 각 층별로 숫자로 구분한 것. 레벨이 낮을 수록 상위 노드이다.
• 서브 트리 : 트리 내부에 있는 트리
• 차수(Degree) : 자식 노드의 수
• 트리의 차수 : 모든 노드 중 가장 큰 값트리는 사이클이 없고 노드와 간선(edge)로 이루어진 자료 구조 입니다.

트리가 나오게 된 이유는 배열과 비교해서 [삽입/삭제/탐색]이 O(logN) 이 걸리기 때문에 빨라 사용하게 되었습니다.

(단, 탐색의 경우 편향 트리이면 O(N)의 시간이 걸린다)

 

노드(Node) : 트리의 최소단위로 값과 자식 노드의 주소를 가지고 있다.

간선(Edge) : 노드와 노드를 연결해주는 선

루트(Root) : 트리의 최상위에 있는 노드. 근노드라고도 한다.

단말 노드 : 자식 노드가 없는 노드. 리프 노드, 말단 노드라고도 한다.

내부 노드 : 부모와 자식 노드를 가진 노드.

트리의 부모 자식 형제 관계 : A의 하위에 B와 C가 연결되어 있을 때 A는 B의 부모노드, B는 A의 자식노드, B와 C는 형제 노드 라 한다.

레벨(Level) : 각 층별로 숫자로 구분한 것. 레벨이 낮을 수록 상위 노드이다.

서브 트리 : 트리 내부에 있는 트리

차수(Degree) : 자식 노드의 수

트리의 차수 : 모든 노드 중 가장 큰 값