none
BST Deletion node function RRS feed

  • Question

  • i am using Binary Search Tree in traverse the nodes that i inserted and i need to delete a node from it. 

    i don't know how to delete a node it is confusing and i couldn't find any source to explain it to me any kind of help would be appreciated. 

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace DeletionBST
    {
        class Program
        {
            static void Main(string[] args)
            { //insert nodes
                Tree BST = new Tree();
                BST.Insert(30);
                BST.Insert(35);
                BST.Insert(57);
                BST.Insert(15);
                BST.Insert(63);
                BST.Insert(49);
                BST.Insert(89);
                BST.Insert(77);
                BST.Insert(67);
                BST.Insert(98);
                BST.Insert(91);
                Console.WriteLine("Inorder Traversal : ");
                BST.Inorder(BST.ReturnRoot());
                Console.WriteLine(" ");
                Console.WriteLine();
                Console.WriteLine("Preorder Traversal : ");
                BST.Preorder(BST.ReturnRoot());
                Console.WriteLine(" ");
                Console.WriteLine();
                Console.WriteLine("Postorder Traversal : ");
                BST.Postorder(BST.ReturnRoot());
                Console.WriteLine(" ");
                Console.ReadLine();
            }
        }
        class Node
        {
            public int item;
            public Node left;
            public Node right;
            public void Display()
            {
                Console.Write("[");
                Console.Write(item);
                Console.Write("]");
            }
        }
        class Tree
        {
            public Node root;
            public Tree()
            {
                root = null;
            }
            public Node ReturnRoot()
            {
                return root;
            }
            public void Insert(int id)
            {
                Node newNode = new Node();
                newNode.item = id;
                if (root == null)
                    root = newNode;  //see if the node is empty insert that value in the current node
                else
                {
                    Node current = root;
                    Node parent;
                    while (true)
                    {
                        parent = current;
                        if (id < current.item)
                        {
                            current = current.left;
                            if (current == null)
                            {
                                parent.left = newNode;
                                return;
                            }
                        }
                        else
                        {
                            current = current.right;
                            if (current == null)
                            {
                                parent.right = newNode;
                                return;
                            }
                        }
                    }
                }
            }
            public void Preorder(Node Root)
            {
                if (Root != null)
                {
                    Console.Write(Root.item + " ");
                    Preorder(Root.left);
                    Preorder(Root.right);
                }
            }
            public void Inorder(Node Root)
            {
                if (Root != null)
                {
                    Inorder(Root.left);
                    Console.Write(Root.item + " ");
                    Inorder(Root.right);
                }
            }
            public void Postorder(Node Root)
            {
                if (Root != null)
                {
                    Postorder(Root.left);
                    Postorder(Root.right);
                    Console.Write(Root.item + " ");
                }
            }
           // public void Delete(Node root)
            {
    
            }
        }
    }
    

    Wednesday, November 29, 2017 3:47 PM

All replies

  • Completely depends upon how you implement your BST. In your case a node has a potential left and right node. So if you remove that node you have to update the tree. Updating a BST is documented in several places.

    Basically what you need to do is find the node's parent, if any. Once you find the parent node you will be replacing it's existing link (left or right) with a child of the node being deleted. There are a couple of scenarios to deal with. Note that this does not take into account the process of rebalancing the tree, if that is a requirement for you. Assume R is the node to delete and P is the parent node. Whether R is stored in the left or right portion of P is not relevant but we'll assume left for this discussion.

    1 - The node has no left or right children.  R { left = null, right = null }
    In this case the node can be removed and the parent node's link set to null. P { left = null }

    2 - The node has either a left or right child but not both. R { left = A, right = null }
    Since there is only 1 child that child becomes the node that the parent node links to.  P { left = A }

    3 - The node has both a left and right child. R { left = A, right = B }, B { left = C }, C { left = null }

    In this case either A or B has to be promoted up to P. It doesn't really matter which one you choose but I think the right node is the most common. B becomes the node the link in the parent P { left = B }. But you cannot lose the left node (A) so that node now becomes the left-most child of the new root node (B). So you follow the left children down until you find a null C { left = A }. At this point the tree is not balanced but the sorting is still intact.


    Michael Taylor http://www.michaeltaylorp3.net

    Wednesday, November 29, 2017 8:00 PM
    Moderator