Results 1 to 3 of 3
  1. #1
    benn22 is offline Member
    Join Date
    Feb 2011
    Posts
    17
    Rep Power
    0

    Default Binary Search Tree - Delete Node Iteratively

    My code works recursively for deletion:

    Java Code:
    	public void delete(K key) throws KeyNotFoundException{
    		root = delete(root, key);
    	}
    	
    	protected bstNode<K,V> delete(bstNode<K,V> T, K key){
    		if (T != null){
    			if (key.compareTo(T.key) < 0){
    				T.left = delete(T.left, key);
    			}else if (key.compareTo(T.key) > 0){
    				T.right = delete(T.right, key);
    			}else{
    				this.BSTSize--;
    				if (T.left == null && T.right == null){
    					T = null;
    				}else if (T.left == null){
    					T = T.right;
    				}else if (T.right == null){
    					T = T.left;
    				}else{
    					bstNode<K,V> minNode = getMin(T.right);
    					T.key = minNode.key;
    					T.value = minNode.value;
    					T.right = delete(T.right, T.key);		
    				}
    			}
    		}else{
    			throw new KeyNotFoundException();
    		}
    		return T;
    	}
    	
    	public bstNode<K,V> getMin() {
    		return getMin(root);
    	}
    	
    	protected bstNode<K,V> getMin(bstNode<K,V> T) {
    		if (T == null) {
    			return null;
    		} else if (T.left == null) {
    			return T;
    		} else {
    			return getMin(T.left);
    		}
    	}
    Here is my attempt of doing it iteratively:

    Java Code:
    public void delete(K key) throws KeyNotFoundException{
    		if (root != null){
    			bstNode<K,V> deleteNode = root;
    			while (deleteNode != null){
    				if (key.compareTo(deleteNode.key) < 0){
    					deleteNode = deleteNode.left;
    					return;
    				}else if (key.compareTo(deleteNode.key) > 0){
    					deleteNode = deleteNode.right;
    					return;
    				}else{
    					this.BSTSize--;
    					if (deleteNode.left == null && deleteNode.right == null){
    						deleteNode = null;
    					}else if (deleteNode.left == null){
    						deleteNode = deleteNode.right;
    					}else if (deleteNode.right == null){ 
    						deleteNode = deleteNode.left;
    					}else{
    						bstNode<K,V> minNode = getMin(deleteNode.right);
    						deleteNode.key = minNode.key;
    						deleteNode.value = minNode.value;
    						//*I don't know how to do it here with two children*
    					}
    				}
    			}
    		}else{
    			throw new KeyNotFoundException();
    		}
    }
    I don't know how to work with a node if it has two children (iteratively). I think the other parts seem OK.

    Thanks for your help.

  2. #2
    benn22 is offline Member
    Join Date
    Feb 2011
    Posts
    17
    Rep Power
    0

    Default Re: Binary Search Tree - Delete Node Iteratively (RESOLVED)

    *Code will be posted after the assignments due date*
    Last edited by benn22; 11-18-2012 at 04:53 AM.

  3. #3
    benn22 is offline Member
    Join Date
    Feb 2011
    Posts
    17
    Rep Power
    0

    Default Re: Binary Search Tree - Delete Node Iteratively (RESOLVED)

    As promised:
    Java Code:
    	@Override
    	public void delete(K key) throws KeyNotFoundException{	
    		bstNode<K,V> parent = null;
    		bstNode<K,V> child = root;
    		bstNode<K,V> node = root;
    		while (node != null && node.key != key){
    			parent = node;
    			if (key.compareTo(node.key) < 0)
    				node = node.left; //Scan left
    			else
    				node = node.right; //Scan right
    		}
    		
    		if (node == null)
    			throw new KeyNotFoundException();
    		
    		//key found, work with their children
    		if (node.left == null && node.right == null){ 
    			if (parent == null)
    				root = null;
    			else if (key.compareTo(parent.key) < 0)
    				parent.left = null;
    			else
    				parent.right = null;
    		}else if (node.left == null){ //If left child is null, get right child
    			child = node.right;
    			swapKeys(node, child);
    			swapValues(node, child);
    			node.left = child.left;
    			node.right = child.right;
    		}else if (node.right == null){ //If right child is null, get left child
    			child = node.left;
    			swapKeys(node, child);
    			swapValues(node, child);
    			node.left = child.left;
    			node.right = child.right;
    		}else{ //If two children
    			child = node.left;
    			parent = null;
    			while (child.right != null){
    				parent = child;
    				child = parent.right;
    			}
    			if (parent == null){
    				swapKeys(node, child);
    				swapValues(node, child);
    				node.left = child.left;
    			}else{
    				swapKeys(node, child);
    				swapValues(node, child);
    				parent.right = child.left;
    			}
    		}
    	}
    	
    	private void swapKeys(bstNode<K,V> node, bstNode<K,V> child){
    		K temp = node.key;
    		node.key = child.key;
    		child.key = temp;
    	}
    	
    	private void swapValues(bstNode<K,V> node, bstNode<K,V> child){
    		V temp = node.value;
    		node.value = child.value;
    		child.value = temp;		
    	}

Similar Threads

  1. How to sample a node from a binary tree efficiently?
    By malaguena in forum Advanced Java
    Replies: 0
    Last Post: 03-12-2011, 05:57 PM
  2. Binary search tree
    By hansmoolman in forum New To Java
    Replies: 2
    Last Post: 10-28-2010, 01:59 PM
  3. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  4. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 01:42 AM
  5. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 02:03 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •