무작위 이진 탐색 트리 편집하기 (부분)

==주요 종류==
*[[트립 이진 탐색 트리|트립]]
**노드에 무작위 우선순위를 부여하여 힙 + BST 구조 유지
**삽입, 삭제 연산은 회전을 통해 힙 속성을 보존하면서 이루어짐

*Randomized Binary Search Tree (RBST)
**새 노드를 루트로 삽입할 확률을 1 / (n + 1)로 설정
**루트로 삽입 시 기존 트리를 좌우로 분할(split), 새 노드 아래로 병합(join)
**단순하고 효율적인 구현으로 유명

*Skip List 기반 트리 (예: Skip Tree)
**여러 층의 연결 리스트로 구성된 구조를 트리처럼 응용
**탐색, 삽입, 삭제 시 각 노드의 높이를 무작위로 결정

*Scapegoat Tree (부분 무작위)
**노드 삽입 시 불균형이 감지될 때만 부분적으로 트리 재구성
**무작위는 직접 사용하지 않지만, 삽입 순서가 무작위일 때 성능이 안정적

*Treap 변형
**Cartesian Tree: 배열을 기반으로 Treap과 유사한 트리 구성
**Implicit Treap: 키 대신 배열 인덱스를 기반으로 Treap 구성

*Randomized Meldable Heap 기반 BST
**트리를 명시적인 구조 없이 포인터만으로 표현하며 병합(meld) 연산으로 유지
**병합 시 무작위 결정에 따라 왼쪽/오른쪽 서브트리를 선택