이진 정렬 트리의 평균 검색 길이

이진 정렬 트리의 평균 검색 길이는 ASL = ∑(이 레이어의 높이 * 이 레이어의 요소 노드 수) / 총 노드 수입니다.

이진 검색 트리라고도 알려진 이진 정렬 트리입니다.

차선의 이진 트리와 달리 이진 정렬 트리는 동적 트리 테이블입니다. 그 특징은 트리 구조가 보통 한꺼번에 생성되지 않고, 검색 과정에서 주어진 값과 같은 키를 가진 노드가 트리에 없을 때 삽입된다는 점이다. 새로 삽입된 노드는 새로 추가된 리프 노드여야 하며, 검색 실패 시 검색 경로에서 마지막으로 방문한 노드의 왼쪽 자식 노드 또는 오른쪽 자식 노드여야 합니다.

이진 정렬 트리 관련 용어:

1. 루트 노드: 루트 노드는 트리에 최대 하나의 루트 노드가 있는 노드입니다.

2. 엣지: 엣지는 상위 노드에서 하위 노드로의 링크를 나타냅니다.

3. 리프 노드: 자식 노드가 없는 노드를 리프 노드라고 합니다.

4. Brother 노드: 동일한 상위 노드를 갖는 모든 하위 노드를 Brother 노드라고 합니다.

5. 조상 노드: 루트 노드에서 노드 q까지의 경로가 있고 해당 노드 p가 이 경로에 나타나면 노드 p는 노드 q라고 할 수 있습니다. p의 자손 노드라고 합니다.

6. 노드 크기: 노드의 크기는 자신을 포함한 자손의 수를 나타냅니다.