avl 트리 예제

  • 0

avl 트리 예제

Category : Senza categoria

삽입은 서브 트리 중 하나의 높이를 1로 증가시켰습니다. 하위 트리의 높이 = h+3이 있을 때 트리의 나머지 부분의 균형이 조정되었기 때문에 하위 트리의 높이 = h+3이 여전히 있기 때문에 트리의 나머지 부분의 균형이 유지됩니다!!! 왜 AVL 나무? 대부분의 BST 작업(예: 검색, 최대, 최소, 삽입, delete.등)은 h가 BST의 높이인 O(h) 시간을 취합니다. 이러한 작업의 비용은 기울어진 이진 트리의 O(n)가 될 수 있습니다. 모든 삽입 및 삭제 후 트리의 높이가 O(Logn)로 유지되도록 하면 이러한 모든 작업에 대해 O(Logn)의 상한을 보장할 수 있습니다. AVL 트리의 높이는 항상 O(Logn)이며 n은 트리의 노드 수입니다(이 비디오 강의에서 증명). 자체의 균형을 맞추기 위해 AVL 트리는 다음과 같은 네 가지 회전을 수행 할 수 있습니다 – 바이너리 검색 트리 (작은 키와 왼쪽 하위 트리와 큰 키오른쪽 하위 트리)의 속성을 보존하기 위해, 우리는 노드 x에 하위 트리 T0, T1, T2 및 T3를 연결해야합니다 , y와 z 다음과 같이 : 자신의 발명가 아델슨, 벨스키와 랜디스의 이름을 따서 명명, AVL 나무는 이진 검색 트리의 높이 균형입니다. AVL 트리는 왼쪽 및 오른쪽 하위 트리의 높이를 확인하고 차이가 1을 초과하지 않음을 보장합니다. 이러한 차이를 균형 계수라고 합니다. 노드가 오른쪽 하위 트리의 오른쪽 하위 트리에 삽입 될 때 트리가 불균형하게되면, 우리는 하나의 왼쪽 회전을 수행 – 트리가 w의 삽입 전에 균형이었기 때문에, 우리는 있다 : 처음 두 회전은 단일 회전과 다음 두 로입니다 tations는 이중 회전입니다. 불균형 트리를 얻으려면 적어도 높이 2의 트리가 필요합니다.

이 간단한 트리를 통해 하나씩 이해해 봅시다. 삽입된 노드(46)에서 시작하여 트리를 트래버스하여 첫 번째 불균형 노드를 찾습니다: BST 연산과 마찬가지로 AVL 트리에서 일반적으로 수행되는 연산은 위에서 언급한 4가지 경우에서 수행되어야 하는 작업입니다. 모든 경우에 z로 뿌리된 하위 트리의 균형을 다시 조정하기만 하면 되고 z로 루팅된 하위 트리의 높이(적절한 회전 후)가 삽입 전과 동일하게 됨에 따라 전체 트리의 균형이 조정됩니다. (이 비디오 강의에서 증명을 참조하세요) 답변: 트라이 노드 재구성 작업 후 하위 트리의 루트 노드 높이가 원래 트리와 같기 때문에 예!!! 시간 복잡성: 몇 개의 포인터만 변경되기 때문에 회전 작업(왼쪽 및 오른쪽 회전)은 일정한 시간이 소요됩니다.