자료구조
1.[C] 레드블랙트리(red-black tree)
자가 균형 이진 탐색 트리대표적으로는 연관 배열 등을 구현하는데 쓰이는 자료구조이다. RB tree는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다.모든 노드는 빨간색 혹은 검은색이다.루트 노드는 검은
2.[C] 구조체, 포인터
복잡한 객체에는 다양한 타입의 데이터들이 한데 묶여져서 있다.배열(array): 타입이 같은 데이터의 모임구조체(structure): 타입이 다른 데이터를 묶는 방법\*C언어에서는 struct 키워드를 이용하여 표기구조체의 형식이 위와 같이 정의되었다면 구조체 변수는
3.[C] 연결 리스트 (Linked List)
연결리스트(Linked List) 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 연결리스트의 각 노드는 다음 노드를 가리키는 포인터를 포함한다. 다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있다.
4.[C] RB tree 구현하기 - (1) 회전
레드블랙 트리는 루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써 그러한 경로 중 어떠한 것도 다른 것보다 두 배 이 상 길지 않음을 보장하게 되는데, 이로써 트리는 근사적으로 균형을 이룬 트리가 된다.트리는 각 노드의 color, key, left, ri
5.[C] RB tree 구현하기 - (2) 삽입 (insert, insert_fixup)
삽입 n개의 노드로 이루어진 레드-블랙 트리에서 노드 하나를 삽입하는 것은 O(logn) 시간에 수행될 수 있다. 보통의 이진 탐색 트리처럼 노드 z를 트리 t에 삽입한 뒤 z를 적색으로 칠한다. (왜 흑색이 아닌 적색으로 칠할까?.. -> 고민해보기) RB tree
6.[C] RB tree 구현하기 - (3) 삭제 (delete, delete_fixup)
삭제를 구현하기 전에 rbtree 특성을 다시 한번 짚어보자모든 노드는 빨간색 혹은 검은색이다.루트 노드는 검은색이다.모든 리프 노드(NIL)들은 검은색이다.\*NIL: null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드빨간색 노드의 자식은 검은색이다.==