| sitelink1 | |
|---|---|
| sitelink2 | |
| sitelink3 | |
| sitelink4 | |
| sitelink5 | |
| extra_vars6 |
http://blog.naver.com/simtwolove?Redirect=Log&logNo=30022013436
자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
Part7 트리 - 트리의 기본. 용어 및 사용하는 때.
--------------------------------------
오랜만에 글 올리네요..
오늘 배워 볼 트리는 정말 어려운 자료구조 중 하나입니다.
자 그럼 공부해 봅시다~
선린 인터넷 고등학교 20420 전호근.
--------------------------------------
이 전에 배운 동적배열, 연결리스트, 스택, 큐는 모두 선형적인 구조를 가지는데 비해,
트리는 비선형 자료구조( Non-Linear ) 라고 한다.
이 전에 배운 자료구조들은 1차원의 선형구조를 가지는 데 비해,
트리는 2차원이다.
그림과 같이 2차원의 구조라는걸 알 수 있다.
트리는 입체적인 구조 때문에, 이전에 배운 자료구조들보다 구현과 사용이 어렵다.
또, 스택이나 연결 리스트처럼 구현 방법이 정형화되어 있지 않고 적용하는 알고리즘에 따라 천차 만별로 모양이 달라져 응용력을 필요로 하기도 한다.
하지만, 2차적인만큼, 자료의 입출력 및 검색이 상당히 빠르고,
용량이 커지더라도 속도에 아주 큰 영향은 받지 않는 장점이 트리를 사용케 하는 큰 장점이다.
아래 그림을 보자.
와 같이 검색이 빠르다. (이진검색과 비슷한 이치이다.)
그 외에도 어느 정도 규모가 있고 복잡한 데이터를 다룰 때는 주로 트리가 사용되는데
토너먼저 대진표 등과 같이 계층적인 자료들을 다룰 때도 트리가 가장 어울린다.
트리는 말 그대로 나무 이므로, 트리를 구성하는 요소들 및 용어들은 대부분
나무의 각 부분들의 용어를 따온 경우가 많으므로 이해하긴 쉬울 것이다.
단, 진짜 나무는 뿌리가 아래에 있지만, 프로그래밍의 트리구조는 뿌리가 위에있다는 점
(나무를 거꾸로 뒤집은 상태)의 차이점은 있다.
위 그림을 보다시피 동그라미는 노드라고 하는데, 연결리스트와 같다.
노드는 노드를 연결하는 링크(Link)를 가진다.
단, 트리에선 노드라는 용어대신 버텍스(vertex) , 링크라는 용어대신 엣지(edge)라는 용어를 사용하기도 한다.
아래 그림을 보고 더 많은 용어를 공부해 보자.
1. 트리의 기본이 되는 최상층의 노드를 루트 (뿌리) 라고 한다.
모든 트리는 단 하나의 유일한 루트를 가지며, 아래로 무수한 노드를 가지게 된다.
2. 최상위 노드부터 1 , 2, 3, 4 단계로 나뉘는데, 이것을 레벨이라고 부른다.
최상위 즉, 루트는 1레벨. 그 아래 B, C 는 2레벨, 그 아래 3, 그 아래를 4레벨이라 부른다.
C 언어는 모든 숫자를 0부터 시작하지만 트리의 레벨은 1부터 시작(One Base)한다 또, 최고 레벨인 4를 이 트리의 높이라고한다. 즉 이 트리의 높이는 4 이다.
3. 트리를 구성하는 노드 중, 아래쪽의 노드를 자식이라고 하며 위쪽의 노드를 부모라고 한다.
위 그림에서 B, C는 A의 자식이며 D, E, F의 부모는 B이다.
같은 부모를 가진 노드들을 형제라고 하는데 G, H는 공동의 부모 C에 소속되어 있으므로 형제 관계이다.
직속 관계가 아니더라도 아래쪽에 있으면 후손이며 위쪽에 있으면 선조라고 한다.
4. 경로(Path)란 특정 노드에서 다른 노드로 가는 길이다.
어떤 하나의 노드에서 다른 노드로 가는 길은 단 하나뿐이다.
왜냐하면, 두 노드의 공동의 선조까지 올라간 후 다시 아래로 내려가야 하기 때문이다.
I에서 K로 가는 경로는 I-D-B-F-K 단 하나밖에 없다.
5. 차수(Degree)는 자식 노드의 개수인데 B의 차수는 3, C의 차수는 2, M의 차수는 0이다.
차수가 0인 노드, 즉, 자식이 하나도 없는 노드를 잎(Leaf) 노드 또는 외부(External) 노드라고 하며
자식이 있는 노드를 내부(Internal) 노드라고 한다.
6.
순서트리(Ordered Tree)와 비순서 트리(Oriented Tree).
위 그림과 같은 두개의 트리에서 모두 A 밑에 B, C를 자식으로 가지는데,
순서트리(Ordered Tree)라면 이 둘은 다른것이고, 비순서 트리(Oriented Tree)라면 이 둘은 같은 것이다.
순서트리란, 순서가 있는 트리, 비순서 트리란 순서가 의미가 없는 트리를 말한다.
7. 순회 : Order.
순회 방법 -
- 1. 전위순회 ( PreOrder )
- 2. 중위순회 ( InOrder )
- 3. 후위순회 ( PostOrder )
- 4. 레벨순회 ( levelOrder )
순회는 다음 강의에서 알아보자.
마지막으로, 트리를 구성하는 작은 트리를 서브 트리(Sub Tree)라고 하며,
트리가 여러개 모인것은 포레스트(forest)라고 하는데, 나무가 모여 숲은 이루는 것과 같은 이치이다.
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
Part7 트리 - 트리의 기본. 용어 및 사용하는 때.
--------------------------------------
오랜만에 글 올리네요..
오늘 배워 볼 트리는 정말 어려운 자료구조 중 하나입니다.
자 그럼 공부해 봅시다~
선린 인터넷 고등학교 20420 전호근.
--------------------------------------
이 전에 배운 동적배열, 연결리스트, 스택, 큐는 모두 선형적인 구조를 가지는데 비해,
트리는 비선형 자료구조( Non-Linear ) 라고 한다.
이 전에 배운 자료구조들은 1차원의 선형구조를 가지는 데 비해,
트리는 2차원이다.
그림과 같이 2차원의 구조라는걸 알 수 있다.
트리는 입체적인 구조 때문에, 이전에 배운 자료구조들보다 구현과 사용이 어렵다.
또, 스택이나 연결 리스트처럼 구현 방법이 정형화되어 있지 않고 적용하는 알고리즘에 따라 천차 만별로 모양이 달라져 응용력을 필요로 하기도 한다.
하지만, 2차적인만큼, 자료의 입출력 및 검색이 상당히 빠르고,
용량이 커지더라도 속도에 아주 큰 영향은 받지 않는 장점이 트리를 사용케 하는 큰 장점이다.
아래 그림을 보자.
와 같이 검색이 빠르다. (이진검색과 비슷한 이치이다.)
그 외에도 어느 정도 규모가 있고 복잡한 데이터를 다룰 때는 주로 트리가 사용되는데
토너먼저 대진표 등과 같이 계층적인 자료들을 다룰 때도 트리가 가장 어울린다.
트리는 말 그대로 나무 이므로, 트리를 구성하는 요소들 및 용어들은 대부분
나무의 각 부분들의 용어를 따온 경우가 많으므로 이해하긴 쉬울 것이다.
단, 진짜 나무는 뿌리가 아래에 있지만, 프로그래밍의 트리구조는 뿌리가 위에있다는 점
(나무를 거꾸로 뒤집은 상태)의 차이점은 있다.
위 그림을 보다시피 동그라미는 노드라고 하는데, 연결리스트와 같다.
노드는 노드를 연결하는 링크(Link)를 가진다.
단, 트리에선 노드라는 용어대신 버텍스(vertex) , 링크라는 용어대신 엣지(edge)라는 용어를 사용하기도 한다.
아래 그림을 보고 더 많은 용어를 공부해 보자.
1. 트리의 기본이 되는 최상층의 노드를 루트 (뿌리) 라고 한다.
모든 트리는 단 하나의 유일한 루트를 가지며, 아래로 무수한 노드를 가지게 된다.
2. 최상위 노드부터 1 , 2, 3, 4 단계로 나뉘는데, 이것을 레벨이라고 부른다.
최상위 즉, 루트는 1레벨. 그 아래 B, C 는 2레벨, 그 아래 3, 그 아래를 4레벨이라 부른다.
C 언어는 모든 숫자를 0부터 시작하지만 트리의 레벨은 1부터 시작(One Base)한다 또, 최고 레벨인 4를 이 트리의 높이라고한다. 즉 이 트리의 높이는 4 이다.
3. 트리를 구성하는 노드 중, 아래쪽의 노드를 자식이라고 하며 위쪽의 노드를 부모라고 한다.
위 그림에서 B, C는 A의 자식이며 D, E, F의 부모는 B이다.
같은 부모를 가진 노드들을 형제라고 하는데 G, H는 공동의 부모 C에 소속되어 있으므로 형제 관계이다.
직속 관계가 아니더라도 아래쪽에 있으면 후손이며 위쪽에 있으면 선조라고 한다.
4. 경로(Path)란 특정 노드에서 다른 노드로 가는 길이다.
어떤 하나의 노드에서 다른 노드로 가는 길은 단 하나뿐이다.
왜냐하면, 두 노드의 공동의 선조까지 올라간 후 다시 아래로 내려가야 하기 때문이다.
I에서 K로 가는 경로는 I-D-B-F-K 단 하나밖에 없다.
5. 차수(Degree)는 자식 노드의 개수인데 B의 차수는 3, C의 차수는 2, M의 차수는 0이다.
차수가 0인 노드, 즉, 자식이 하나도 없는 노드를 잎(Leaf) 노드 또는 외부(External) 노드라고 하며
자식이 있는 노드를 내부(Internal) 노드라고 한다.
6.
순서트리(Ordered Tree)와 비순서 트리(Oriented Tree).
위 그림과 같은 두개의 트리에서 모두 A 밑에 B, C를 자식으로 가지는데,
순서트리(Ordered Tree)라면 이 둘은 다른것이고, 비순서 트리(Oriented Tree)라면 이 둘은 같은 것이다.
순서트리란, 순서가 있는 트리, 비순서 트리란 순서가 의미가 없는 트리를 말한다.
7. 순회 : Order.
순회 방법 -
- 1. 전위순회 ( PreOrder )
- 2. 중위순회 ( InOrder )
- 3. 후위순회 ( PostOrder )
- 4. 레벨순회 ( levelOrder )
순회는 다음 강의에서 알아보자.
마지막으로, 트리를 구성하는 작은 트리를 서브 트리(Sub Tree)라고 하며,
트리가 여러개 모인것은 포레스트(forest)라고 하는데, 나무가 모여 숲은 이루는 것과 같은 이치이다.
