이전에 포스팅 했던 편향 이진 탐색 트리를 해결 하기 위한 방법 중 하나인 AVL TREE 가 아닌 또 다른 해결 방법인 RED-BLACK TREE에 대해서 알아보자. RED-BLACK TREE 레드-블랙 트리도 처음 공부할 때, 많이 헷갈릴 수 있다. 특히 나중에 해결하기 위한 방법으로 Recoloring 과 Restructuring 방식 두 가지가 나오는데, 언제 적용해야 하는지가 분명하지만 이상하게도 자주 헷갈린다! 이를 쉽게 구분하기 위한 개인적인 팁도 제공해보려고 한다. 먼저 RED-BLACK TREE 의 특징에 대해서 알아보자. RED-BLACK TREE 특징 모든 노드는 빨간색 or 검은색 이다. 루트 노드는 무조건 검은색이다. RED-BLACK 트리에 존재하는 NIL은 검은색이다. 빨간색 ..
Hash Function 데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수와 관련된 용어를 먼저 살펴보자. Key : 매핑 전 값 Hash value : 매핑 후의 값 Hashing : 매핑하는 과정 위의 용어들을 기본으로 두고 자세히 살펴보자. Hash Table 해시 테이블은 Key를 Hash Function을 사용하여 Hash value로 매핑하고, 이 Hash Value를 index로 Data를 저장하는 방식이다. 듣다보면 파이썬, JS의 Dictionary, 자바의 Map이 떠오를건데 바로 Hash Table을 방식을 택한 자료구조 이다. 위 사진을 보면 buckets 라는 것이 보인다. buckets 는 해시 테이블에서 데이터가 저장..
AVL(Adelson-Velsky and Landis)TREE AVL의 full form은 발명자의 이름이다. 먼저 AVL 트리의 특징에 대해서 살펴보자. 특징 이진탐색트리의 속성을 그대로 가진다. 왼쪽, 오른쪽 서브트리의 높이 차이가 최대 1이어야 한다. 높이 차이가 1보다 커지면 Rotation을 통해 균형을 맞춘다. Rotation 방식을 설명하기 전에, 먼저 높이 차이를 비교하는 BF에 대해서 먼저 이해할 필요가 있다. BF(Balance Factor) $ BF(K) = K_{leftHeight} - K_{rightHeight} $, K = Node 수식처럼 노드의 왼쪽 높이와 오른쪽 높이를 비교하는 요소를 BF 라고 한다. 만약 height의 의미가 이해가 안된다면, 트리의 특징에서 height..
