BSTSuccessor 썸네일형 리스트형 [자료구조 트리] BST 삭제 완전 정복: Predecessor vs Successor (이진탐색트리) BST, 즉 Binary Search Tree에서 root를 remove하는데에는 2가지 방법이 있습니다.predecessor와 successor가 있는데 두 차이점과 어떻게 구한하는지를 적어보려 합니다. BST 삭제가 어려운 이유 BST Delete가 어려운 근본적인 이유는 단순합니다. 삭제 후에도 BST의 핵심 성질을 반드시 지켜야 하기 때문입니다.BST의 성질: Left 서브트리 삽입은 이 규칙에 따라 내려가다가 빈 자리에 꽂으면 끝지만, 근데 삭제는 다릅니다. 노드를 없애면 그 자리가 비어버리고, 그 아래 연결된 서브트리들이 붕 뜨게 됩니다. 이걸 BST 성질을 깨지 않으면서 다시 연결해야 합니다. BST 노드 삭제 과정은 크게 세 가지로 나뉩니다. Case 1자식이 없는 노드 (리프 노드)그.. 더보기 이전 1 다음
