트리 자료구조(Tree Data Structure)

Tree

트리구조 (Tree)

트리구조란 그래프의 일종으로 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프, 즉 순환 되지 않는 그래프를 트리라고 부른다. 또한 여러 노드가 한 노드를 가르킬 수 없다.

• 그래프

 

• 그래프

 

• 트리

 

구성요소

트리는 정점과 간선으로 이루어져 있다.

• 정점 / Node / Vertex
• 간선 / Link / Edge
• 차수 : 자식노드의 갯수 ( 트리의 차수 : 최대 차수)
• 레벨 (Level) : 루트 노드가 레벨 0 에 해당되고 자식노드로 내려갈수록 레벨을 1씩 증가한다.
• 높이 (Height)/ 깊이 (Depth) : 트리의 최대 레벨
• 뿌리(Root) 노드 : 최상위 노드
• 자식(Child) 노드 : 어떤 노드의 하위 노드
• 부모(Parent) 노드 : 어떤 노드의 상위 노드
• 잎 (Leaf) 노드 / 단말 노드/ 터미널 노드: 자식 노드가 존재 하지 않는 노드

종류

• 2진트리(Binary Tree)

• 균형트리 / 불균형 트리
• 사향 이진 트리
• 완전 이진 트리
• 포화 이진 트리
• AVL 트리
• 레드 블랙 트리
• B - 트리 (B Tree)
• B + 트리 (B+Tree)

참조

08-자료구조: 트리(Tree) - 일반 트리와 트리의 정의,일반트리의 구현

자료구조(독학학위제 독학사 컴퓨터과학과 2단계)