트리에 대하여
/*
서론.
그래프를 먼저 공부하고 트리를 정리했어야했는데 조금 아쉽다.
트리는 그래프의 한 종류이기 때문이다.
트리로 검색했을 때 중복되어 나오는 결과들은 다음과 같다.
- 자료들 간에 계층관계를 가진 계층형 자료구조
- 순환을 갖지 않는 연결그래프
- 비선형 자료구조
- 나무를 뒤집어 놓은 모양새여서 트리라고 부른다
- 이진 트리
- 이진 탐색 트리
- DFS순회/BFS순회
- in-order, pre-order, post-order (전위, 중위, 후위) 순회
- 레드-블랙 트리, AVL
- 기타 그 밖의 용어들(레벨, 차수, 단말 노드, 부모, 형제, 자손 등...)
하나하나 찾다보면 아예 모르는 것들은 아닌데(들어본 것들인데), 도대체 트리를 왜 써먹어야 하는지 잘 모르고 있었던 것 같다.
특히, 자료 구조시간에 지겹게 나왔던 순회.
재귀로 간단히 구현할 수 있다는 것을 알고있으나, 왜 굳이 순회를 해야하는지 생각해 본 적 없어 정리해보고자 한다.
아직 완벽히 정리(이해)는 되지 않아서 좀 부족한 것 같지만....
*/
1. 트리는 무엇이고 왜 써야하는가?
트리와 그래프는 비선형 데이터 구조이며, 트리는 계층형 데이터 구조이다.
선형 데이터 구조로는 계층형 구조를 나타낼 수 없기 때문에, 트리라는 자료구조를 활용한다.
선형 데이터 구조는 데이터를 구성하는 원소들이 순차적으로 나열된 데이터 구조이다. 리스트(선형, 연결) , 스택, 큐, 데크 같은 것들이다.
계층으로 나타낼 수 있는 예로, 가족 관계도를 생각해보면..
가족 관계를 선형으로 나타내기는 굉장히 어렵다. 또한, 선형데이터로 나타낸 가족 관계도에서 내 조카를 찾아보라고 하면 굉장히 찾기 어려울 테다.
트리는 주로 탐색을 하기 위해 사용된다. 폴더 구조, DBMS, 검색 엔진 등에서 활용이 된다.
2. 트리의 용어에 대해서
용어는 생략하고 싶다. 정리하기 지겹지만.. 자주 헷갈리는 것만 적어보자면..
- 차수(degree)
- 차수란 노드에서 뻗은 가지의 수 중, 가장 많이 뻗은 가지의 수를 트리의 차수라고 말한다.
- 높이(height)
- 루트 노드부터 시작해서 맨 끝에 있는 리프 노드까지의 깊이
- 깊이
- 레벨
그림이 없어 설명하기 힘들다. 그치만, 그림 그리기가 너무나도 귀찮아서 다음 용어들은 생략..!
- 루트노드
- 부모노드
- 자식노드
- 단말노드(리프노드)
- 형제노드
3. 이진트리
트리구조를 저장하는 방법은 여러가지가 있다.
흔한 방법으로는 1. n링크 방법 2. 왼쪽 자식, 오른쪽 형제 노드(left-child, right-sibling) 방법 등이 있다.
1. n링크 방법은, 노드에 자식의 개수 만큼 n개의 링크를 두고, 링크는 트리가 저장된 곳을 링크하는 방법이다.
한번에 찾을 수 있기에 시간 복잡도가 O(1)인 장점이 있지만 데이터안에 빈공간이 많게 된다. 모든 데이터가 차수의 링크를 가져야하기 때문이다.
또한, 노드의 수가 늘어나게 되면 적용하기 어렵다. 실제적으로는 노드의 개수가 정해질 때보다 가변적일 때가 많은데, 그렇게 되면 동적배열을 사용해야하고.. 그러면 구현하기가 어려워져서
잘 사용하지 않는다. 그래서
2. 왼쪽자식, 오른쪽 형제 노드 방법이 있다. 이건 포인터로 왼쪽에는 자식을, 오른쪽에는 형제를 표시한다.
왼쪽자식, 오른쪽 형제 노드를 이용하면 이진 트리로 표현할 수 있는 장점이 있다.(조금만 기울여 보면 이진트리가 된다.)
시간 복잡도는 n링크 방법보다 더 걸리지만, 구현이 매우 쉽다. 단점은 n링크처럼 원하는 위치의 노드에 한번에 방문하기 어렵다.
그럼 이진트리는 왜 필요한걸까? 이진 트리가 중요한 이유는 구현이 매우 간단하기 때문이라고한다. N링크법은 활용하기도 힘들고, 여러 변형 트리 기법을 적용하기 어려운데, 이진 트리는 자식의 갯수가 무조건 두개로 고정되어 있기 때문에 활용이 편리하다고 한다.
이진트리의 모양새에 따라 이진트리는 또 여러 종류로 나뉘는데 스큐이진트리(편향이진트리), 포화 이진 트리, 완전 이진트리 등이 있다.
그림을 보면 간단한데, 스큐 이진트리는 한쪽으로 편향된 모양새 포화이진트리는 꽉 찬거고 완전이트리는 위에서 부터 왼쪽에서부터 차례대로 차곡차곡 쌓여잇는 것 이다.
4. 그놈의 순회 왜해야하는 걸까?
트리를 정리해놓은 자료를 살펴보면, 보통 이런 흐름이다.
트리는 무엇인지? 트리의 용어 정리, 이진트리, 이진트리의 순회.
순회가 필요한 경우는 주로 연결리스트로 트리가 구현되어있을 경우이다.
트리는 선형구조가 아닌 비선형 구조이기 떄문에 모든 노드들을 거쳐가기 위한 방법이 필요한 것이다.
예를 들자면, 데이터를 삭제해야하는 경우 서브트리를 삭제하기 위해서는 모든 노드를 거쳐야지만 삭제할 수 있기때문에 순회가 필요하다.
일단, 순회방법에는 깊이우선탐색(DFS) 와 너비우선탐색(BFS)가 있고,
자료구조 시간에 지겹게 본 pre-order, in-order, post-order 순회는 깊이우선탐색기법(DFS)이다.
왜 순서를 나누는지 잘 모르겠어서 블로그를 찾다가 다음 포스팅을 발견했다. http://www.geeksforgeeks.org/618/
- In case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder itraversal s reversed, can be used.
- Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on of an expression tree. Please see http://en.wikipedia.org/wiki/Polish_notation to know why prefix expressions are useful.
요약하자면
- inorder(중위순회)는 이진탐색트리에서 오름차순으로 노드를 얻는데 사용할 수 있다.
- preorder(전위순회)는 트리의 복사본을 생성하기 위해 사용하거나, 수식트리에서 prefix 수식을 얻는데 사용할 수 도 있다.
- postorder(후위순회)는 트리의 삭제에 이용되며 수식트리에서 postfix 수식을 얻는데 사용된다.
위의 세가지는 재귀를 통해 간단하게 구현할 수 있다.
다음과 같은 이진트리가 있다고 가정하면
inorder같은 경우 노드의 방문 순서는 LVR로 6-2-8-1-5
preorder의 노드의 방문 순서는 VLR로 1-2-6-8-5
postorder의 노드의 방문 순서는 LRV로 6-8-2-5-1 이다.
너비탐색(BFS)의 경우에는 큐를 이용하여 구현할 수 있다. 너비 탐색을 이용하면 노드의 방문순서는 1-2-5-6-8이 된다.
각 레벨의 노드를 큐에 추가하고 각 자식의 노드들을 모두 큐에 넣으면서 하나씩 반환하면 된다.
5. 이진 탐색 트리
이진 탐색트리는 이진 탐색이 적용된 이진트리이다. 이진탐색트리의 특징은 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 커야한다는 것이다. 다음은 이진 탐색 트리의 예이다.
이진탐색트리에서는 탐색, 삽입, 삭제 세가지 연산을 할 수 있다.
삭제의 경우만 탐색이나 삽입보다 복잡한 편이다.
삭제하려는 노드가 단말 노드인 경우는 링크를 null로 만들어 주면 되고
삭제하려는 노드가 하나의 자식노드를 가지고 있을때에는 자식 노드가 그 자리를 대체한다.
삭제하려는 노드가 두개의 자식 노드를 가지고 있을 떄에는 왼쪽 서브트리에서 가장 큰 값으로 대체하거나,
오른쪽 서브트리에서 가장 작은 값의 노드로 대체한다.
6. 트리의 균형잡기
왜 레드블랙 트리, B-tree, AVL 트리 같은 것들이 필요할까?
이진탐색트리에 값을 삽입하다보면 스큐이진트리가 될때가 있다...
다음 두 그림은 모두 이진탐색트리의 규칙을 어긋나지 않는, 이진 탐색 트리이다.
그러나, 1이라는 노드를 탐색한다고 가정하면, 두 트리의 탐색 속도는 오른쪽이 빠르다.
트리의 균형이 맞지 않으면, 왼쪽 처럼 그냥 일반 연결리스트에서 찾는 것과 다름없게 된다.
레드블랙트리, 비트리, AVL트리는 이러한 문제를 해결하기 위한 방법으로 고안된 발전된 고급 이진트리들이라고 생각하고 있다.
비트리(B-tree)는 자식을 두개만 가질 수 있는 이진 트리를 확장하여 더 많은 자식을 가질 수 있으며 자동으로 균형을 맞춘다.
레드블랙트리는 이진 트리에 색상이라는 속성을 노드에 추가하여 자동으로 균형을 잡도록 만드는 트리이다.
AVL트리도 LR회전 LL회전 RR회전 RL회전 등을 통해서 자동으로 트리의 균형을 맞추기 위해 만들어진 알고리즘이다.
