250505 8일차

트리
특징
비선형 자료구조, 계층 구조형 (부모-자식)
1개의 루트, 0개이상의 자식, 사이클 없음
삽입/삭제 균형트리 기준 O(logN) -> 레벨

전위순회 루트-> 왼쪽-> 오른쪽
중위순회 왼쪽-> 루트-> 오른쪽 //BST에서 오름차순 정렬
후위순회 왼쪽-> 오른쪽-> 루트

BFS 너비우선 탐색
-가까운노드부터
-큐
-최단거리

DFS 깊이우선 탐색
-깊이우선 (미로 한쪽벽)
-스택
-백트래킹

종류
이진트리 : 자식이 최대 2개인 트리
이진탐색트리 (BST) : 왼쪽노드 < 부모 < 오른쪽 (정렬된트리)
힙 : 최대 or 최소값이 루트 (힙정렬할때 쓰던)
균형트리 - AVL, 레드블랙 
트라이 - 문자열 검색용 트리

 

해시테이블
key값을 index에 매핑 하는 자료구조 (버킷)
해시충돌 해결방식
체이닝 - 각 버킷 연결리스트 삽입삭제 빠름
오픈어드레싱 - 충돌시 주소결정함수로 빈슬롯 탐색, 클러스터링 발생(자료 몰리는현상)
평균 O(1) 삽입,삭제,검색
충돌시 최악 O(n)

여기서 자료구조 1권을 마무리했는데,
내용이 좀 부족하거나 설명이 끊기거나,
핵심 내용들이 빠진느낌이 있다.. 2회독은 안할예정

<윤성우자료구조>
이 책은 좀 세세한 부분도 있긴했지만,
아무래도 어느 정도 코딩의 실력이나 용어를 안다는 전제에
설명하기에 이해하기 어려운 부분도 있다.
리스트까지 빠르게 훑어보았다.

ADT 추상 자료형
adt는 인터페이스만 정의된 자료구조
같은 자료구조(스택,큐,...)라도 프로그래밍 언어, 라이브러리에 따라 다르다.
각 차이점, 장단점 알아보기

리스트-챕터
더미노드 사용에 대한 자세한 설명이 있었다
조건 분기 줄이고 코드 일관성 증가
삽입삭제의 로직 단순화가 되는부분이었다.

추가적으로 해시테이블에 대해서 알아보았다
Key에 해당하는 index에 바로 접근할수 있으므로 평균 O(1)의 시간복잡도를 가지고 데이터를 삽입,삭제,검색 할 수 있음.
체이닝의 경우 겹침(충돌) 발생시 리스트로 관리, 삽입은 O(1)유지, 삭제, 검색은 최악 O(n)

버킷수 8일때  증가패턴 12일때의 예시
대부분의 짝수가 클러스터링 현상이 발생하였다
주소결정함수가 %버킷수 연산을 한다면 버킷수를 소수로하는게 중요하다.
소수로 쓰는이유는 최대공약수에 걸리지 않아 특정 패턴에도 균일 하게 분포되기 때문
여기서 해시함수는 입력한 Key값을 특별한 해시값 1239932498등 큰 정수로 만드는것
주소결정함수는 해시값을 버킷 배열 인덱스로 변환하는것 
C++에서는 내부적으로 마스킹이 되어있고 버킷수는 8, 64, 512 이후 2배씩 증가한다.

 

오늘은 약간 휴식중점 학습으로 진행하였다.