티스토리 뷰
1. 개요
[그림 1] 트리 (Tree)
"트리 (Tree)" 자료구조란 나무를 뒤집은 모습으로 계층구조를 표현하기에 적합한 자료구조이다. 맨 위의 노드가 "루트노드 (Root Node)" 라고 하며 이 노드 아래에 있는 노드들은 다시 트리 구조가 된다. 이런 구조를 "서브 트리 (Sub Tree)"라고 한다. 또한, 임의의 노드의 조상과 자손을 지칭 할 수 있는데, 임의의 노드 바로 위에 있는 노드를 "부모 노드 (Parent Node)" 라고 하고 그 바로 아래 노드들을 "자식 노드 (Children Node)"라 한다.
[그림 2] 이진 트리 (Binary Tree)
이런 트리구조에서 파생된 자료구조를 "이진트리 (Binary Tree)"라고 부르는데, 이진트리는 모든 노드들의 자식 노드가 두 개 이하인 트리를 의미한다. 이런 이진트리에서는 서브트리가 2개 이하기 때문에 서브트리는 왼쪽과 오른쪽으로 구분된다.
이진트리를 구현하는 방법으로 < 1) 배열을 이용하여 구현 , 2) 링크드리스트를 이용하여 구현 > 두 가지가 있다.
1. 배열로 구현
배열로 구현하게 될 경우, 연결리스트로 구현하는것보다 더 복잡하고 생각해야할것이 많다. 하지만 그렇다고해서 아예 안쓰이지는 않고, 힙 트리의 경우 배열로 구현하게 되는 경우가 많다.
배열로 구현하는 방법은 다음과 같다.
우선, 0번방은 비워놓고 루트노드를 1번방으로 시작하여 내려간다. 임의의 노드를 탐색하고 싶은 경우 해당 배열 방 번호를 입력하면 된다.
[그림 2]처럼 데이터 4의 노드에서 오른쪽 자식노드(5)를 가고자 하면 => (2 x i ) + 1 을 해주면 데이터 5의 방 번호가 나온다.
정리하면,
====================================
노드 i의 부모 노드 = i/2
노드 i의 왼쪽 자식 노드 = 2 x i
노드 i의 오른쪽 자식 노드 = ( 2 x i ) + 1
루트 노드 = 1
====================================
이다.
배열로 구현하는 방법의 장점은 시간복잡도를 줄일수 있다는 점이 있지만, 편향 이진트리의 경우 사용하지 않는 배열 원소에 대한 메모리 낭비가 발생하고, 삽입/삭제에 대한 배열의 크기 변경이 어렵다는 점이 있다.
2. 링크드리스트로 구현 ( Use to Linked List )
[그림 3] 링크드 리스트를 이용한 이진트리
링크드 리스트로 구현하는 방법은 배열로 구현하는것보다 더 쉽고 접근에 있어서 더 직관적이다. 하지만, 배열 구조에서만 가능한 임의 노드로의 접근이 불편(?)하다. 데이터가 커질수록 전위,후위 순회 하는 속도가 더 느려지므로 탐색시간에 있어서 링크드 리스트가 배열 구조보다 시간이 더 오래걸린다는 점이 있다.
1. 구조체 선언
[그림 3]처럼 노드의 구조체를 코드처럼 데이터방, 노드포인터 왼쪽,오른쪽 변수를 가지는 구조체를 선언하고, 트리관리 구조체를 하나 선언한다. 트리관리 구조체를 선언하는 이유는 노드의 삽입 및 삭제 시 노드의 갯수를 저장해주는 공간의 필요와 삭제 시에 루트노드가 바뀌는 경우가 있으므로 루트노드를 지정해주기 위해 선언한다.
2. 트리 초기화
3. 이진 탐색 트리 ( Binary Search Tree )
[그림 4] 이진 탐색트리 조건을 갖춘 트리
[그림 4]의 트리구조를 보면 조건이 하나 있다. 부모노드를 기준으로 왼쪽자식은 부모노드의 값보다 더 작은 값, 오른쪽 자식은 부모노드의 값보다 더 큰 값을 가지고 있다. 그 아래 서브트리도 마찬가지로 왼쪽이 작은 값 오른쪽이 큰 값을 가지는 형태로 이루어져있다.
예를 들어, [그림 4]의 "21" 데이터를 찾는다고 하면, 루트노드 10을 기준으로 하여 대/소 비교를 하며 트리 아래로 내려간다. 첫번째로 현재 노드가 찾을 값과 같은지 비교하고 같지 않으면 10과 21을 비교한다. 21이 더 크므로 오른쪽 자식으로 내려가고 그 다음 18과 비교하여 21이 더 크므로 오른쪽으로 간다. 이런 조건을 가지는 트리를 "이진 탐색 트리 (Binary Search Tree)" 라고 부른다.
다음은 그 과정을 코드로 구현한 것이다.
1. 노드 탐색
[그림 4] 이진 탐색트리 조건을 갖춘 트리
예를들어, 10값을 가진 노드를 삭제한다고 가정하자. 10노드를 삭제하게 되면 10의 자리에는 어떤 값이 들어가야 할까? 이진탐색트리의 조건에 맞춰서 6보다는 크고 18보다는 작아야 한다. 그 값은 두 가지로 구할수 있다. 하나는 삭제하고자 하는 노드의 왼쪽노드 부분에서 최대값을 찾는 것이고 하나는 삭제하고자 하는 노드의 오른쪽노드 부분에서 최솟값을 찾는것이다. 전자는 "8" 이 될 것이고 후자의 경우 "15" 가 될 것이다.
4. 노드 순회 ( Traversal )
[그림 5] 순회 과정
전위순회는 루트노드를 먼저 방문하고 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문하는 방법이다. 왼쪽서브트리를 모두 방문하고 왼쪽방이 더 이상 없으면 그 이전 노드로 돌아가 오른쪽 노드를 탐색하고 왼쪽,,,또 오른쪽..이런 순으로 방문한다.
'프로그래밍 > 자료구조' 카테고리의 다른 글
5. 그래프 (Graph) - 인접리스트법 (0) | 2016.08.23 |
---|---|
5. 그래프 (Graph) - 인접행렬법 (0) | 2016.08.23 |
3. 원형 큐 (Circular Queue) (0) | 2016.08.22 |
2. 스택 (Stack) (0) | 2016.08.22 |
1. 링크드 리스트 (Linked List) (0) | 2016.08.22 |