1. 스레드 이진트리

- 연결리스트로 구현된 이진트리의 경우, 자식이 1개 이하인 노드는 자식을 가리키는 메모리 주솟값이 하나 이상 null을 가리키게 된다. 예를 들어 노드수 n개인 이진트리가 있다 하면 여기서 자식을 가리키는 메모리 주솟값이 2n개가 할당되게 되는데, 그 중 절반이 null을 가리키게 된다. 스레드 이진트리는 이처럼 null을 가리켜야 할 메모리 주솟값에 그 노드의 중위선행자/후속자(그 트리를 중위순회했을 때 그 노드의 선행자/후속자)를 가리키게 한 이진트리로서, 이러한 자료구조를 사용할 경우 여러 알고리즘에서 메모리 공간을 절약할 수 있다. (예를 들어, 스레드 이진트리의 중위순회는 추가적인 메모리를 필요로 하지 않는다.)

- 스레드 이진트리를 구현하는 경우 다음을 고려해야 한다.

(1) 현재 가리키고 있는 노드가 중위선행/후속자인지 자식노드인지 판별하는 스위치를 구현해야 한다.

(2) 자식노드, 중위선행/후속자 모두 없는 경우에는 그 메모리 주솟값이 루트를 가리키게 해야 한다.

2. AVL 트리

- 이를 고안한 Georgy Adelson-Velsky와 Evgenii Landis의 이름을 딴 트리로, 트리를 구성하는 모든 노드의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이 차이가 0 또는 1이 되도록 한 이진탐색트리의 한 종류다.

- AVL 트리 구현 시, 삽입/삭제 연산을 해서 정의를 벗어날 경우 높이를 조정해주는 연산(‘회전 연산‘)을 수행해야 한다. 삽입/삭제가 일어난 말단 위치에서부터 시작해서 바로 위 부모노드로 하나씩 위로 올라가며 트리 균형 여부를 탐색하고 불균형하면 ‘회전 연산’을 수행하는데, 이 작업은 최악의 경우 트리 높이만큼 수행하게 된다.

- 일반적인 이진탐색트리는 삽입/삭제되는 데이터의 구성에 따라 검색시간이 최악의 경우 O(n) 가까이 걸리기도 한다. AVL트리는 비교적 트리가 균형적으로 만들어져 검색/삽입/삭제에 걸리는 시간이 O(logn)이 보장된다는 장점이 있다. 그러나 삽입/삭제 시 회전 연산으로 인해 추가되는 작업 횟수가 있다는 점 때문에 이 점에서 이점이 있는 레드블랙트리 같은 다른 균형 이진탐색트리들이 더 많이 쓰인다.

3. 상향식 스플레이 트리

- BST의 일종으로, 요청에 따라 어떤 노드를 찾았을 때 그 노드를 다시 찾을 가능성이 높다고 보고 그 노드를 루트까지 끌어올리는 연산 (‘스플레이 연산’이라 한다) 을 탐색/삽입/삭제 때마다 하는 트리를 말한다. 상향식 스플레이 트리는 실제로 입력으로 같은 노드값이 반복해서 들어오는 경우에 높은 효율을 보인다는 장점이 있다.