자료구조 및 알고리즘/자료구조7 [자료구조] 자바 에서의 힙(Heap) #2 자바를 통한 힙에서 데이터 삽입 구현 자바에서 구현한 힙 트리 데이터 삽입 코드는 다음과 같다. - Heap.java // 힙 트리 데이터 추가 public boolean insert(int data) { // 방어 코드 : 힙 배열에 아무 데이터도 들어가 있지 않은 상태에서 // 메소드가 수행되는 경우를 대비하여 리스트에 데이터 값을 적재해주는 코드를 작성해준다. if(this.heapArray.size() == 0) { this.heapArray.add(null); this.heapArray.add(data); return true; } // ArrayList 에서 add 라는 메소드 자체가 리스트의 가장 마지막 부분에 // 데이터를 추가해주는 것이기 때문에 힙 트리의 마지막 요소에 데이터를 추가해주.. 2021. 11. 30. [자료구조] 자바 에서의 힙(Heap) #1 힙(Heap) 이란? - 힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) - 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 * 힙을 사용하는 이유? - 단순히 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸린다. - 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(log n) 이 걸린다. - 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다. 힙(Heap) 구조 - 힙은 최대값을 구하기 위한 구조(최대 힙 - Max Heap) 와 최소값을 구하기 위한 구조(최소 힙 - Min Heap) 로 분류할 수 있다. - 힙은 다음.. 2021. 11. 30. [자료구조] 자바 에서의 트리 #2 자바를 통해 이진 탐색 트리 구조에서 삭제 기능을 구현해보자. * 과정이 많이 복잡하기 때문에 나눠서 이해하는 것이 좋다. Leaf Node 삭제 - Leaf Node : Child Node 가 없는 Node - 삭제할 Node 의 Parent Node 가 삭제할 Node 를 가리키지 않도록 한다. Child Node 가 하나인 Node 삭제 - 삭제할 Node 의 Parent Node 가 삭제할 Node 의 Child Node 를 가리키도록 한다. Child Node 가 두 개인 Node 삭제(택1) (중요) * 삭제할 Node 의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node 의 Parent Node 가 가리키도록 한다. * 삭제할 Node 의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node 의 P.. 2021. 11. 28. [자료구조] 자바 에서의 트리 #1 트리 구조 Node 와 Branch 를 이용해서 노드간에 사이클이 이루어지지 않도록 구성한 데이터 구조이다. - 트리 중 이진 트리(Binary Tree) 형태의 구조가 탐색(검색) 알고리즘 구현을 위해 많이 이용된다. 용어 - Node : 트리에서 데이터를 저장하는 기본 요소이다.(데이터와 연결된 다른 노드에 대한 Branch 정보 포함) - Root Node : 트리의 가장 위에 있는 노드이다. - Level : 최상위 노드(Root Node)를 Level 0 이라고 했을 때, 특정 노드가 최상위 노드로부터 하위 Branch 로 연결되어 있는 깊이를 의미한다. - Parent Node : 어떤 노드의 이전 레벨에 연결된 노드 - Child Node : 어떤 노드의 하위 레벨에 연결된 노드 - Leaf.. 2021. 11. 28. 이전 1 2 다음
