[자료구조] 트리(Tree)란? (미완)

트리(Tree)

아래의 내용을 정리하여 보았다.

• 트리란 무엇인가?
• 트리의 구성요소 (root node, parent node, child node, leaf node 의 의미)
• 트리의 종류 (이진트리, AVL트리, 레드-블랙트리)
• 트리의 응용
  

트리란 무엇인가?

정의 : 트리란, 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. [출처 : 위키피디아]

계층적인 관계를 설명하는데 유용하게 쓰일 수 있다.

위의 설명보단 아래의 그림을 보는 것이 좀 더 직관적이다.

트리의 구성요소

2, 7, 8, 6, 9, 5.. 위에 보이는 각 동그라미가 노드를 의미한다.

7과 5는 가장 상위에 있는 2의 자식노드(Child Node)

2는 7과 5의 부모노드(Parent Node) 이다.

7과 5는 서로 형제노드(Sibling Node) 이다.

주어진 노드의 상위 노드는 모두 조상노드(Ancestor Node)이다.

주어진 노드의 하위 노드는 모두 후손노드(Descendent Node)이다.

제일 위의 노드 즉 상위 노드가 없는 노드를 루트 노드(Root Node)라고 부른다.

하위 노드가 없는 노드를 단말노드(Leaf Nod)라고 부른다.

단말 노드를 제외한 모든 노드를 내부노드(Internal Node)라고 부른다.

트리의 종류

아래의 이미지는 이진 트리이다. (이진 트리는 각 노드의 자식의 갯수가 최대 2개로 한정되는 트리이다.)

[출처 : 위키피디아]

AVL 트리 : 균형 잡힌 이진 탐색 트리, 자식 노드들의 높이 차가 최대 1이다.

레드-블랙 트리:

트리의 응용

출처

http://blog.naver.com/PostView.nhn?blogId=kzeroz&logNo=50023945325&parentCategoryNo=&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

http://www.ktword.co.kr/abbr_view.php?m_temp1=4726

http://www.assortrock.com/46