Crat

3-2. 힙 트리(Heap Tree)

0. 이진 트리(Binary Tree) 각 노드가 최대 두 개의 자식 노드를 가지는 트리 위의 두 조건을 거치면 특정 값을 찾을 수 있다. 왼쪽 혹은 오른쪽으로 진행할 때 검색할 필요가 없는 나머지 부분은 날려버리고(메모리 절약) 검색을 수행한다. 그리고 각 숫자를 한쪽으로만 추가하면 균형이 깨지므로 트리 재배치로 균형을 유지하는 것이 중요하다. 1. 힙 트리의 특징 (1) 부모 노드의 값은 항상 자식 노드의 값보다 커야 한다 - 형제 노드 간 어떤 규칙도 만족할 필요가 없다. (2) 노드 개수를 알면 트리 구조를 정확히 확정할 수 있다 - 완전 이진 트리 ; 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 마지막 레벨에 노드가 있을 때에는 반드시 왼쪽부터 순서대로 채워야 한다. => ..

3-1. 트리 기초

1. 개념 계층적 구조를 가지는 데이터를 표현하기 위한 자료 구조 (1) 노드(Node) : 각 데이터를 표현하는 정점 (2) 간선(Edge) : 노드의 계층 구조를 표현하기 위해 사용하는 화살표 2. 관련 용어 - 부모 노드, 자식 노드, 형제 노드 - 선조, 자손 - 루트 ; 최상위 노드, 잎 ; 최하위 노드 - 깊이 ; 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 - 높이 ; 가장 깊숙히 있는 노드의 깊이 - 트리의 재귀적 속성 ; 트리의 일부분만 잘라도 트리의 속성을 띄고 있음 - 서브트리 3. 코드로 작성해보기 (1) 노드(Node) #include #include #include // shared_ptr 사용 #include #include #include using namesp..