Tree !?
이름 그대로 나무를 생각하면 된다.
근데 나무를 뒤짚어서 생각하면 된다.
요건 나무라고 생각해보면 A는 루트이고 J,K가 맨 위에 있는 나뭇가지이다.
🙋♂️ 그렇다면 선형 자료 구조에 배열, 리스트 등도 있지만 트리가 왜 나왔을까?
선형 구조 : 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있다.
비선형 구조 : 표현에 초점이 맞춰져 있다.
1. 시간 복잡도에서의 개선
일반 배열에서 삽입, 삭제를 하는데 O(n)의 시간이 걸린다.
배열의 첫번째 원소에 삽입하는 경우, 나머지 모든 요소들을 한 칸씩 뒤로 미뤄야 하므로 최악의 시간 복잡도인 O(n)이 나온다.
하지만, 트리는 편향 트리가 아닌 이상 일반적인 트리에서는 O(logN) 정도의 시간으로 줄여진다.
2. 계층 구조
위의 그림을 보다 시피, Root 밑으로 각각의 depth=층이 있고
그 안에 각각의 원소들이 위치해 있다.
어느 부모를 갖고 있는지만 알면 그곳에 따라 자식들을 찾기가 수월하다.
특징
- 정점과 간선을 이용해 사이클을 이루지 않도록 구성한 Graph의 특수한 형태로, 계층이 있는 데이터를 표현하기에 적합하다.
- Tree는 Stack이나 Queue와 같이 선형 구조가 아닌 비선형 자료구조이다.
- 계층적 관계를 표현한다.
- 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 갖는다.
Tree Components
위 그림을 다시보자.
A,B,C,D,E,F,G,H,I,J 와 같은 각각의 요소들을 우리는 노드라고 부른다.
그리고 그 노드와 노드들을 계층적으로 연결하는 선을 Edge(엣지)라고 부른다.
트리 구조에서 가장 최상위에 있는 노드는 Root Node라고 부른다.
하위에 다른 노드가 연결되어 있지 않은 H,I,J와 같은 노드들을 우리는 Terminal Node(단말 노드)라고 부른다.
단말 노드를 제외한 루트 노드를 포함한 모든 노드를 Internal Node라고 부른다.
다양한 형태의 트리
Binary Tree(이진 트리)
- 루트 노드를 중심으로 2개의 서브 트리로 나뉘어 진다. (노드가 없을 수도 있다.) 나뉘어진 2개의 서브 트리도 모두 이진 트리여야 한다. (2가지 경우만을 가지고 있어야 한다는 것이다.)
- 각 층 별로 숫자를 매겨 이를 트리의 레벨이라고 한다. 레벨은 1부터 시작하고 루트 노드의 레벨은 1이다. 트리의 최고 레벨을 가리켜 트리의 높이라고 한다.
- 종류
- Full Binary Tree(포화 이진 트리)
- 모든 레벨이 꽉 찬 이진 트리를 의미한다.
- 레벨 별로 노드의 갯수가 1,2,4,8,16..으로 늘어난다. 일반적인 이진트리에서 각 레벨 별 최대 노드의 개수는 2^(k-1)이 된다.
- 레벨 별 노드는 공비가 2인 등비 수열이라고 볼 수 있으므로 등비 수열의 합으로 생각하면 높이가 h인 이진트리가 가질 수 있는 최대 노드 수는 2^h-1이라고 할 수 있다.
- Complete Binary tree(완전 이진 트리)
- 왼쪽에서 오른쪽으로 차곡 차곡 채워진 이진 트리이다.
- 노드를 삽입할 때, 왼쪽부터 차례대로 삽입하는 트리이다. 왼쪽이 비어있고 오른쪽이 들어가있는 트리는 완전 이진 트리가 아니다.
- Skewed Binary Tree(편향 이진 트리)
- 모든 노드가 부모의 왼쪽 자식이기에 왼쪽으로 편향되어 있거나 반대로 모든 노드가 부모의 오른쪽 자식이기에 오른쪽으로 편향된 이진트리를 말한다.
developer