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

1. 개념

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

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

왼쪽 하위 트리

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

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

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

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

logN =》"tree"

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

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!