BST 기반 자료구조들의 우선순위

 

 

<Performance Analysis of BSTs in System Software> 라는 논문 결과 (2004년 스탠퍼드대 연구)

(논문 링크: https://web.stanford.edu/~blp/papers/libavl.pdf)

Abstract

1. 논문 작성 당시, BST(이진 검색 트리) 기반 자료구조의 선택을 돕는 경험적 연구가 부족함

2. 현실세계의 시나리오를 가정한 후, 해당 환경에서 20가지의 BST 변형 성능을 측정하고 비교함

3. 결론

• 입력이 무작위 순서로 제공되는게 확실할 경우, unbalanced한 일반적인 BST가 우수
• 입력이 무작위 순서로 제공되고 가끔 정렬된 순서가 있는 경우 RB 트리가 우수
• 정렬된 순서로 삽입 후 무작위 접근이 필요할 때는 AVL 트리가 우수
• 삽입 후 순차적 또는 군집된(clustered) 접근에는 splay 트리가 우수

---

 

 

 

응용 사례를 위주로 보자.

 

RB 트리를 공부해야 하는 이유는

리눅스 커널에서 rb 트리가 활용되기 때문이며 (OS 공부의 선행지식)

자바에서 트리맵 뿐만 아니라 트리셋 등을 구현할 때도 rb 트리가 활용되기 때문.

실제로는 rb 트리가 더 자주 쓰인다고 한다. 

 

AVL 트리는

백과사전과 같이 삽입 삭제 등 편집을 어느정도 거친 후에는 검색만 주구장창 하게되는 경우에 주로 쓰인다.