MD 기록저장소

1. 개념 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작고 오른쪽 서브 트리는 해당 노드의 값보다 크다. 2. 순회 순회란? 이진탐색트리에 있는 모든 노드들을 한 번씩 방문하는 것. 이진탐색트리에서는 주로 중위선회(Inorder Traversal)를 사용한다. - 중위선회 루트 노드부터 시작해서 일단은 왼쪽 노드를 따라서 간다. 더 이상 왼쪽 노드가 존재하지 않는 시점의 노드까지 간 후 해당 노드를 출력한다. 그리고 그 노드의 오른쪽 노드로 옮겨간다. 만약 이 때 옮겨갈 오른쪽 노드가 존재하지 않는다면 한 단계 위 레벨의 노드로 움직인다. 그리고 맨 처음 한 것과 같이 왼쪽에 있는 맨 마지막 노드로 옮겨간다. 그리고 또 오른쪽 노드로 움직인다. 이것을 계속해서 반복한다. 3. 노드의 후임자(Suc..

1. 트리(Tree) 개념 - 노드들의 집합 - 노드: 값과 각 노드들을 가리키는 레퍼런스로 구성되어 있음 트리 관련 용어 1. 간선(edge) - 노드와 노드를 연결하는 선 - 구현 관점에서는 레퍼런스를 의미 2. 루트 노드 - 최상단에 위차한 노드 3. 자녀 노드 - 어떤 노드 밑에 연결된 노드 - 모든 노드는 0개 이상의 자녀 노드를 가진다. 4. 부모 노드 - 자녀 노드를 가지는 노드 5. 형제 노드 - 같은 부모 노드를 가지는 노드 6. 조상 노드 - 부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드 7. 자손 노드 - 자녀 노드를 따라 내려가며 만나는 모든 노드 8. 내부 노드 - 자녀 노드를 가지는 노드 9. 외부 노드(단말 노드, 리프 노드) - 자녀 노드를 가지지 않는 노드 10..

1. Set 특징 - 순서를 보장하지 않는다. - 중복을 허용하지 않는다. - 데이터 조회가 List보다 빠르다. 언제쓰는 것이 좋은가? - 중복을 허용하지 않을 때 - 데이터 존재 여부를 확인할 때 구현체 - Hash Set - Linked Hash Set - Tree Set 2. Hash Set 특징 - Hash Table을 사용 - key를 통해 바로 데이터에 접근하는 것이 가능하기 때문에 데이터 조회 속도가 빠르다. Java: Hash Set - 자바에서 Hash Set은 내부적으로 Hash Map을 이용해서 구현되어있다. - Set에 넣고 싶은 데이터를 key에 넣고 value 자리에는 임의의 dummy 데이터를 넣는다. - Set에 데이터가 있는지 없는지를 확인하기 위해서는 containsKe..

1. Map key-value 쌍을 저장하는 ADT key는 중복 불가, value는 중복 가능 언제 주로 사용하는가 1대1로 대응되는 정보를 저장할 때 ex) 이름 - 전화번호 특정 정보에 대한 카운팅을 할 때 ex) 이름 - 득표 수 구현체 Hash Table Tree 기반 자료구조 2. Hash Table (Hash Map) 배열과 해시 함수를 이용해서 Map을 구현한 자료구조 해시 함수란? 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수 Hash Table에서 해시 함수는 주로 임의의 데이터를 정수로 변환하는 역할을 담당함 특정 데이터를 해시 함수에 넣어서 나온 정수값을 '해시(hash)'라고 부른다. 데이터에 접근하는 시간이 상수 시간으로 매우 빠..

1. ADT 관점에서의 List 값을 저장하는 추상 자료형 순서가 있다. 중복을 허용한다. Set, Map을 쓰는 것이 더 적절한 상황이 아니라면 웬만해서는 List를 사용한다. 2. List 구현 (1) Array List Array 형태로 List를 구현한다. 기존 배열의 크기가 다 찼는데 새로운 값을 넣으려고 하면 기존 배열보다 큰 크기의 배열을 만든 후 기존 배열에 있던 값을 새로운 배열에 복사한다. 그리고 새로운 배열에 새로운 값을 집어넣는다. 데이터를 삭제하려면 일단 데이터가 List 안에 있는지 탐색하는데 시간이 1차적으로 걸리고, 데이터가 만약 있다면 해당 자리에 있던 데이터를 지우고 또 data shift가 일어나므로 시간이 2차적으로 소요된다. Array List 안에 있는 값을 탐색하..

1. 배열(Array) 같은 타입의 데이터들을 저장하는 자료구조 연속된 메모리 공간에 자료들을 저장 데이터들 각각은 이름은 없지만 인덱스라는 것이 주어져 있어서 인덱스로 데이터에 접근 가능 배열의 인덱스는 0부터 시작한다. 배열에 객체를 저장하는 경우에는 배열에는 객체 참조값이 저장이 된다. 객체 참조값은 연속된 메모리에 저장이 된다. 실제 객체들은 당연히 Heap 메모리에 비연속적으로 저장이 되어있을 것이다. 배열의 장점 연속된 메모리 공간에 데이터를 저장하기 때문에 CPU 캐시를 통해서 같은 배열에 있는 다른 데이터에 접근하는 시간을 단축시킬 수 있다. 2. 동적 배열(Dynamic Array) 크기가 변할 수 있는 배열 데이터를 더하거나 빼는 것이 가능한 자료구조 ex: ArrayList 3. 연관..

1. Priority Queue(우선순위 큐) 큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리되는 자료구조 주요 동작 insert: 아이템을 집어넣을 때 우선순위 정보도 같이 넣어줘야한다. delete: 우선순위가 가장 높은걸 제거한다. peek: delete와 유사하지만 실제로 우선순위 큐에서 제거하지는 않는다. 2. Heap(힙) 트리: 부모-자녀처럼 계층적인 형태를 가지는 구조 이진트리: 자녀가 최대 두 개인 트리힙은 주로 이진트리 기반으로 구현된다. Max Heap과 Min Heap 두 가지 종류가 있다. Max Heap: 부모 노드의 key가 자식 노드(들)의 key보다 크거나 같은 트리 Min Heap: 부모 노드의 key가 자식 노드(들)의 key보다 작거나 같은 트리 주요 동작 inse..