Red-Black 트리 이진 트리에서 편향 이진 트리와 같은 최악의 시간복잡도를 같는 경우를 해결하기 위해 균형 트리인 AVL트리가 존재했었다. Red-Black 트리는 AVL과 동일하게 균형 트리이지만, AVL 트리보다는 덜 균형하다는 특징이 있다. 즉, 균형트리에서 삽입이나 삭제가 많은 경우 Red-Black 트리를 사용하는 것이 유리하며, 탐색이 많은 경우 AVL 트리가 유리하다. 평균과 최악의 상황에서 검색, 삽입, 삭제 등 모두 log(N)의 시간 복잡도를 갖는다. Red-Black 트리의 규칙 Red-Black 트리에는 5가지 규칙이 있다. 해당 규칙을 위배하는 순간 노드 재배치를 진행한다. 규칙은 다음과 같다. 모든 노드는 빨강 또는 검정이다. 루트 노드는 항상 검정이다. 모든 리프 노드는 ..

자료구조 vs 객체 자료구조 vs 객체 //자료구조 public interface Vehicle { double getFuelTankCapacityInGallons(); double getGallonsOfGasoline(); } public class Car implements Vehicle { double fuelTankCapacityInGallons; double gallonsOfGasoline; public double getFuelTankCapacityInGallons() { return this.fuelTankCapacityInGallons; } public double getGallonsOfGasoline() { return this.gallonsOfGasoline; } } 자료구조는 값을 가..

트리 구조 트리 : Node 와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 주로 이진 트리 형태의 구조로 탐색 알고리즘 구현에서 많이 사용 된다. 트리 용어 Node : 데이터를 저장하는 요소 Root Node : 최상위 노드 (레벨 0) Level : 노드의 깊이 Sibling (Brother Node) : 동일한 부모를 가진 노드 Depth : 트리에서 Node를 가질 수 있는 최대 레벨 이진트리와 이진 탐색 트리 이진 트리 (Binary Tree) : 최대 브랜치가 2인 트리 이진 탐색 트리 : BST (이진 트리에 추가적인 조건이 있는 트리) 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값 장점 : 탐색 속도 개선 단점 : 복잡하다. class N..

해시 테이블 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다. 파이썬 딕셔너리 타입이 해쉬 테이블의 예 보통 배열로 미리 Hash Table 사이즈 만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 블록 체인에서 사용 파이썬에서는 해쉬를 별도로 구현할 이유가 없다. 딕셔너리 자체가 해쉬테이블 용어 Hash : 임의의 값을 고정 길이로 변환 Hash Table : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수 : 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값 또는 해쉬 주소 : 키를 해싱 함수로 연산해서, 해쉬 값을 알아내고 키에 대한 위치를 일관성있게 찾을 수 있다...