> Java > java지도 시간 > 본문

Java에서 이진 검색 트리를 구현하는 방법

王林
풀어 주다: 2023-06-03 20:46:01
앞으로
1375명이 탐색했습니다.

1. 개념

a. 각 노드는 최대 2개의 하위 노드를 갖습니다.

b 이 트리에 있는 노드의 값은

왼쪽 하위 트리

동일한 값은 일반적으로 이진 검색 트리에서 고려되지 않습니다(요소는 반복되지 않음). JDK의 검색 트리는 동일한 값(TreeMap-key)을 갖지 않습니다.

Java에서 이진 검색 트리를 구현하는 방법

가장 큰 특징: 또한 검색 트리인지 확인하는 방법

트리를 순서대로 순회하여 오름차순 집합을 얻을 수 있습니다. 0 1 2 3 4 5 6 7 8 9

순서대로 이진 검색의 시간 복잡도를 계산하려면 logN

logN =》"tree"

2와 연결될 때까지 /2/2 / 2 == 1을 계속 설정하세요. 2. 키 작업

Java에서 이진 검색 트리를 구현하는 방법

58이 삭제되면 , 이 노드의 왼쪽 및 오른쪽 하위 트리가 모두 비어 있습니다

Hibbard 삭제 1962

왼쪽 및 오른쪽 하위 트리가 모두 있는 BST에서 노드를 삭제합니다.

새 루트 노드가 58인 현재 루트 노드의 이전 노드 또는 후속 노드를 찾습니다. 삭제 후 노드

Predecessor: 루트가 58인 BST에서 58->53보다 작은 마지막 노드

Successor: 루트가 58->59인 BST에서 58보다 큰 첫 번째 노드

후임 노드를 사용할 때 노드, root.left

TreeNode successor = findMin(root.right);
successor.right = removeMin(root.right);
successor.left = root.left;
로그인 후 복사

3에도 불구하고 먼저 RemoveMin(root.right)을 연결하세요.

위 내용은 Java에서 이진 검색 트리를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:yisu.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿