비선형 구조

-비선형 구조-

1. 트리

이번에 배울 트리는 비선형 구조입니다.

비선형 구조는 선형구조와는 다르게 데이터가 계층적으로 구성되어있다.

선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 들어나는데

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. 

그렇다면 트리는 무엇을 표현하기 위한 자료구조인가? 

컴퓨터의 directory 구조가 트리의 대표적인 예가 될 수 있다. 어떠한 프로그램, 사진, 영상 등을 찾을 때 우리는 폴더에서 폴더로 들어가면서 찾곤 한다. 이렇게 계층적인 구조를 갖는 것이 트리라 할 수 있다. 또 다른 예로는 조직도, 족보 등이 있다. 

트리 관련 용어

 

• Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드
• Node : 트리의 구성요소에 해당하는 A,B,C,D,E,F,G,H,I,J와 같은 요소
• Edge : 노드와 노드를 연결하는 연결설
• Terminal Node(Leaf Node) : 밑으로 또 다른 노드가 연결되어 있지 않은 H,I,J,F,G와 같은 노드
• Sub-Tree : 큰 트리에 속하는 작은 트리
• Level : 트리에서 각 층별로 숫자를 매김
• Height : 트리의 최고 레벨

• 이진트리 : "이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의서브트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진트리이어야 한다." 
  
• 포화 이진 트리(Full Binary Tree) : 모든 레벨이 꽉 찬 이진 트리
• 완전 이진 트리(Complete Binart Tree) : 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리

트리는 스택이나 큐와 다르게 비선형구조로 탐색하는 방법이 여러가지가 있다. 위에 구현된 간단한 트리만 보더라도 b4-b2-b1-b3 순으로 탐색할 수 있고, b1-b2-b4-b3 순으로 탐색 할 수도 있다. 이렇게 트리에 있는 모든 노드들을 탐색하는 것을 트리 순회(Traversal)이라 한다.

2. 그래프

그래프는 이후에 나올 많은 알고리즘에서 사용되기 때문에 굉장히 중요하다.

그래프는 트리와 비슷하게 노드와 엣지로 구성되어 있다. 그래프에서는 노드를 버텍스, 엣지를 아크라고 부른다. 사실 그냥 노드랑 엣지로 불러도 상관 없지만, 있어보이려면 버텍스와 아크로 부르도록 한다.

그래프는 버텍스 간에 여러 개의 아크가 존재할 수 있다. 다른 버텍스에서부터 오는 아크의 개수를 In-degree, 다른 버텍스로 가는 아크의 개수를 Out-degree라고 부른다. 또한 방향성을 띄고 있는지에 따라 방향 그래프와 무방향 그래프로 나뉜다.

트리는 사실 그래프의 특수한 형태다. 트리는 하나의 부모 노드에서부터 아래 방향으로 내려오는 그래프다. 즉, 트리를 루트가 있고 In-degree가 1인 방향 그래프라고 말할 수 있다.

그래프를 코드로 표현하는 방법에는 크게 두 가지가 있는데 하나는 이차원 배열을 사용하는 방법과, 다른 하나는 연결 리스트를 사용하는 방법이 있습니다.

이차원 배열을 사용하면 공간은 많이 차지하지만 간단하고, 연결 리스트는 공간은 적게 차지하지만 복잡합니다.