• 균형을 이룬 이진탐색트리에 노드를 삽입하면 그 트리의 균형이 깨질 수도 있는데 재 균형시 다음과 같은 네가지 회전의 있다.(α : 재균형될 노드 )
  1. α 노드의 왼쪽 서브트리의 왼쪽 서브트리에 삽입된다.(LL)(single rotation)
  2. α 노드의 왼쪽 서브트리의 오른쪽 서브트리에 삽입된다.(LR)(double rotation)
  3. α 노드의 오른쪽 서브트리의 오른쪽 서브트리에 삽입된다.(RR)(single rotation)
  4. α 노드의 오른쪽 서브트리의 왼쪽 서브트리에 삽입된다.(RL)(double rotation)

**** 예) 3,2,1,4,5,6,7 의 순서로 비어 있는 AVL 트리에 삽입하는 과정

• Splay 트리
  • 작업한 노드는 무조건 일련의 회전으로 루트로 간다.
  • 필요성 : AVL 트리 균형 조건 검색에 많은 비용이 든다.
  • 회전의 종류 :
    • Zig(단순회전)
    • Zig-Zag(이중회전)
    • Zig-Zig

* 트리의 높이 또는 무게르 균형있게 구축하는 것 - AVL 트리
* 자주 탬색하는 키를 갖는 노드를 트리의 루트에 가깝게 두는 것 - Splay 트리

• Splaying 효과