hye0.log hye0.log

AVL 트리

• [알고리즘] AVL 트리

  Computer Science/Algorithm 2021. 10. 24. 03:26

  AVL 트리 러시아의 수학자 Adelson - Velskii 와 Landis가 고안한 높이 균형 이진 탐색 트리 오른쪽 서브트리와 왼쪽 서브트리의 높이 차가 2이상이 되면 회전을 통해 트리의 높이 차를 1이하로 유지 높이차 = 오른쪽 서브트리의 높이 - 왼쪽 서브트리의 높이 이진 탐색 트리를 기반으로 하기 때문에 삽입 시엔 이진 트리 처럼 노드를 삽입한다. AVL 트리의 높이 차 AVL 트리에선 노드 삽입 시, 회전이 필요한 경우 2가지가 있습니다. 경우 1: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 1자인 경우 -> 단일 회전 단일 회전: 가운데 숫자가 위로 올라가면서, ㅅ자 모양으로 회전 경우 2: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 >, 이중 회전 이중 회..

  Read More