collections.rbtree

2004년 여름쯤에 파이썬 2.4가 릴리스되기 전에 collections 모듈에
타입이 1개 밖에 없는데 이름이 복수로 붙어서, 피보나치 힙을
넣자는 얘기가 있을 때 한 3주일 고민을 해서 피보나치 힙을 구현
했었습니다. 그런데, 피보나치 힙이 워낙 괴짜스러운 자료구조라서 복잡하고
편리한 것들을 추가하기에는 영 불편해서 결국은 그냥 중단했었습니다.

올해 초에는, 피보나치힙과 비슷한 용도에 사용할 수 있지만,
바이너리 트리의 특징을 유지하고 있기 때문에, 구현이 훨씬 쉬운
레드블랙 트리를 한번 구현을 해 볼까 생각을 했었습니다. 그런데~ 훈련소
다녀오고 나니까 머리가 안 돌아가서.. 이히히 ^_^;;
결국은 한참을 벼르던 레드블랙 트리 구현을 마침 숙제하기가
너무 귀찮기도 하고 파이썬 2.5도 곧 피쳐프리즈가 되지 않을까 해서 밀어넣어보려고 한번 집중해서 구현해 봤습니다. 기본적으로
제공되는 메쏘드는

• T.insert(v): 값을 트리에 넣음
• T.remove(v): 값을 트리에서 뺌
• T.clear(): 트리를 비움
• T.has_key(k): 키가 있는지 검사
• T.values(): 값의 리스트를 리턴
• T.keys(): 키의 리스트를 리턴
• T.items(): (키, 값) 페어의 리스트를 리턴
• T.nfirst(n): 작은 값부터 순서대로 n개를 리턴
• T.nfirstitems(n): 작은 값부터 순서대로 n개를 (키, 값) 페어의 리스트로 리턴
• T.nlast(n): 큰 값부터 순서대로 n개를 리턴
• T.nlastitems(n): 큰 값부터 순서대로 n개를 (키, 값) 페어의 리스트로 리턴
• T.popleft(v): v보다 작은 값을 모두 빼내고 리스트로 리턴
• T.popleftitems(n): v보다 작은 값을 모두 빼내서 (키, 값) 페어의 리스트로 리턴
• T.popright(v): v보다 큰 값을 모두 빼내고 리스트로 리턴
• T.poprightitems(n): v보다 큰 값을 모두 빼내서 (키, 값) 페어의 리스트로 리턴
• 그 외에 __setitem__, __getitem__, __len__, __contains__ 이 지원됩니다.

아무래도 레드블랙트리나 피보나치힙류는 세션 테이블같이 정렬 순서에 따라서 빠르게 작업을 해야 하는 경우에 프리어러티 큐로 활용하는 것이 가장 대표적인 용례인데, 피보나치힙으로 구현을 한다면 순위를 뽑으려고 할 때 매번 extractmin을 해야하는 반면에, 레드블랙트리는 그냥 트리에서 돌아다니는 것으로 구할 수 있다는 것이 장점이라고 할 수 있겠습니다. (속도는 완전한 C 타입으로 구현하면 피보나치힙이 훨씬 빠르지만, 파이썬의 비교연산 특성상 파이썬 확장 모듈이 되면 별 차이가 안 납니다.)

소스는 오픈룩 trac 작업실안에도 있고, 소스포지 패치 리뷰 트래커에 Patch #1324770으로 올렸습니다. 이히히. 잘 돼서 파이썬 2.5에 들어가면 좋겠군요.