Python : 트리 (Tree)
이제 그림이 많이 나올 예정이다.. PPT로 만드느라 시간은 많이 걸리지만 이해하기에는 굉장히 도움이 많이 되고 있고, 혹시나 문제가 있다면 수정 요청해주셨으면 한다!
트리 (Tree)
: 아래의 조건을 만족하는 한 개 이상의 노드로 이루어진 유한 집합. (node가 한개여도 트리라고 부를 수 있다)
- 노드 중 최상위 노드를 루트(root)
- 나머지 노드들은 n(>= 0)개의 분리 집합 T1, ... TN으로 분리 가능
- 분리 집합들이 각각의 하나의 트리가 되며(재귀적 정의) root의 부 트리(subtree)라고 한다
- 노드(node) : 트리의 원소 (A, B, C, D, E, F, G, H, I, J, K)
- 간선(edge) : 노드를 연결하는 선. 부모 노드와 자식 노드를 연결
- 루트 노드(root node) - 트리의 시작 노드 ( A )
트리 - 용어정리
부모 노드 : 간선으로 연결되어있는 노드 중 상위 레벨의 노드
ex) B는 E와 F의 부모 노드, C는 G의 부모 노드, F는 K의 부모 노드
자식 노드 : 간선으로 연결되어있는 노드 중 하위 레벨의 노드 (자식 != 자손)
ex) B의 자식 노드는 E, F, D의 자식 노드는 H, I, J
형제 노드 : 같은 부모 노드의 자식 노드들 (바로 옆 노드)
ex) B, C, D는 A가 부모인 모두 형제 노드
조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
ex) K의 조상 노드는 F, B, A
서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
ex) A와 D의 간선을 끊는다면 부모가 D, 자식이 H, I, J 인 서브 트리가 생성된다
자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 (본인과 연결된 리프노드까지 하위 레벨의 모든 노드)
ex) B의 자손 노드는 E, F, K
차수 (degree)
- 노드의 차수 : 노드에 연결된 자식 노드의 수 (B의 차수 = 2, C의 차수 = 1)
- 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 (트리 T의 차수 = 3, 부트리 T1의 차수 = 2, 부트리 T3의 차수 = 1)
- 단말 노드(리프 노드) : 차수가 0인 노드. 자식 노드가 없는 노드를 뜻한다
높이
- 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨 (B의 높이 = 1, F의 높이 = 2)
- 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨 (트리 T의 높이 = 3)
- *높이의 경우는 교육 자료마다 다를 수 있다
이진 트리
: 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리. 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 드리이며 자식 노드는 0개 혹은 1개일 수 있다.
- 왼쪽 자식 노드(left child node)
- 오른쪽 자식 노드(right child node)
이진 트리의 특성
- 레벨 i 에서의 노드의 최대 개수는 2**i개
- 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2**h+1 - 1)개
각 레벨 별 노드 최대 개수 : 2 ** h 개
높이까지의 최대 노드 개수 : 2 ** (h+1) -1 개
높이까지의 최대 노드 개수는 각 레벨 별 노드 최대 개수를 더한 것인데, 2^0 + 2^1 + 2^2 + 2^3 = 2^4 - 1 (등비수열)임을 기억하자
이진 트리의 최소 개수는 h + 1인데, 이 경우 편향 이진 트리라고 한다 (아래에서 다룰 예정이다)
포화 이진 트리 (Full Binary Tree)
- 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
- 높이가 h일 때, 최대의 노드 개수인 (2**h+1 - 1)의 노드를 가진 이진 트리. 같은 높이의 노드가 채워져있다고 생각하면 편하다
- root를 1번으로 하여 (2**h+1 - 1)까지 정해진 위치에 대한 노드 번호를 가진다
- 포화 이진 트리에서 root는 항상 1로 고정이며, 순서는 '좌 - 우' 이다. BFS와 유사하다고 볼 수 있다. (예시는 위의 그림과 동일하기 때문에 생략하겠다)
완전 이진 트리 (Complete Binary Tree)
가장 많이 다루게 될 트리 종류이기 때문에 중요하다. 지금은 정의만 하고, 아래에서 자세히 다뤄볼 예정이다. 포화 이진트리와 완전 이진 트리를 헷갈릴 수 있는데, 조심해야한다.
- 높이가 h이고 노드 수가 n개 일 때 (2**h <= n <= 2**(h+1) -1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리
- 비어있는 레벨을 제외하고는 나머지 레벨은 끝까지 채워져 있어야 한다
편향 이진 트리 (Skewed Binary Tree)
- 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가지는 이진트리
- 왼쪽 편향 이진트리
- 오른쪽 편향 이진트리
- 선형구조를 이루고 있으며 비교적 비효율적
순회까지 진도를 나가고 싶었는데 정확히 이해하지 못한 부분이라 조금 더 정리하고 확실하게 해야겠다