Tree Structure 노트2 - Binary Tree

이진 트리(Binary Tree)와 그 특성

ㆍ이진트리는 재귀적(recursive) 자료구조이다

- 이진트리의 재귀적 정의 : null tree는 이진트리이다, 왼쪽 subtree L이 이진트리이고 오른쪽 subtree R이 이진트리라면 root R과 결합된 R + L  + R 역시 이진트리이다.

- 재귀식 이진트리의 정의는 많은 알고리즘을 암시해줌. 따라서 이진트리에 적용되는 알고리즘은 모두 recursive 하게 짤 수 있음.

 

이진트리는 전형적인 Regular(정규) 자료구조. 정규 자료구조란 전체 구조의 세부 단위가 모두 동일한 구조를 가진 자료구조.

 

이진 트리의 오묘한 특성 : 이진 트리는 순서가 있는 트리이다(Ordered Tree), Leaf 노드의 개수와 중간노드 개수에는 긴말한 상관관계가 있다. n0 = n1 + 1(모든 internal node degree가 2 또는 0일때)  

 

특별한 이진트리의 종류

ㆍFull binary tree (포화 이진트리) : 모든 노드의 degree가 2. Leaf 노드들이 같은 레벨에 다 있는 것.

ㆍComplete binary tree (완전 이진트리) : full binary tree에서 첫번째 leaf를 제외하고 leaf 노드들이 연속되게 지워진 것들. => 마지막 level을 제외한 나머지 모든 level에 노드들이 가득 차있고, 마지막 level에서 노드는 가장 왼쪽부터 채워지는 형태의 tree. 이 구조를 통해서 Binary Heap 이라는 데이터 구조를 만들수 있는데 이것이 Heap. Complete binary tree의 구현에는 Array를 사용하는게 일반적이라고 함.

ㆍDegenerate Tree (Pathological Tree) : 모든 interval 노드가 하나의 child만을 가질때의 트리. Linked List와 성능 동일. Skewed tree라고도 하는듯.

ㆍPerfect binary tree : 모든 interval 노드가 두개의 child들을 가지고 있고 모든 leaf 노드가 같은 level에 있을때의 트리. Height가 h인 Perfect binary tree에서는 2^h - 1 개의 노드를 가짐. 

 

이진트리 저장 방법

- full binary tree라고 가정하고 선형 배열에 넣는 방법

특정 노드의 parent구할때, 노드 인덱스/2 에 정수를 취하면 parent의 인덱스 구해짐.

반대로 특정 노드의 child구할떄, 노드 인덱스*2와 노드 인덱스*2+1하면 child 번호 구해짐. (이 특성을 이용해서 second max value 찾기 알고리즘 했던 기억있음) 

- 각 노드에 포인터를 메다는 방법 (한 방향, 또는 두 방향, 아래위로 탐색이 가능하도록) 

- Vector에 parent만 메다는 방법 (잘 안쓰는 방법)

- 기타 다른 정보 추가 후 augmentation(증가) 시키는 방법

 

이진트리의 순회(traverse) 방법 : 모두 빠짐없이, 중복없이 

ㆍPostorder : Left - Right - Root

ㆍPreorder : root - Left - Right

ㆍInorder : Left - root - Right

 

depth(T) 구하기

depth(T) = max(depth(T.left), depth(T.right)) + 1. Recursive하게 표현. depth(null)은 0.

depth(tree T) {

    if( T == null) return;

    else {

          da = depth(T -> T.left);

          db = depth(T -> T.right);

    }

    return max (da, db+1);

}

 

Inorder와 Preorder/Postorder중 하나가 주어지면 트리를 reconstruction(재구성) 가능

 

이진트리가 있을때 재귀적으로 구하기

- 전체 노드의 수: Su(T) = Su(T->TLeft) + Su(T->TRight) + 1

- 전체 Leaf 노드의 수: L(T) = L(TLeft) + L(TRight), L(T == null) return 1

- max depth(T): Depth(TLeft) + Depth(TRight) + 1 

 

Extended Binary Tree의 Extended Node의 수는 Internal Node수 + 1

 

쓰레드 이진트리(out of dated 자료구조)

쓰레기같은 tree..라고함 memory 아끼기 위한 자료구조. (오늘 우연히 연구실원들이랑 쓰레드 이진트리 얘기가 나왔는데 안쓰는 거였네 어쩐지 듣도 보도 못한 트리였음 )