자료구조 공부 링크

자료구조 1

자료구조 2

인접행렬, 인접리스트

• binary tree
• binary search tree
• b-tree
• b+tree

b, b+ 1
b, b+ 2

스택으로 큐 만들기

• binary search tree 는

다음과 같은 문제가 생겨 삽입,삭제 연산에 최악의 경우 O(logn)을 보장할 수 없다. 따라서 균형 이진 트리로 만들어야 하는데 balanced binary tree를 대입하면 leaf node간 최대 level 차이가 1이 되지만 구현에 많은 비용이 소모된다. 두 마리 토끼를 모두 잡은 것이 red-black tree 이다. red-black tree는 leaf node간 최대 level 차이가 2배 안쪽으로 난다. 따라서 balanced binary tree 보다 구현에 적은 비용이 들면서 삽입,삭제 연산에 O(logn)의 시간 복잡도를 유지할 수 있다.

red-black tree