2
일부 노드의 왼쪽 및 오른쪽 자식의 높이가 2라는 점이 다릅니다.AVL 트리 - 일부 노드의 왼쪽 및 오른쪽 자식의 높이가 1만큼 다를 수있는 이유는 무엇입니까?
이것은 AVL 트리와의 첫 만남이며, 필자는 그것이 왜 필요한지 이해할 수없는 것 같습니다.
2 살이되면 아이들이 어째서 잘못 되었습니까?
감사 AVL 트리의 개념이다
A
답변
3
하고, 검색 0 (logn)를 만들 정의에 따르면 균형 이진 트리는 하나만 다를 수 있습니다. AVL 트리에서 작동하는 알고리즘을 살펴보면이 속성이 항상 유지된다는 것을 알 수 있습니다.
높이가 +2만큼 다른 데이터 구조를 만드는 것이 가능하지만 그렇게하는 것이 실제 이익이 아닙니다. + - 1로두면 더 단순하고 자체 균형이 잡힌 데이터 구조가 생성됩니다.
+2
+ -1 불변 값을 사용하지 않고 다른 유용한 종류의 데이터 구조를 만들 수도 있지만 더 이상 AVL 트리가 아닙니다. – Vlad
+0
@Oleksi : 만약 당신이 올바르게 이해한다면, 그 차이가 + -2 이상이된다면, 요소를 찾거나 삽입/삭제할 때'O (n)'이 걸릴 것입니까? – ron
+0
@ron 아니요. 일정한 차이가 있기 때문에 아직 O (log (n))에서 수행 할 수는 없지만 왜 이것을 + - 2로 만들겠습니까? 더 빨라진 것은 아니지만 알고리즘이 좀 더 복잡해집니다. 실제로, 그것들은 약간 느릴 것입니다 (그러나 여전히 점근 적으로 O (log (n)). 당신은 기본적으로 AVL 트리를 더 이상 사용하지 않습니다. – Oleksi
2
음을, 왼쪽 및 오른쪽 차일의 높이가 최대 하나의 차이는 안된다. AVL 트리에서 위키 백과
에서
, 모든 노드 의 두 개의 하위 서브 트리의 높이가 최대 하나의 차이.
는 균형 잡힌 이래로이 모든 요소가 왼쪽에있을 수있는 비 균형 이진 트리,보다 빠르게, 그래서이 0 (N)
관련 문제
- 1. AVL 트리 노드의 균형 요소 업데이트
- 2. 분석 AVL 트리
- 3. C++ AVL 트리 구현
- 4. 및 증가를 AVL 트리, 순서
- 5. GraphViz 이진 트리 왼쪽 및 오른쪽 자식
- 6. AVL 트리 삽입 질문
- 7. python AVL 트리 삽입
- 8. AVL 트리의 노드 밸런스 요소
- 9. AVL 트리 로테이션 효율
- 10. C++ 트리 AVL 저울
- 11. 왼쪽 및 오른쪽 속성
- 12. AVL 트리 구현
- 13. Avl 트리 삭제에서 더 높은 우선 순위를 가진 하위 트리
- 14. n AVL 트리 합치기
- 15. TableLayout 왼쪽 및 오른쪽
- 16. TableViewCell의 높이가 다를 수 있습니까?
- 17. AVL 트리 - 수동 그리기 및 인쇄
- 18. 왼쪽 및 오른쪽 서브 브랜치 깊이를 계산하는 데 도움이 필요합니다.
- 19. avl 트리 도움말 사전 구현
- 20. 이진 트리 (AVL)의 밸런싱
- 21. 자체 균형 조정 avl 트리
- 22. 테이블 행의 국경 문제는 일부 패딩이나 마진 (왼쪽 및 오른쪽)
- 23. 트리 노드의 포리스트 C++?
- 24. 왼쪽 오른쪽 열 div
- 25. 왼쪽 및 오른쪽 열 문제
- 26. 왼쪽 및 오른쪽 방향으로 UIViewAnimationTransitionCurl
- 27. 이진 트리 높이가 정확합니까?
- 28. 셀에 왼쪽 및 오른쪽 정렬 텍스트가있는 JTree?
- 29. avl 트리에서 노드의 균형 요소 계산
- 30. AVL 트리에서 차 순회
그렇기 때문에 불균형이 무효화되어 추가 삽입 및 삭제에 쓸모가 없습니다. –
"균형 잡힌"대 "불균형"을 정의하는 임의의 방법을 찾아야합니다. 그들이 불균형을> 0으로 정의했다면 균형을 잡는데 더 많은 시간을 할애 할 것입니다.> 2로 만들면 더 긴 룩업 비용으로 끝날 것입니다. AVL 트리는 빠른 검색을 위해 설계되었으므로> 2로 설정하면 도움이되지 않습니다. – Justin