Dot Algo∙ DS/알고리즘 개념
2022. 1. 17.
[알고리즘] 균형잡힌 이진 검색 트리 Balanced BST - 트립(Treap) (Java)
균형잡힌 이진 검색 트리 (Balanced Binary Search Tree) 표준 라이브러리의 이진 검색 트리는 대부분 X보다 작은 원소의 수를 계산하거나 k번째 원소를 찾는 연산을 지원하지 않기 때문에 이진 검색 트리를 직접 구현해야 할 경우가 종종 있다. 단순한 이진 검색 트리는 특정 형태의 입력에 대해 편향트리와 같은 연결 리스트가 되어 버리는 문제가 있기 때문에, 균형잡힌 이진 검색 트리를 구현해야 한다. AVL 트리나 레드 블랙 트리 등 교과서에 실리는 대부분의 균형잡힌 이진 검색 트리들은 구현이 매우 까다롭다. 다양한 경우의 수를 따져서 구현해야 하기 때문에 코드도 길고, 한정된 시간 안에 코드를 작성해야 하는 프로그래밍 대회에서 사용하기엔 부적합하다. 따라서 대회에서는 구현이 간단한 트립(..
![[알고리즘] 균형잡힌 이진 검색 트리 Balanced BST - 트립(Treap) (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/bzqakr/btrqTZWaRBT/fmP66pbCOx7veaOeeZAYY1/img.png)