logo

TechCodeview

AVL 트리 데이터 구조

안 AVL 트리 자기 균형으로 정의 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이를 균형 요소 노드의.

int를 문자열 java로 변환하는 방법

AVL 트리의 이름은 이를 발명한 Georgy Adelson-Velsky와 Evgenii Landis가 1962년 논문 An Algorithm for the Organisation of Information에서 발표한 이름을 따서 명명되었습니다.

AVL 트리의 예:

AVL 트리

AVL 트리



위 트리는 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 1보다 작거나 같기 때문에 AVL입니다.

AVL 트리 작업:

AVL 트리에서 하위 트리 회전:

AVL 트리는 균형을 유지하기 위해 다음 네 가지 방법 중 하나로 회전할 수 있습니다.

왼쪽 회전 :

오른쪽 하위 트리의 오른쪽 하위 트리에 노드가 추가될 때 트리의 균형이 깨지면 단일 왼쪽 회전을 수행합니다.

AVL 트리의 왼쪽 회전

오른쪽 회전 :

리눅스 어떤 명령

왼쪽 하위 트리의 왼쪽 하위 트리에 노드가 추가되면 AVL 트리의 균형이 깨질 수 있으므로 단일 오른쪽 회전을 수행합니다.

avl-트리

AVL 트리의 오른쪽 회전

좌우 회전 :

좌우 회전은 오른쪽 회전이 실행된 후 첫 번째 왼쪽 회전이 발생하는 조합입니다.

AVL 트리의 왼쪽-오른쪽 회전

오른쪽-왼쪽 회전 :

좌우 회전은 왼쪽 회전이 실행된 후 첫 번째 오른쪽 회전이 발생하는 조합입니다.

AVL 트리의 오른쪽-왼쪽 회전

AVL 트리의 응용:

  1. 데이터베이스의 거대한 레코드를 색인화하고 효율적으로 검색하는 데 사용됩니다.
  2. 세트 및 사전을 포함한 모든 유형의 메모리 내 컬렉션에 대해 AVL 트리가 사용됩니다.
  3. 삽입과 삭제가 덜 일반적이지만 빈번한 데이터 조회가 필요한 데이터베이스 애플리케이션
  4. 최적화된 검색이 필요한 소프트웨어입니다.
  5. 기업 영역과 스토리라인 게임에 적용됩니다.

AVL 트리의 장점:

  1. AVL 트리는 스스로 균형을 유지할 수 있습니다.
  2. 확실히 비뚤어진 것은 아닙니다.
  3. Red-Black Tree보다 빠른 조회를 제공합니다.
  4. 이진 트리와 같은 다른 트리에 비해 검색 시간 복잡도가 더 높습니다.
  5. 높이는 log(N)을 초과할 수 없습니다. 여기서 N은 트리의 총 노드 수입니다.

AVL 트리의 단점:

  1. 구현하기가 어렵습니다.
  2. 일부 작업에는 높은 상수 요소가 있습니다.
  3. Red-Black 나무에 비해 덜 사용됩니다.
  4. 다소 엄격한 균형으로 인해 AVL 트리는 더 많은 회전이 수행될수록 복잡한 삽입 및 제거 작업을 제공합니다.
  5. 균형을 맞추려면 더 많은 처리가 필요합니다.

관련 기사:

캣 timpf 몸무게는 얼마야?