[Today I Learned] 11월 3주차 day1

트리

뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료구조이다.

트리용어

Node : 트리에서 데이터를 저장하는 기본 요소
Root Node : 트리 맨 위에 있는 노드
Level : 최상위 노드를 level0 으로 하였을때, 하위 branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진트리

각 노드가 최대 두개의 자식을 가지는 트리이다.
이진트리의 높이는 최대 O(log(N))이다.

	  o      Level 0 
    o o o    Level 1
   o  o  o   Level 2 # 이진 트리(X)

      o      Level 0 
   	o   o    Level 1
   o o o     Level 2 # 이진 트리(O)

완전이진트리

노드를 삽입할 때 최하단 왼쪽노드부터 차례대로 삽입된 트리이다.

	  o      Level 0
    o   o    Level 1
     o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

      o      Level 0
    o   o    Level 1
   o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

그래프

연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조이다.

노드(Node) : 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.
간선(Edge) : 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점)

           로제 - 사나
             ⎜       
      제니 - 르탄

르탄이는 연결 관계를 가진 데이터, 노드입니다!
르탄과 제니는 간선으로 연결되어 있습니다.
르탄과 로제는 인접 노드 입니다!