AVL 트리 소개

안녕하세요 오늘은 AVL 트리에 대해 알아보겠습니다.
#day_19

AVL 트리를 사용해야 하는 이유

때때로 이진 탐색 트리의 연산은 편향된 이진 탐색 트리로 인해 O(log n) 대신 O(n)이 됩니다. 이것이 Adelson, Velskii 및 Landis의 이유입니다. 그래서 AVL 트리는 무엇입니까?

이진 검색 트리에 익숙하지 않은 경우 도움이 될 것입니다. :)

AVL 트리의 정의

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

• www.geeksforgeeks.org

시간 및 공간 복잡성

avl 트리의 공간 복잡도는 O(n)입니다.


끼워 넣다
검색
삭제


O(로그 n)
O(로그 n)
O(로그 n)

균형 요인

왼쪽과 오른쪽 하위 트리의 높이 차이는 아래 공식을 사용하여 계산할 수 있습니다.

BalanceFactor = height(left-sutree) − height(right-sutree)

균형 요소가 1, 0 또는 -1이면 트리가 균형을 이루고 그렇지 않은 경우 회전을 사용하여 균형을 맞춥니다. 네 가지 유형의 회전이 있습니다.

오른쪽 회전

왼쪽 회전

오른쪽-왼쪽 회전

좌우 회전

다음 게시물에서 우리는 구현과 함께 회전 유형을 다룰 것입니다. 내일 뵙겠습니다. 좋은 하루 보내세요!

참조 및 유용한 리소스

https://en.wikipedia.org/wiki/AVL_tree

https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm

https://www.javatpoint.com/avl-tree