Computer Science/자료구조15 [자료구조] 히프 (Heap) 히프 (Heap) 루트 노드가 언제나 그 트리의 최대값 혹은 최소값을 가지는 완전 이진 트리 최대 트리 : 노드의 키 값이 자식 노드 키 값보다 크거나 같음 최소 트리 : 노드의 키 값이 자식 노드 키 값보다 작거나 같음 힙 최초 구성 시 시간 복잡도 : O(nlogn) 우선순위 큐를 만드는데 사용! 트리의 최대값, 혹은 최소값을 반환하는 것이 주된 기능 1. 최대 히프 (Max Heap) 완전 이진 트리 & 최대 트리 부모 노드 키값 >= 자식 노드 키값 루트 노드 : 최대값 언제나 최대값이 반환됨 2. 최소 트리 (Min Heap) 완전 이진 트리 & 최소 트리 부모 노드 키값 2020. 9. 15. [자료구조] 이진 트리 순회(Traversal) 트리 순회(Traversal) 트리의 모든 노드를 한 번씩 방문하는 것을 의미 재귀 함수로 구현할 수 있다. 1. 전위 순회 (Preorder Traversal) 현재 노드를 먼저 방문 현재 노드 방문 -> 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 public static void preorder(int index, int tree[]) { if(index < tree.length) { System.out.println(tree[index]);//현재 노드 출력 preorder(index*2,tree); preorder(index*2+1,tree); } } 결과 : 1 2 4 5 3 6 7 2. 중위 순회 (Inorder Traversal) 현재 노드를 중간에 방문 왼쪽 서브트리 방문 -.. 2020. 9. 15. [자료구조] 이진 트리 (Binary Tree) 이진 트리 (Binary Tree) 모든 노드의 차수가 2 이하인 트리 이진 트리 종류 1. 포화 이진 트리 (Full Binary Tree) 모든 레벨의 노드가 꽉 차있는 이진 트리 n = 2 ^ h - 1 ( 높이가 h 인 이진 포화 트리의 노드 개수) 2. 완전 이진 트리 (Complete Binary Tree) 높이가 h 일 때, 레벨1 ~ 레벨 h-1까지는 포화 이진트리처럼 꽉 채워져 있고 마지막 레벨 h(단말 노드) 에서는 중간에 빈 노드 없이 노드가 왼쪽부터 차례로 채워져 있어야함. n < 2 ^ h - 1 (높이가 h인 완전 이진 트리의 노드 개수) 3. 편향 이진 트리 (Skewed Binary Tree) 같은 높이의 이진 트리 중에서 최소 개수의 노드 개수를 가지면서 왼쪽 혹.. 2020. 9. 8. [자료구조] 트리 (Tree) 트리 (Tree) - 계층 구조 (Hierarchical Structure)로 자료를 저장하는 자료구조 (비선형 자료구조) - 노드(Node), 간선 (Edge)의 집합 - 계층 구조 : 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조 회사 조직도 모델링 노드 종류 1. 위치 기준 노드 이름 설명 루트(Root) 노드 트리의 첫 번째 노드 단말(Leaf 혹은 Terminal) 노드 자식 노드가 없는 노드 내부 (Internal) 노드 자식 노드가 있는 노드 2. 관계 기준 노드 이름 설명 부모(Parent) 노드 자식 노드와 간선(Edge)으로 연결 자식(Child) 노드 부모 노드와 간선(Edge)으로 연결 선조(Ancestor) 노드 루트 노드 - 부모 노드까지 경로 상에 있는 모든.. 2020. 8. 31. 이전 1 2 3 4 다음
