자료구조와 알고리즘

: 하나 또는 여러개의 키를 조건으로 데이터 집합에서 원하는 값을 찾아내는 것선형 검색 : 무작위 데이터 집합에서 검색이진검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서의 빠른 검색해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서의 빠른 검색정의 : 직선(선형

: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 (깊게) 탐색하는 방법스택 자료구조 사용 (or 재귀함수)모든 노드 방문하고자 할때 이 방법 선택자기 자신을 호출하는 순환 알고리즘 의 형태방문처리 : 어

레드 블랙 트리 (Red-Black Tree) 이진 탐색 트리(BST)의 한 종류 스스로 균형(balancing) 잡는 트리 O(logN) BST 의 worst case의 단점을 개선 한쪽으로 편향되어있는 상태의 삽입 삭제 검색의 시작 복잡도 O(N) = 모든

삽입 전 RB 트리 속성을 만족한 상태일반적인 BST의 삽입 방식과 동일삽입 후 RB 트리 위반 여부 확인RB 트리 속성을 위반했다면 재조정RB 트리 속성을 다시 만족레드 블랙트리의 속성 복습하기!루트 노드는 Black⭐ 4. Red 의 자녀들은 Black ( =

레드 블랙트리의 속성 복습하기!루트 노드는 Black Red 의 자녀들은 Black ( = Red 는 연속적으로 존재할 수 없다 )임의의 노드에서 자손 nill 노드들까지 가는 경로들의 Black 수는 같다 ( 자기 자신은 카운트에서 제외 )삭제 전 RB 트리 속성