홍시홍의 프로그래밍

이진 탐색 트리란 노드의 왼쪽에는 현 노드보다 작은 값, 오른쪽에는 큰 값이 저장되어 있는 자료 구조 이진 탐색 트리 조건 1. 왼쪽에는 작은 값 2. 오른쪽에는 큰 값 3. 공집합도 포함 삽입 위의 과정으로 위치를 찾아 삽입 삭제 1. 단말 노드일 경우 - 노드 삽입 2. 하나의 자식이 있는 경우, 본인 노드 지우고 자식을 자신의 자리에 3. 노드가 2개 있는 경우 - 오른쪽 서브 트리 중 가장 작은 값을 삽입 시간 복잡도 평균 O(logn) 최악의 경우 한쪽으로 치우친 트리일 경우 O(n)

해싱이란 해시 테이블을 이용한 탐색 기법 이론적으로 O(1)에 탐색가능 해시 함수 : 인덱스를 해시 주소로 바꿔주는 함수 해시 함수 조건 - 충돌이 적어야 한다 - 해시 주소가 고르게 분포되어야한다 - 계산이 빨라야 한다. 제산 함수 일 경우 소수로 나눈다 폴딩 이동 폴딩, 경계 폴딩 탐색키가 문자열일 경우 호너의 방법 사용 해싱은 충돌을 잘 처리해야 한다 충돌이 일어날 경우, 선형 조사법과 체이닝으로 해결 충돌 해결법 2가지 1. 오픈 어드레싱 2. 체이닝 오픈 어드레싱 종류 3가지 1. 선형 조사법 - h(k)+1 ,,,, +2 ,,,,+3 으로 2. 이중 조사법 - 제곱을 더함 h(k) +1^2,2^2,3^2식으로 3. 이중 해싱법 - 해시 2개 사용 - 첫번째 해시 kmod H 두번째 해시 P -..

1. 시간 복잡도 O(n^2) 바깥루프에서 n-1번 안쪽 루프에서 n-i번 2. 구현방법 0->n번째까지 i번재 로 작은 값을 찾아 앞에서 부터 채워준다. 3. 특징 비교 정렬이다 O(n^2)시간 복잡도를 가져 느리다 https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

1. AVL이란 BST의 단점(한쪽으로 치우치는 것)을 보완하기 위해 만들어진 균형 잡힌 이진 트리 각 노드의 BF(벨러스 백터) (왼쪽 서브 노드 높이 - 오른쪽 서브 노드 높이)가 -1,0,1 이 되어야한다. 2. 특징 균형 이진 트리를 유지하기 위해서 LL , RR, LR, RL 4가지의 경우 처리할 방법이 있다 LL은 오른쪽으로 이동 -> 현재 노드의 왼쪽 서브 트리 왼쪽에 삽입이 일어났을 경우 RR은 왼쪽으로 이동 -> 현재 노드의 오른쪽 서브 트리 오른쪽에 삽입이 일어났을 경우 LR 은 왼쪽으로 이동 후 오른쪽 -> 현재 노드의 왼쪽 서브트리 오른쪽에 삽입이 일어났을 경우 RL은 오른쪽으로 이동 후 왼쪽 -> 현재 노드의 오른쪽 서브트리 왼쪽에 삽입이 일어났을 경우 단점 삽입, 삭제가 빈번할 ..