이진 검색 트리(BST)
BST는 트리 구조를 사용하여 데이터를 저장하고 검색합니다.
각 노드에는 키가 있으며 루트 노드에서 시작하여 왼쪽 하위 트리는 작은 키를 가진 노드로 구성되고 오른쪽 하위 트리는 큰 키를 가진 노드로 구성됩니다.
BST에서는 검색, 삽입 및 삭제 작업이 가능합니다.
최악의 시간 복잡도는 \(O(n)\)할 수 있다
이진 검색 트리(BST) 삽입
1. BST에 새로운 요소를 삽입할 때 요소의 위치 찾기 이진 검색 수행하다
2. 삽입하려는 요소가 이미 트리에 존재하는 경우 삽입 중지하다
3. 요소가 트리에 없으면 요소를 삽입할 위치를 찾아 해당 위치에 요소를 삽입하고 위치를 내부 노드로 변환합니다.
예를 들어 키가 5인 요소를 삽입하려면 해당 키가 있는 노드를 찾아 키가 5인 새 요소를 삽입합니다.
리프 노드를 내부 노드로 변환하다
예를 들어 아래와 같은 이진 검색 트리가 있다고 가정합니다.
6
/ \
3 9
/ \ / \
1 4 7 10
\
5이때, 리프 노드 1, 4, 5, 7, 10을 내부 노드로 변환원하는 경우 다음과 같이 트리 구조를 재정렬할 수 있습니다.
6
/ \
3 9
/ \ / \
2 4 8 11
\
7위의 예에서 1, 5, 7, 10은 리프 노드이지만 각 노드를 삭제하고 이를 대체할 새 노드를 삽입하여 트리를 재구성합니다.
이때 새로 삽입된 노드는 자식을 가질 수 있으므로, 리프 노드에서 내부 노드로의 전환입니다.
이렇게 내부 노드로 변환된 노드는 추가 메모리를 사용할 수 있지만 트리의 구조를 보다 균형있게 만듭니다.
그래프에서 이름이 2인 내부 노드의 왼쪽 자식으로 이름이 1인 노드가 있습니다.
당신은 가지고 있습니다.
1은 2의 오른쪽에 있는 리프 노드였지만 2의 자식 노드가 되어 내부 노드가 되었습니다.
BST(이진 검색 트리) 삭제
위의 알고리즘은 BST에서 노드를 삭제하는 방법설명하다.
이는 다음 순서로 수행됩니다.
- 삭제할 노드를 찾습니다.
이것 원격 노드그것은 알려져있다. - 만약에 remNode가 리프인 경우즉, 자식 노드가 없으면 즉시 삭제하고 null을 반환합니다.
- 만약에emNode에는 자식 노드가 하나만 있습니다.
있는 경우 자식을 반환하여 remNode를 제거합니다. - 그렇지 않다면 remNode의 순차적 계승자삭제. 이 경우 inorder 계승자는 BST에서 remNode 이후의 노드를 참조합니다.
이 inorder 계승자의 키 값을 remNode에 복사한 다음 remNode를 반환합니다.
이렇게 하면 노드를 제거할 때 구조와 균형이 최소화됩니다.
이 접근 방식은 모든 삭제 사례를 다룰 수 있습니다.
후계자 이란
순차적 계승자이진 검색 트리에서 실행 삭제할 노드에 자식 노드가 2개 있는 경우이 노드를 대체할 노드를 나타냅니다.
이진 검색 트리에서 중위 순회, 노드는 오름차순으로 출력됩니다.
예를 들어, 다음 이진 검색 트리가 주어지면,
4
/ \
2 6
/ \ / \
1 3 5 7중위 순회는 1, 2, 3, 4, 5, 6, 7을 순서대로 출력합니다.
노드 4를 삭제하면 중위 순회노드 4 이후의 노드를 찾아야 합니다.
즉, 순차적 계승자당신은 여기를 찾아야합니다 5는 질서있는 후계자입니다.
이 되다.
따라서 삭제할 노드는 순차적 계승자삭제할 노드에 해당 값을 찾아 복사한 후, 순차적 계승자이 노드를 삭제하면 삭제할 수 있습니다.
간단히 말해서 노드 4는 노드 5가 되고, 노드 5는 두 개를 가질 수 없습니다.
이는 상위 노드 6의 왼쪽 하단 노드에서 5를 삭제한다는 의미입니다.