이진 검색 트리(BST) 다음 규칙을 따르는 특별한 유형의 트리입니다 -
-
왼쪽 자식 노드의 값은 항상 부모보다 작습니다. 참고
-
오른쪽 자식 노드는 부모 노드보다 큰 값을 가집니다.
-
모든 노드는 개별적으로 이진 검색 트리를 형성합니다.
이진 검색 트리(BST)의 예 -
검색, 최소값 및 최대값 찾기와 같은 작업의 복잡성을 줄이기 위해 이진 검색 트리가 생성됩니다.
이진 검색 트리(BST) 작업 삭제
삭제 작업은 트리에서 지정된 노드를 삭제합니다. 노드를 삭제하는 경우 세 가지 가능성이 있습니다 -
-
트리에서 리프 노드 삭제:가장 간단한 삭제는 이진 검색 트리에서 리프 노드를 삭제하는 것입니다. 리프 노드를 삭제하는 경우 리프만 영향을 받습니다. 예,
리프 노드 7을 삭제하면
-
하나의 자식 노드가 있는 노드 삭제:이 삭제를 위해 자식 노드를 삭제할 노드로 교체한 후 삭제해야 합니다. 예,
BST에서 2개 삭제
-
두 개의 자식 노드가 있는 노드 삭제:여기서 삭제할 노드에는 두 개의 자식 노드가 있습니다. 따라서 우리는 트리의 순서 형식으로 사용할 것입니다. 여기에서 요소를 삭제하고 해당 위치에 대해 순서가 없는 이웃을 선택하고 나머지를 재생성합니다. 예,
BST에서 5를 삭제하면 다음 트리가 반환됩니다.
예
#include#include 구조 노드{ int 키; struct node *left, *right;};struct node *newNode(int item){ struct node *temp =(struct node *)malloc(sizeof(struct node)); 임시 -> 키 =항목; 임시 -> 왼쪽 =임시 -> 오른쪽 =NULL; 반환 임시;} 무효 inordertraversal(구조 노드 *루트){ if (루트 !=NULL){ inordertraversal(루트->왼쪽); printf("%d ", 루트->키); inordertraversal(루트->오른쪽); }}struct node* insert(struct node* node, int key){ if (node ==NULL) return newNode(key); if (키 <노드->키) 노드->왼쪽 =삽입(노드->왼쪽, 키); else 노드->오른쪽 =삽입(노드->오른쪽, 키); 반환 노드;}구조 노드 * minValueNode(구조 노드* 노드){ 구조 노드* 현재 =노드; 동안 (현재 &&현재->왼쪽 !=NULL) 현재 =현재->왼쪽; return current;}struct node* deleteNode(struct node* root, int key){ if (root ==NULL) return root; if (키 <루트->키) 루트->왼쪽 =deleteNode(루트->왼쪽, 키); else if (키> 루트->키) 루트->오른쪽 =deleteNode(루트->오른쪽, 키); else{ if (루트->왼쪽 ==NULL){ 구조체 노드 *temp =루트->오른쪽; 무료(루트); 반환 온도; } else if (루트->오른쪽 ==NULL){ 구조체 노드 *temp =루트->왼쪽; 무료(루트); 반환 온도; } 구조체 노드* temp =minValueNode(루트->오른쪽); 루트 -> 키 =임시 -> 키; 루트->오른쪽 =deleteNode(루트->오른쪽, 임시->키); } return root;}int main(){ 구조체 노드 *root =NULL; 루트 =삽입(루트, 50); 루트 =삽입(루트, 30); 루트 =삽입(루트, 20); 루트 =삽입(루트, 40); 루트 =삽입(루트, 70); 루트 =삽입(루트, 60); 루트 =삽입(루트, 80); printf("주어진 트리의 순회 순회 \n"); inordertraversal(루트); printf("\n20개 삭제\n"); 루트 =삭제노드(루트, 20); printf("수정된 트리의 순회 순회 \n"); inordertraversal(루트); printf("\n30개 삭제\n"); 루트 =삭제노드(루트, 30); printf("수정된 트리의 순회 순회 \n"); inordertraversal(루트); printf("\n50 삭제\n"); 루트 =삭제노드(루트, 50); printf("수정된 트리의 순회 순회 \n"); inordertraversal(루트); 반환 0;}
출력
주어진 트리의 중위 순회20 30 40 50 60 70 80Delete 20수정된 트리의 중위 순회30 40 50 60 70 80Delete 306수정된 트리40 50 60 70 580Delete 70 580 수정된 트리의 중위 순회