[Java] 비선형 자료구조 - 트리

트리 (Tree) Tree란? 트리는 영어 단어 그대로 가지가 뻗어 있는 모양으로 노드와 간선으로 구성된 그래프의 일종이다. 그래프와 다른 점은 하나의 노드에서 다른 노드로 이동하는 경로가 유일하다는 점이다. 이를 Acycle이라고 한다. 트리는 폴더 구조, 조직도, 가계도 등 계층적 구조를 나타날 때 사용 한다. 트리의 구조 트리 구조의 자료 값을 담고 있는 단위를 노드(Node)라고 한다. 그리고 노드 간의 연결선을 에지(Edge)라고 한다. 이렇게 연결된 두 노드 중 상위의 노드를 부모(Parent) 노드, 하위의 노드를 자식(Child) 노드라고 한다. 그리고 같은 부모를 가지는 노드를 형제(Sibling) 노드라고 한다. 자신을 포함한 자식 노드의 개수를 크기(Size)라고 하며, 각 노드가 지..

• format_list_bulleted 자료구조/비선형 자료구조
• · 2024. 3. 4.
• textsms

[Java]힙(Heap) 자료구조

힙(Heap)이란 ? 힙은 완전 이진트리 형태로 최대, 최소 값을 빠르게 찾아내는데 유용한 자료구조이다. 힙은 중복 값을 허용하며, 부모 - 자식 간 정렬은 보장하나 형제간의 정렬은 보장하지 않는다. (반 정렬 상태) 최소 힙( Min Heap) 최소 힙은 부모 노드의 Key가 자식 노드의 Key보다 작거나 같은 완전 이진트리이다. 최소 힙 - 삽입 트리의 가장 끝 위치에 데이터 삽입 부모 노드와 키 비교한 후 부모 보다 작을 경우 부모와 자리 교체 (반복) 최소 힙 - 삭제 최상위 노드 반환 및 삭제 가장 마지막 위치의 노드를 최상위 노드로 위치 시킴 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체 (반복) 최소 힙 - 구현 기본 구조 ArrayList heap; MinHeap() {..

• format_list_bulleted 자료구조/비선형 자료구조
• · 2023. 12. 17.
• textsms