삭제 기능은 이진 검색 트리에서 지정된 노드를 삭제하는 데 사용됩니다. 그러나 이진 검색 트리의 속성을 위반하지 않는 방식으로 이진 검색 트리에서 노드를 삭제해야 합니다. 이진 검색 트리에서 노드를 삭제하는 세 가지 상황이 있습니다.
삭제할 노드는 리프 노드입니다.
가장 간단한 경우입니다. 이 경우 리프 노드를 NULL로 교체하고 할당된 공간을 간단히 해제합니다.
자바 수학 펑
다음 이미지에서는 노드 85를 삭제합니다. 해당 노드는 리프 노드이므로 해당 노드는 NULL로 대체되고 할당된 공간이 해제됩니다.
삭제할 노드에는 하위 노드가 하나만 있습니다.
이 경우 노드를 하위 노드로 교체하고 삭제할 값이 포함된 하위 노드를 삭제합니다. 간단히 NULL로 바꾸고 할당된 공간을 해제하세요.
다음 이미지에서는 노드 12가 삭제됩니다. 자녀가 한 명뿐입니다. 노드는 하위 노드로 교체되고 교체된 노드 12(현재 리프 노드)는 삭제됩니다.
삭제할 노드에는 두 개의 하위 노드가 있습니다.
다른 두 경우에 비해 조금 복잡한 경우입니다. 그러나 삭제될 노드는 (삭제될) 노드 값이 트리의 리프에 배치될 때까지 반복적으로 순서대로의 후속 노드 또는 선행 노드로 대체됩니다. 절차가 끝나면 노드를 NULL로 교체하고 할당된 공간을 해제합니다.
다음 이미지에서는 트리의 루트 노드인 노드 50이 삭제됩니다. 아래에 주어진 트리의 순서대로 순회합니다.
6, 25, 30, 50, 52, 60, 70, 75.
스캐너 다음
50을 후속 후속 항목인 52로 바꿉니다. 이제 50은 트리의 리프로 이동되며 간단히 삭제됩니다.
연산
삭제(트리, 항목)
ELSE IF ITEM DATA '트리에서 찾을 수 없는 항목'이라고 씁니다.
삭제(TREE->LEFT, ITEM)
ELSE IF 항목 > 트리 -> 데이터
삭제(트리 -> 오른쪽, 항목)
ELSE IF TREE -> 왼쪽 및 TREE -> 오른쪽
SET TEMP = findLargestNode(나무 -> 왼쪽)
트리 설정 -> 데이터 = 온도 -> 데이터
삭제(트리 -> 왼쪽, 온도 -> 데이터)
또 다른
설정 온도 = 나무
IF 트리 -> 왼쪽 = NULL이고 트리 -> 오른쪽 = NULL
세트 트리 = NULL
ELSE IF 트리 -> 왼쪽 != NULL
트리 설정 = 트리 -> 왼쪽
또 다른
트리 설정 = 트리 -> 오른쪽
[IF 끝]
무료 온도
[IF 끝]
기능:
void deletion(Node*& root, int item) { Node* parent = NULL; Node* cur = root; search(cur, item, parent); if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur- >right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? Cur- >left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } Node* findMinimum(Node* cur) { while(cur->left != NULL) { cur = cur->left; } return cur; }