Computer Science/Data Structure
-
AVL 트리Computer Science/Data Structure 2021. 9. 24. 16:23
AVL 트리의 정의 ㆍ 균형 잡힌 높이의 이진 검색 트리이다. ㆍ 두 개의 자식 노드들 간에 깊이 차이가 1 이하인 트리이다. AVL 트리의 장점 ㆍ 트리의 검색 연산이 항상 O(log n)으로 균형 잡혀 있다. ㆍ 트리의 삭제 연산 또한 O(log n)으로 균형 잡혀 있다. AVL 트리의 단점 ㆍ 삽입 연산이 이루어질 때 트리의 재구성 시간이 소요된다. ㆍ 이진 검색 트리보다 구현의 난이도가 높다. 구현 방법 relink() 메서드 protected void relink(Node parent, Node child, boolean makeLeft) { if (child != null) child.parent = parent; if (makeLeft) parent.left = child; else pare..
-
이진 검색 트리Computer Science/Data Structure 2021. 9. 24. 16:04
이진 검색 트리의 정의 ㆍ 각 노드는 (키, 값)의 쌍을 저장하며, 서로 다른 노드의 키는 다르다. ㆍ 왼쪽 서브 트리에 저장된 노드의 키보다는 크다. ㆍ 오른쪽 서브 트리에 저장된 노드의 키보다는 작다. 이진 검색 트리의 장점 ㆍ 심볼 테이블을 정렬된 순서로 유지할 필요 없다. ㆍ 새로 삽입되는 노드는 항상 리프 노드에 위치한다. 이진 검색 트리의 단점 ㆍ 균형 트리를 보장하지 않는다. ㆍ 감색 시 많은 시간이 소요된다. 구현 방법 노드의 구성 class Node { K key; V value; Node left, right; int N; int aux; Node parent; public Node(K key, V value) { this.key = key; this.value = value; this..
-
연결 리스트를 이용한 순차 검색Computer Science/Data Structure 2021. 9. 24. 12:31
Symbol Table이란? ㆍ (키, 값) 쌍이 모인 자료구조 ㆍ 특정 키와 그 키에 해당되는 값의 쌍을 삽입할 수 있다. ㆍ 키가 주어질 때, 관련된 값을 검색할 수 있다. 연결 리스트를 이용한 Symbol Table의 동작 방법 구현 방법 노드의 구성 class Node { K key; V value; Node next; public Node(K key, V value, Node next) { this.key = key; this.value = value; this.next = next; } } ㆍ 노드는 키, 값, 다음 노드를 가리키는 참조로 구성되어 있다. Symbol Table의 기본 구성 public class SequentialSearchST { private Node first; int ..
-
배열을 이용한 이진 검색Computer Science/Data Structure 2021. 9. 24. 12:20
Symbol Table 이란? ㆍ (키, 값) 쌍이 모인 자료구조 ㆍ 특정 키와 그 키에 해당되는 값의 쌍을 삽입할 수 있다. ㆍ 키가 주어질 때, 관련된 값을 검색할 수 있다. 배열을 이용한 Symbol Table의 동작 방법 구현 방법 Symbol Table의 기본 구성 public class BinarySearchST { private static final int INIT_CAPACITY = 10; private K[] keys; private V[] values; private int N; } ㆍ 키를 저장하는 배열 K[ ], 값을 저장하는 배열 V[ ]가 있다. ㆍ (키, 값) 쌍의 개수에 대한 변수인 N이 있다. search() 메서드 private int search(K key) { int..