트리

<가장 일반적인 트리의 형태>

struct treeNode {
    int element;
    treeNode * parent;
    vector<treeNode*> children;
}

 

<용어정리>

* 이진 트리: 자식을 최대 두 개 갖는 트리

 

* 이진 탐색 트리:

이진트리. 어떤 노드에서 left엔 자기보다 작은 값, right엔 자기보다 큰 값을 유지하는 식

 

* 힙:

포화 이진트리. 노드가 들어갈 수 있는 자리가 비어있는 경우가 없으므로 일반적으로 배열로 구현.

 

* 구간트리:

 

* 상호 배타적 집합 구조(disjoint set) :

각 노드는 부모를 가리키는 포인터는 있지만 자식에 대한 정보는 없다.