728x90 Algorithm/알고리즘 기본27 [Algorithm] Binary Search Tree - Search Binary Search Tree 의 Search 구현 앞에서 Binary Search Tree의 정의와 insert를 구현을 해봤다. 이번에는 Search를 알아보고 구현해보자. Search 구현 search 구현은 참 간단하다 그래도 설명을 하면 더 쉽게 이해 되니 그림으로 먼저 알아보자. 일단 글로 설명하자면 root 부터 비교를 한다 root 값보다 작으면 왼쪽으로 이동 root 값보다 크면 오른쪽으로 이동 이동하면서 탐색을 반복한다. Search 코드 구현 // rootNode 는 멤버면수이다. public Node searchNode(int data) { // rootNode 가 null 이면 리턴 if (rootNode == null) { System.out.println("Can not f.. 2021. 6. 8. [Algorithm] Binary Search Tree - Insert Binary Search Tree 컴공때 배웠던걸 복습할겸 다시 공부할겸 정리할겸 겸사겸사 특징 자식을 최대 2개만 가질수 있는 트리이다. root 의 왼쪽값은 root 의 값보다 작다. root 의 오른쪽 값은 root의 값보다 크다. Insert, Search, Delete, Successor, Predecessor 을 구현한다. Binary Search Tree 의 구조 다음은 Binary search tree 의 구조이다 100 이 처음에 들어와 루트가 되었고 50 을 넣을때 100 과 비교한다. 부모보다 작기 때문에 왼쪽에 추가해준다. 200 이 들어왔을때 부모의 값보다 크기 때문에 오른쪽 에 추가해준다. 이걸 반복하면 다음과 같은 그림이 된다. Insert 구현 위의 예시대로 구현 하면된다. .. 2021. 6. 8. [Algorithm] Counting Sort Counting Sort? counting sort는 data의 수를 count 해서 정렬하는 방법이다. 특징 O(n+k): k 는 정렬할 숫자 중에 제일 큰값. 배열의 크기가 아닌 최대값의 영향을 받는다. 서로 비교를 하지 않고 숫자를 세어 정렬하는 방식. 최대값에 따라 영향을 받기 때문에 작은 범위에서 효율적이다. stable한 알고리즘이다. 입력에 동일한 값이 있을때 먼저 나오는 값이 출력에서도 먼저 나온다 분석 1. 데이터들의 숫자를 카운트한다. 2. 카운트 된 숫자를 출력한다. 구현 public class CountingSort { public static void main(String[] args) { int maxCount = 30; int[] arrayA = {2,5,3,0,2,3,0,3}.. 2021. 5. 21. [Algorithm] Max heapify 구현과 이론 Max heapify 최대힙에 대해서 알아보고 구현까지 해보자 힙이란? 완전이진트리의 한 종류이다. 힙의조건 heap property를 만족해야 된다. Heap property 1.Max heap property 부모는 자식보다 크거나 같다. 2.Min heap property 부모는 자식보다 작거나 같다. 힙의구조 구현방법 1. Tree의 index 표현 root = i; Left child = i * 2 Right child = i * 2 +1 2. Swap 방법 자식노드가 부모노드 보다 크면 자리를 변경한다. 3. 반복하면서 Max heap을 만들어 간다. 4. 실제로 구현할 때는 맨 마지막 노드 즉 index 7번의 부모노드부터 선택하여 반복 정렬해간다. 그래야 순차적으로 root들을 기준으로 m.. 2021. 5. 4. 이전 1 ··· 3 4 5 6 7 다음 728x90 반응형
