본문 바로가기
반응형

자료구조 & 알고리즘/자료구조7

Map과 Set이란(Hash, Tree 기반 자료형 비교) Map맵은 비선형 자료구조로 key-value 쌍으로 데이터를 저장하는 특징을 갖고 있다.맵의 key는 중복이 허용되지 않으나, value는 중복이 허용된다.자바의 맵 자료형에는 대표적으로 HashMap과 TreeMap이 존재한다.HashMap은 해시테이블 기반으로 자료를 관리하기에 조회, 삽입, 삭제 연산에 O(1)의 시간복잡도를 갖는다.TreeMap은 균형 이진탐색트리의 한 종류인 레드블랙 트리를 통해 데이터를 관리하기에 조회, 삽입, 삭제 연산에 O(logN)의 시간복잡도를 갖는다. Set셋은 비선형 자료구조로 중복이 허용되지 않는다.중복을 허용하지 않는 집합과 같은 개념이다.자바의 셋에는 HashSet, TreeSet이 존재한다.HashSet은 해시테이블 기반으로 자료를 관리하기에 조회, 삽입, .. 2025. 6. 12.
이진트리와 Balanced트리의 비교 (mysql innoDB는 왜 Balanced 트리를 사용할까?) Q. Mysql InnoDB는 왜 이진트리가 아닌 Balanced Tree를 사용할까??Q. 자바의 Tree 자료타입은 왜 Balanced Tree가 아닌 균형이진탐색 트리인 RB 트리를 사용할까?? 이진트리를 학습하며 나는 위와 같은 궁금증이 생겼다.따라서 나는 이진트리, 이진탐색트리, 완전이진트리와 mysql innoDB의 balanced tree를 비교하며 어떠한 기준으로 자료구조가 선택됬는지 알아보았다. 내가 알아본 기준은 아래와 같다.[InnoDB에서 Balanced-Tree 사용하는 이유]균형 유지Fan-Out에 따른 탐색 횟수범위 검색[자바의 Tree 타입이 균형이진탐색 트리 사용하는 이유]메모리와 디스크의 차이단순한 구조와 쉬운 구현 균형유지우선 이진트리나 이진탐색트리와 Balanced-T.. 2025. 5. 30.
레드블랙트리 레드블랙트리Red-Black Tree는 이진 탐색 트리의 한 종류로, 편향된 트리구조가 나올 수 있는 이진탐색트리를 균형을 유지하도록 하여 시간복잡도가 평균 O(logN)을 유지하도록 한 트리이다. 지난 포스팅에서 균형 이진탐색트리 중의 하나인 AVL 트리를 다루었다.AVL 트리와 비슷하게 회전연산을 사용하지만 컬러링이라는 새로운 개념이 존재하고,BF 기준으로 엄격하게 균형을 유지했던 AVL 트리에 비해 비교적 느슨한 규칙으로 균형을 유지하는 특성이 있다. AVL 트리에 비해 비교적 느스한 기준으로 인해 균형을 잡기 위해 수행하는 연산의 수가 적어 상대적으로 성능 또한 빠르다는 특징이 있어, 실무에서 가장 많이 사용되는 트리이며 자바의 TreeMap이나 TreeSet에서 사용되는 자료구조이다. 레드블랙.. 2025. 5. 30.
이진탐색트리 - AVL 트리 AVL 트리AVL 트리는 이진탐색트리의 한 종류로편향된 트리구조가 나올 수 있는 이진탐색트리를 균형을 유지하도록 하여 시간복잡도가 평균 O(logN)을 유지하도록 한 트리이다. AVL 트리는 균형을 유지하기 위해 회전연산을 수행한다.LL 회전, RR 회전, LR 회전, RL 회전이라고 불리우는데, 회전 연산의 핵심 원리는 중간 값이 루트 노드가 된다는 것이다.LL, RR 등등은 노드의 왼쪽, 오른쪽 위치로 인해 붙여진 이름의 차이일 뿐,원리는 모두 할아버지, 부모, 자식이 있을 때, 중간 값이 루트가 되고 나머지 두 노드는 크기에 따라 왼쪽, 오른쪽에 위치하게 된다. BF(Balanced Factor, 균형인수)균형인수(BK) = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이균형인수는 AVL 트리가 트.. 2025. 5. 30.
반응형

티스토리툴바