KalelPark's LAB

Red & Black tree란? - Red & Black tree는 AVL tree에 색상이 입혀진 것이다. - 모든 노드는 빨강색 혹은 검정색으로 이루어져 있습니다. 또한, 리프 노드(Externel node)들은 모두 검정색으로 이루어져 있습니다. Red & Black tree's Properties 1. 루트 노드와 리프 노드는 모두 검정색 노드로 구성되어 있습니다. 2. 루튼 노드에서, 리프 노드까지의 경로에는 연속적으로 빨강색 노드가 존재할 수 없습니다. 3. 루트 노ㅌ드에서, 리프 노드까지의 모든 경로에는 동일한 검은색 노드의 개수가 존재합니다. * Red-Black Tree를 만들 때, node를 insertion할 때, Red를 우선적으로 삽입합니다. Red & Black tree's ..

AVL tree란? - Binary SearchTree의 경우, 한쪽으로 노드가 쏠릴 수 있다. 트리에서 특정 값을 찾으려면 O(N)의 시간이 필요하다. 하지만, biasedTree를 AVL tree로 구성하면, 어떤 노드를 탐색하든 O(logN)에 탐색하는 것이 가능하다. - Binary Search Tree의 속성을 가집니다. - 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. - 높이 차이가 1보다 커지면 Rotation을 활용하여, 균형을 맞춰, 높이 차이를 최소화합니다. - 삽입, 검색, 삭제의 시간 복잡도가 O(logN) 이다. (N : 노드의 개수) Balance Factor(BF) - AVL트리는 균형이 무너졌는지에 대해 판단할 때, Balance Factor라는 것을 활용합니다. A..

Hashing이란? - 선형 탐색이나, 이진 탐색은 모두 키를 저장된 키 값과 반복적으로 비교함으로써, 탐색하고자 하는 항목에 접근한다. 이러한 방법들은 최대 가능한 시간 복잡도가 O(logN)에 그친다. - 해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 용어 Identifier density - Identifier density is the ratio n/T, where n is the number of identifiers in the table. T is number of possible identifiers. (Table에 속해있는 identify의 개수) Loading factor - a = n / (s * b) 의 저장공간을 가지고 있습니..