균형 이진 트리와 이진 정렬 트리의 관계

균형 이진 트리와 이진 정렬 트리 사이에는 직접적인 관계가 없지만 이진 정렬 트리의 검색 효율성은 이진 트리의 모양과 관련이 있습니다. 따라서 이진 정렬 트리의 모양을 균일하게 만들고 싶을 때는 다음과 같습니다. 이진 트리를 균형 이진 트리라고 합니다.

1. 이진 정렬 트리

이진 정렬 트리(이진 정렬 트리), 이진 검색 트리(이진 검색 트리)라고도 함, 이포크라고도 함 검색 트리 .

• 이진 정렬 트리 정의:

이진 정렬 트리는 빈 트리이거나 다음 속성을 가진 이진 트리입니다.

1. 왼쪽 하위 트리가 비어 있지 않으면 모든 왼쪽 하위 트리 값 ​​노드의 값이 모두 해당 루트 노드의 값보다 작습니다.
2. 오른쪽 하위 트리가 비어 있지 않으면 오른쪽 하위 트리의 모든 노드 값이 루트 노드의 값보다 큽니다. 왼쪽 및 오른쪽 하위 트리도 각각 두 개로 정렬된 트리입니다.
3. 아래 그림과 같이 이진 정렬 트리입니다.

이진 정렬 트리에서 순차 순회를 수행하면 키워드별로 순차 정렬을 수행할 수 있습니다. 위 그림에서 순회는 10, 42, 45, 55, 58, 63, 67, 70, 83, 90, 98

이진 정렬 트리 검색 분석
을 얻을 수 있습니다. 검색의 평균 시간 성능 즉, 이진 정렬 트리에서의 검색은 이진 검색과 유사하지만 테이블의 순서를 유지한다는 측면에서 이동이 필요하지 않기 때문에 이진 정렬 트리가 더 효율적입니다. 삽입 및 삭제 작업을 완료하려면 노드만 수정하면 됩니다.

이진 정렬 트리 검색 최악의 경우 필요한 검색 시간은

트리의 깊이

에 따라 달라집니다.

1. 이진 정렬 트리가 전체 이진 트리에 가까울 때 그 깊이는 $log_ 2n$ 아래 검색 시간 $n{}_{\mathrm{단일\; 가지\; 트리}}So$2. 균형 잡힌 이진 트리

위 내용은 균형 이진 트리와 이진 정렬 트리의 관계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!