자료구조
-
[자료구조] B-tree 알아보기자료구조 2025. 1. 29. 21:24
B-tree 알아보기이진탐색트리(BST)-각 노드는 최대 2개의 자녀 노드를 가진다.-모든 노드의 왼쪽 서브 트리는 부모보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 부모보다 큰 값을 가진다.-삽입,검색,삭제의 평균적인 시간복잡도: O(logN)-하지만 편향된 트리가되면 최악의 경우 O(N)까지 떨어질 수 있다 이진 탐색트리의 문제점-깊이가 깊어지면 검색, 삽입성능이 떨어진다.-균형유지가 어렵다. 자녀노드를 더 많이 갖기위해서는 어떻게 해야하는가?-> 상위 노드에 더 많은 키값을 가지면 된다.예를들어 자녀 노드를 3개씩 갖기위해서는 부모 노드에 2개의 키값을 가져야한다. 2개의 키 값이 있다면 3가지 값의 범위를 만들어 낼 수 있기 때문. ( k2)왼쪽자식: 작은 키값보다 작은값중간자식:..
-
[자료구조] 배열, 연속리스트, 연결리스트 차이자료구조 2024. 6. 26. 21:26
1. 배열 고정된 크기의 연속된 메모리공간에 동일한 크기와 타입의 자료를 저장한다 특징:요소들은 동일한 타입을 가진다크기가 고정되어있고, 변경불가능하다중간 자료가 삭제되면 null값이 들어간다(밀도 != 1) 인덱스 통한 검색 시: ( 시간복잡도: O(1) ) 장점:빠른 인덱스접근이 가능하다메모리 사용효율적이다(연속된 메모리공간) 단점:크기변경이 불가능하다 2.연속 리스트배열과 유사하게 연속된 공간에 자료를 저장하지만 크기 조절이 가능하다 특징:크기조정시, 기존데이터를 옮기는 작업이 필요하다 중간자료가 삭제되면 뒤의 자료들을 앞으로 땡겨온다 (밀도=1 )인덱스 통한 검색시 : O(1)삽입, 삭제시 : O(n) 장점:연속된 메모리공간에 저장되어 빠른접근이가능하다 크기 조절이 가능하다 단점:삽입,..