Tree

Representation

자식 node 수에 제한이 없는 일반적인 tree

: leftchid-right sbling의 linked node의 형태 (쓸일은 거의 없지싶긴함)

 

Binary Tree

: node 생성 후 linking 시켜서 표현하는게 일반적

BST도 여기 들어감.

 

Complete Binary Tree

: array로 표현하는게 저장공간측면도 그렇고 계산측면도 그렇고 훨씬 좋음

Heap도 여기 들어감.

 

 

Binary Tree Operations

1. 순회(traversal)

2. 전체 복사

3. 전체 equality 확인

4. leaf node 연산(satisfiabiltiy problem)

 

 

Binary Search Tree Operations

1. 검색

2. 삽입

3. 삭제

 

참고로 BST에 중복 key는 오지 못한다.

따라서 삽입시 우선 해당 값이 있는지 find를 먼저 진행한 후 없으면 삽입을 하는데, find 연산의 마지막 값을 활용한다.

그 값을 부모로 해서 좌 or 우 node로 값을 삽입한다.

 

삭제는 leaf node이거나 child가 하나 뿐인 node라면 그냥 삭제해버리면 된다. child있으면 그 subtree 통째로 올리면되고.

하지만 child가 2개인 node를 삭제하는 경우라면, "왼쪽 subtree의 가장 우측 leaf node" or "우측 subtree의 가장 좌측 leaf node" 를 삭제한 자리에 넣어준다.

 

 

Set 구현

Tree를 이용해 간단한 숫자들의 집합을 구현할 수 있다.

특정 숫자가 특정 집합에 포함됐는지 확인할때 사용하면 좋다.

예를들자면 순회에서 해당 번호의 node를 방문 여부를 집합으로 묶어둘 수도 있고, equivalent class 등 쉽게 구현 가능...

 

일반적인 tree와는 반대로 set의 자식이 부모를 가리키도록 한다.

주로 배열로 표현한다. root는 -1의 값을 갖고, 자식들은 부모의 index를 값으로 갖는다.

각 집합은 root로 구분되는 것이다.

 

Union과 Find 연산이 있다. (참고로 C/C++에 union은 keyword이니 구현할때 주의)

간단하다. 특정 집합끼리 union을 할땐 (1)해당 집합의 root를 찾은 후 (2)한 root가 다른 root를 가리키도록 한다.

단일 요소 set이여도 마찬가지로 적용된다.

find를 할땐 link를 타고 root(-1)가 나올때까지 가서 어떤 set인지 찾으면 된다.

 

그런데 worst case인 경우 degenerate tree라는 것이 만들어질 수 있는데, 이땐 find/union 연산이 O(n) 이다.

그래서 worst case가 발생하지 않도록 좀더 신경써서 union과 find를 할 수도 있다.

union을 할때 tree의 node 수가 많은 놈 밑으로 적은 놈이 들어가도록 한다. 이를위해 root 위치는 음수로 tree의 node 수를 카운트한다.

find를 할때는 root까지 가서 찾은 후 곧바로 해당 node와 root를 연결시키는 추가작업을 해서 다음 번에 찾을땐 더 빨리 찾을 수 있도록 한다.