-
[Algorithm] Pattern Matching
패턴매칭은 우리가 평소에 작업을 할 때 많이 사용한다. 예를 들면 strstr() 함수라던지 vim에서 / 동작, word에서 Ctrl+F 등 많은 utility에서 사용되고 있다. 패턴 매칭을 위해서 많은 loop을 돌아야하기 때문에 시간 복잡도는 O(n*m)이 된다.…
-
[Algorithm] Flexible Array
자동으로 자라는 array 구조를 설명한다. 위 코드처럼 C에선 처음 array size가 내부 값을 초기화하면서 고정된다. 이 크기를 유동성 있게 사용하기 위해선 struct 내부로 넣으면 된다. 위 구조체를 잡아서 크기를 확인해보면 4 bytes만 나오게…
-
간격 트리 (Interval Tree)
Kernel에서도 많이 쓰이는 구조로, key 값으로 특정 하나의 값이 아니라 구간이 들어간다. Interval tree는 OS에서 프로세스 address영역을 관리 할 때 용이하게 쓰인다. 만약 위와 같은 tree 구조가 있을 때, 특정 구간 (예를 들면…
-
증강 트리 (Augmented Tree)
소개 Augmented Tree (증강 트리)는 기존 binary search tree에서 확장된 구조다. Binary search tree에서 이론상 특정 값을 검색 할 때, log2(N)만큼의 시간복잡도를 가지기 때문에 balance만 맞춰져 있다고 하면 빠르게 찾을 수 있다. 그러나…
-
Red-Black Tree 개선된 구조
Red-Black Tree – 삽입 글에서 설명한 것 처럼, RB tree에서 사용하는 구조체의 그림과 코드는 다음과 같다. 위 그림에서 rb_color는 단순하게 color값을 나타내는 값인데, 4 bytes를 가지는 int 타입이다. 따라서 parent의 주소값을 가지는 rb_parent의…
-
Red-Black Tree – 삭제
만약 아래 그림과 같은 RB tree 구조가 존재했을 때, node 1을 삭제하면 다음과 같을 것이다. 위 그림과 같이 됐을 때, tree의 균형은 맞는 것 처럼 보일 수 있지만 실제 균형이 맞지 않는 것이다.…
-
Red-Black Tree – 삽입
일명 RB tree라고 부르는 Red Black Tree는 binary search tree의 종류로 모태가 되는 구조는 B tree다. RB tree는 kernel의 메모리를 찾을 때도 사용되고 scheduling 할 때도 많이 사용된다. 큰 장점은 매 새로운 노드를…
-
Binary Search Tree
일반적인 Tree는 검색용으로 적합하지 않다. 왜냐하면 어떤 값을 tree 구조에 저장 할 때 항상 tree에 노드가 균일하게 배치가 된다는 보장이 없기 때문이다. 이를 위해서 Binary Search Tree 구조는 balance 함수를 통해서 항상 log(2)N의…
-
[Algorithm] Generic Tree
Tree 기본 구조 및 용어 Tree 구조의 특징은 어떤 데이터를 찾고자 할 때 좀 더 빠른 시간 내에 찾을 수 있는 장점을 가진다. 구조는 아래 그림과 같이 root를 기점으로 좌 우 노드와 연결되어…
-
[Algorithm] Generic Hash
Linked List 구조에서 특정 데이터를 찾고자 할 때, head가 가리키는 노드부터 찾을텐데 만약 데이터가 가장 마지막 노드에 있다면 시간복잡도 기준으로 O(N)이 된다. Hash에선 bucket이라는 구조가 사용되는데, hash function을 거쳐 나온 값을 통해서 bucket을…
