바이너리 트리에서 2 개의 자식 노드가있는 노드를 삭제하는 방법은 무엇입니까?2 진 검색 트리에서 2 개의 자식 노드가있는 노드를 삭제하는 방법은 무엇입니까?
어떤 방법으로 제거 할 수 있습니까? 내가 봤어. 하지만 그것에 대해 명확한 생각을하지 않았다. 누구든지 도식적 인 표현으로 설명 할 수 있습니까? 당신은 대체
How to delete the node '5' from the this image and what might be the outcome?
말했다의 오른쪽에있는 가장 왼쪽의 자녀, 또는 왼쪽의 오른쪽 대부분의 아이 노드입니다. 그런 다음 대체 된 하위에서 하위를 삭제합니다.
5 개를 삭제하면 어느 방향으로 루트가 3인지 루트인지 18 개가됩니다. http://www.algolist.net/Data_structures/Binary_search_tree/Removal
그것은 당신이 너무 이미지를 원하는 알고리즘을 보여줍니다 당신이이 사이트에서 해당 이미지를 가지고 같은
는 것 같습니다. 당신이 어린이 2 명, 귀하의 경우 5 노드를 삭제하면
http://en.wikipedia.org/wiki/Binary_search_tree
가, 오른쪽 하위 트리에서 최소 값 노드 삭제 된 노드를 대체 할 수
위키 백과 문서는 BST의 좋은 설명을 제공합니다 , 또는 왼쪽 하위 트리의 최대 값 노드.
자식이 2 명인 노드를 간단히 삭제하면 삭제 된 노드의 부모 노드의 하위 노드와 해당 하위 노드가 다시 레이블됩니다.
오른쪽 하위 트리의 가장 왼쪽 노드를 사용할 수 없습니다. 나무가 있고 오른쪽 하위 트리의 가장 왼쪽 노드가 15이지만 15의 부모도 15이므로 삭제할 노드를 오른쪽 하위 트리의 가장 왼쪽 노드로 바꾸면 동일한 노드를 얻을 수 있습니다. 오른쪽 하위 트리의 값입니다. 내 예에서는 15가 하위 트리의 새로운 루트가되고 루트의 오른쪽에는 15가 추가됩니다.
쉽고 간단한 해결책 :
Node* findMaxNode(Node* root)
{
if(root->right == NULL) return root;
findMaxNode(root->right);
}
Node* DeleteNodeInBST(Node* root,int data)
{
//base case when not found or found then recursion breaks
if(root == NULL) return root;
else if(root->data > data) root->left = DeleteNodeInBST(root->left, data);
else if(root->data < data) root->right = DeleteNodeInBST(root->right, data);
else
{
//when the node to be deleted is found
//Four possibilities
//case1: When the node to be deleted has no children
if(root->left == NULL && root->right == NULL)
{
delete root;
root = NULL;
}
//case2: When the node to be deleted has ONLY LEFT child
else if(root->right == NULL)
{
Node* temp = root;
root = root->left;
delete temp;
}
//case3: When the node to be deleted has ONLY RIGHT child
else if(root->left == NULL)
{
Node* temp = root;
root = root->right;
delete temp;
}
//case4: When the node to be deleted has TWO children
else
{
Node* maxNode = findMaxNode(root->left);//finding the maximum in LEFT sub-tree
root->data = maxNode->data; //Overwriting the root node with MAX-LEFT
root->left = DeleteNodeInBST(root->left, maxNode->data);//deleted the MAX-LEFT node
}
return root;
}
}
노드를 삭제하는 세 시나리오 수있다 ..
후계자를 이해해야합니다
삭제의 개념을 알고 전에 후계자 (또는 이전)을 삭제할 : 바이너리에서 노드의 트리 후속 노드는이 노드보다 엄격하게 큰 트리의 가장 작은 노드입니다. 오른쪽 서브 트리의 가장 왼쪽에있는 아이가 후계자가 될 것이다이 경우 :
는 노드
노드는 바로 아이가 두 가지 경우가 있습니다.
노드에는 하위 노드가 없습니다. 상위 노드로 이동하여이 노드가 왼쪽 하위 트리의 일부인 노드를 찾으십시오.
public Node sucessor(Node node) {
Node sucessor = null;
if (node.getRightNode() != null) {
Node newNode = node.getRightNode();
while (newNode != null) {
sucessor = newNode;
newNode = newNode.getLeftNode();
}
} else {
sucessor = findRightParent(node);
}
return sucessor;
}
private Node findRightParent(Node node) {
Node newNode = null;
if (node.getParentNode() != null) {
if (node.getParentNode().getLeftNode() == node) {
newNode = node.getParentNode();
} else {
newNode = findRightParent(node.getParentNode());
}
}
return newNode;
}
지금 삭제 로직
public void deleteNode(Node node) {
// Node is a leaf node //
if(node.getLeftNode() == null && node.getRightNode() == null){
if(isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(null);
}else{
node.getParentNode().setLeftNode(null);
}
// Only left child is there//
}else if(node.getLeftNode() != null && node.getRightNode() == null){
if(isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(node.getLeftNode());
}else{
node.getParentNode().setLeftNode(node.getLeftNode());
}
// Only Right child is there //
}else if(node.getLeftNode() == null && node.getRightNode() != null){
if(isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(node.getRightNode());
}else{
node.getParentNode().setLeftNode(node.getRightNode());
}
// Both Left and Right children are their//
}else{
Node psNode = predessor(node);
deleteNode(psNode);
psNode.setParentNode(node.getParentNode());
psNode.setLeftNode(node.getLeftNode());
psNode.setRightNode(node.getRightNode());
if(isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(psNode);
}else{
node.getParentNode().setLeftNode(psNode);
}
}
}
용액 http://coder2design.com/binary-tree/
에서 가져는 또한 전체 소스 코드를 탐색하고, 삽입의 흐름을 설명했다.
upvote의 정의에 대한 '승계인' –
알고리즘 :
->Find the node which need to delete (assume data is given)
->Find the deepest node of tree
->Replace deepest node's data with the node to be deleted
->Delete the deepest node
Java 구현 :
public static void deleteTheNode(BTNode root, int data) {
BTNode nodeToDelete = findTheNode(root, data);
if (nodeToDelete == null) {
System.out.println("Node Does not exists in Binary Tree");
return;
}
BTNode deepestNode = findDepestNodeOfBinaryTree(root);
nodeToDelete.setData(deepestNode.getData());
_deleteTheNode(root, deepestNode);
}
private static void _deleteTheNode(BTNode root, BTNode node) {
Queue<BTNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
BTNode temp = q.poll();
if (temp.getLeft() == node) {
temp.setLeft(null);
node = null;
break;
} else if (temp.getRight() == node) {
temp.setRight(null);
node = null;
break;
}
if (temp.getLeft() != null) {
q.offer(temp.getLeft());
}
if (temp.getRight() != null) {
q.offer(temp.getRight());
}
}
}
//Find the deepest nodeof the binary tree
public static BTNode findDepestNodeOfBinaryTree(BTNode root) {
int depth = 0;
BTNode deepetNode = root;
Stack<BTNode> nodes = new Stack<>();
Stack<BTNode> path = new Stack<>();
if (root == null) {
return null;
}
nodes.push(root);
while (!nodes.empty()) {
BTNode node = nodes.peek();
if (!path.empty() && node == path.peek()) {
if (path.size() > depth) {
depth = path.size() - 1;
deepetNode = node;
}
path.pop();
nodes.pop();
} else {
path.push(node);
if (node.getRight() != null) {
nodes.push(node.getRight());
}
if (node.getLeft() != null) {
nodes.push(node.getLeft());
}
}
}
return deepetNode;
}
노드의 중위 후계자를 찾아 삭제합니다. 그런 다음 노드의 inorder 후속 노드의 내용을 복사하고 inorder 후속 노드를 삭제합니다. (inorder successor 대신 inorder 전신을 사용할 수도 있습니다.)
이 프로그램은 작동하지만 다른 접근 방식을 사용합니다. 누군가 제가 왜 투표에 실패했는지 말할 수 있습니까? –