[자료구조] Red Black Tree 1. 정의 BST를 기반으로하는 트리 형식의 자료구조 검색, 삽입, 삭제의 시간이 $O(logN)$이 소요 됨 2. 규칙 모든 노드는 빨간색이나 검은색 루트는 항상 검은색 새로 추가되는 노드는 빨간색 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 함 어떤 경로에서도 빨간색 노드가 연속으로 2개가 있으면 안됨 모든 빈 노드(null)는 검은색이라고 가정 2.1 균형을 맞추는 방법 이모 노드가 검은색인 경우 회전을 시킴 회전 후에, 부모 노드는 검은색, 두 자식 노드는 빨간색이어야 함 이모 노드가 빨간색인 경우 색깔을 전환 전환 후에, 부모 노드는 빨간색, 두 자식 노드는 검은색이어야 함 3. 구현 public class RedBlackTree..
CS/[DATA STRUCTURE]
[자료구조] AVL트리 1. 정의 스스로 균형을 잡는 이진 탐색 트리 왼쪽과 오른쪽의 높이 차가 1이하여야 함. 항상 O(logN)의 시간복잡도를 보장 2. 구현 //AVL트리의 생성자 public AVLTree() { root = null; currentSize = 0; } //기본 노드 class Node { T data; Node left; Node right; Node parent; public Node(T obj) { data = obj; parent = null; left = null; right = null; } } //추가 메서드 public void add(E obj) { Node node = new Node(obj); if (root == null) { root = node; curre..
[자료구조] 힙 1. 정의 이진 트리 구조로 이루어져 있다. 최대값과 최소값을 빨리 찾아낼 수 있다. 최대 힙 항상, 자식 노드 부모 노드 관계를 만족해야 한다. 노드의 개수를 n이라고 하면 트리의 높이는 $log_2(n+1) - 1$로 구할 수 있다. 2. 추가 제거 이제부터 최대 힙 기준으로 설명하겠습니다. 추가 비어있는 공간에 노드를 추가한다. 부모 노드보다 자식 노드가 더 크면 두 노드의 자리를 바꾼다. public void add(E obj) { array[++lastposition] = obj; // 1. 노드 추가 trickleUp(lastposition); // 2. trickle up - 부모 노드와 자식 노드를 바꿀지 ..
[자료구조] 트리 1. 정의 트리는 각각의 노드들을 간선(edge)로 연결한 자료구조로써, 각각의 노드들은 부모-자식 관계를 가진다. 뿌리(root): 트리의 시작 잎(leaf): 자식이 없는 노드 간선의 수에 따라 level을 나눈다. 1.1 완전 트리(Complete Tree) 잎이 아닌 모든 노드가 2개의 자식 노드를 가지고 있고, 마지막 줄은 왼쪽에서 오른쪽 순서로 채워져 있는 트리 1.2 정 트리(Full tree) 잎이 아닌 모든 노드가 2개의 자식 노드를 가지고 있고, 모든 잎이 같은 레벨에 있는 트리 2. 순회 전위 순회(Pre order traversal / Depth first traversal) : 루트 노드에서 시작하여, 왼쪽 자식 노드로 갔다가 오른쪽 자식 노드로 가는 순회 방법 ..
[자료구조] 해시 1. 해시 데이터를 빠르게 추가하거나 제거하도록 하는 데이터 구조 키(key)와 값(value)를 가지고 있음 → 키가 주어지면 평균 O(1)의 속도로 값을 찾을 수 있음 2. 해시함수 속도가 빠름 데이터의 속성 두개가 같으면 같은 값을 반환해야 함 동일한 상황일 때 항상 같은 값을 반환해야 함 새로 실행하면 객체가 같아도 다른 값이 나올 수 있음 → 객체들은 실행할 때마다 다른 주소에 저장되기 때문 충돌(collison)이 발생하지 않도록 만들어야 함 충돌: 서로 다른 값을 가진 키가 일치하는 경우 해시의 크기를 홀수로 설정(% 연산으로 다양한 값이 나오게 함) 해시의 크기를 소수로 설정 해시 함수의 반환 값을 hashcode라고 함 → 해시 테이블의 인덱스를 결정 해시코드는 최대한 ..
[자료구조] 연결 리스트(Linked List) 1. 정의 포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조 배열의 단점(데이터 추가, 삭제시 shift 비용 발생)을 해결 각각의 노드들은 다음 노드를 가리키는 포인터, 자신의 값을 가지고 있는 데이터를 가리키는 포인터 2개로 구성 마지막 노드의 다음 노드는 없으므로 null을 가리키게 된다. head라는 포인터는 첫번째 노드의 주소를 가지고 있다. 힙에서는 연결 리스트의 head만 알고 있기 때문에 head.next를 이용하여 연결리스트를 탐색한다. 1.1 배열과 비교 배열 논리적 저장 순서와 물리적 저장 순서가 일치 찾고자 하는 원소의 인덱스를 알고 있으면 O(1)으로 원소에 접근 가능 → Random Access 가능 삭제와 삽입시 빈 공간이 ..
[자료구조] 스택과 큐 1. 정의 1. 스택 Stack : 쌓는다는 의미 → 차곡차곡 쌓는 자료구조 LIFO : Last In First Out 구조 top에 있는 자료가 가장 최신의 자료 한쪽에서 자료의 삽입과 삭제가 반복 됨 1.2 큐 Queue : 줄서서 기다린다는 의미 → 먼저 들어오는게 먼저 나가는 자료 구조 FIFO : First In First Out 구조 큐의 양끝에서 자료 추가와 삭제가 이루어짐 2. 구현 2.1 스택 class Stack { static class Node { private T data; private Node next; public Node(T data) { this.data = data; } } private Node top; //데이터 제거 public T pop(..
