솔

이번에는 c++ 표준 라이브러리인 std::map, std::unordered_map 에 대해 알아보겠습니다. 라이브러리의 이름이 map 이라고 지어진 이유는 mapping 과 관련이 있기 때문입니다.  std::map (Ordered Map)map 은 BST (이진탐색트리) , RedBlackTree(레드블랙트리) 로 구현되어 있어서키의 순서가 자동으로 정렬되고O(log N) 을 기대할 수 있습니다. 또, 트리의 형태를 유지하기 위해 추가적인 메모리를 사용하지만 Unordered_mapd 에 비하면 적고,중복된 값은 허용하지 않습니다. ( 덮어쓰기 ) std::unordered_map (Unordered Map)unordered_map 은 해시테이블로 구현되어 있어서키의 순서가 정렬되지 않고평균적으로 ..

앞에서 AVL Tree와 RedBlackTree에 대해 알아보았는데요. 이번에는 두 트리를 비교해보겠습니다. https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com https://sol248.tistory.com/64 RedBlackTree (레드-블랙 트리)레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서  앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/..

다음에 알아볼 레드블랙트리를 더 쉽게 이해하기 위해, 2-3트리에 대해 먼저 알아보겠습니다. 2-3트리는 이진트리의 확장 버전입니다. 이진트리에서는, 한 노드가 하나의 키값을 가지고 최대 두개의 자식을 가질 수 있었습니다. 하지만 2-3트리에서는 한 노드가 두개의 키값을 가질 수 있고, 세개의 자식을 가질 수 있습니다. 이진트리에서는 leftChild , rightChild 이렇게 두개의 자식이 있었다면 2-3트리에서는 leftChild , midChild , rightChild 이렇게 세개의 자식을 가질 수 있다고 생각하면 됩니다. 2-3트리는 이진 트리와 비교했을 때 무슨 장점이 있을까요?  먼저,데이터 삽입의 예시를 살펴보겠습니다. 1. 데이터를 삽입할 때 키 값이 2개 있는 노드가 일시적으로 3개..

AVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데이터가 마치 연결리스트처럼 한줄로 쭉 나열되는 최악의 경우 트리의 이점을 살리지 못한다는 단점이 있었습니다바로 아래의 그림처럼 말이죠.  이런 일이 발생하지 않기 위해서는 데이터를 추가할 때 한쪽으로 몰리지 않게 조절해주는 기능이 필요합니다. 이것을 가능하게 한 것이 바로 AVL 트리 입니다. 먼저 이진탐색트리의 코드부터 보겠습니다. 이진탐색트리 클래스)연습을 위해 동일한 기능을 하는 함수를 재귀를 사용한 것과 사용하지 않은 것 둘다 구현했습니..