Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: need ideas for implemeting special Binary search tree

  1. #1
    Junior Member
    Join Date
    Mar 2014
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default need ideas for implemeting special Binary search tree

    hey guys..

    i need ideas or algorithms for implementing a special version of binary search tree..

    the tree is an normal binary seatch tree, where left is smaller than right node.
    but each node has a counter, each time i'll find a node using find method the count should increment by one
    and node with highest count should replace the root of the tree...

    any idea would be great..


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,147
    My Mood
    Mellow
    Thanks
    187
    Thanked 660 Times in 647 Posts

    Default Re: need ideas for implemeting special Binary search tree

    Welcome to the forum! Please read this topic to learn how to post code in code or highlight tags and other useful info for new members.

    Show the code for the binary tree and the node. Is there a reason for the scheme you've explained? Ultimately, what are you trying to do?

  3. #3
    Junior Member
    Join Date
    Mar 2014
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: need ideas for implemeting special Binary search tree

    here the code:

    public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T> implements
    		BinarySearchTreeADT<T> {
     
    	BinaryTreeNode<T> newParent = null;
     
    	public LinkedBinarySearchTree() {
    		super();
    	}
     
     
    	public LinkedBinarySearchTree(T element) {
    		super(element);
    	}
     
     
    	public void addElement(T element) {
    		BinaryTreeNode<T> temp = new BinaryTreeNode<T>(element);
    		if (root == null)
    			root = temp;
    		else
    			add(temp, root);
    	}
     
    	public void addElement(T element, int hitCount) {
    		BinaryTreeNode<T> temp = new BinaryTreeNode<T>(element, hitCount);
    		if (newParent == null)
    			newParent = temp;
    		else
    			add(temp, newParent);
    	}
     
    	protected void add(BinaryTreeNode<T> node, BinaryTreeNode<T> next) {
    		Comparable<T> compElement = (Comparable<T>) node.element;
    		if (compElement.compareTo(next.element) < 0) {
    			if (next.left == null)
    				next.left = node;
    			else
    				add(node, next.left);
    		} else {
    			if (next.right == null)
    				next.right = node;
    			else
    				add(node, next.right);
    		}
    		count++;
    	}
     
    	public boolean contains(T targetElement) {
    		return super.contains(targetElement);
    	}
     
    	public T removeElement(T targetElement) throws ElementNotFoundException {
    		T result = null;
     
    		if (!isEmpty()) {
    			if (((Comparable) targetElement).equals(root.element)) {
    				result = root.element;
    				root = replacement(root);
    				count--;
    			} else {
    				BinaryTreeNode<T> current, parent = root;
    				boolean found = false;
     
    				if (((Comparable) targetElement).compareTo(root.element) < 0)
    					current = root.left;
    				else
    					current = root.right;
     
    				while (current != null && !found) {
    					if (targetElement.equals(current.element)) {
    						found = true;
    						count--;
    						result = current.element;
     
    						if (current == parent.left) {
    							parent.left = replacement(current);
    						} else {
    							parent.right = replacement(current);
    						}
    					} else {
    						parent = current;
     
    						if (((Comparable) targetElement)
    								.compareTo(current.element) < 0)
    							current = current.left;
    						else
    							current = current.right;
    					}
    				} // while
     
    				if (!found)
    					throw new ElementNotFoundException("binary search tree");
    			}
    		} // end outer if
     
    		return result;
    	}
     
    	public void removeAllOccurrences(T targetElement)
    			throws ElementNotFoundException {
    		removeElement(targetElement);
     
    		try {
    			while (contains((T) targetElement))
    				removeElement(targetElement);
    		}
     
    		catch (Exception ElementNotFoundException) {
    		}
    	}
     
    	public T removeMin() throws EmptyCollectionException {
    		T result = null;
     
    		if (isEmpty())
    			throw new EmptyCollectionException("binary search tree");
    		else {
    			if (root.left == null) {
    				result = root.element;
    				root = root.right;
    			} else {
    				BinaryTreeNode<T> parent = root;
    				BinaryTreeNode<T> current = root.left;
    				while (current.left != null) {
    					parent = current;
    					current = current.left;
    				}
    				result = current.element;
    				parent.left = current.right;
    			}
     
    			count--;
    		}
     
    		return result;
    	}
     
    	public T removeMax() throws EmptyCollectionException {
    		T result = null;
     
    		if (isEmpty())
    			throw new EmptyCollectionException("binary search tree");
    		else {
    			if (root.right == null) {
    				result = root.element;
    				root = root.left;
    			} else {
    				BinaryTreeNode<T> parent = root;
    				BinaryTreeNode<T> current = root.right;
    				while (current.right != null) {
    					parent = current;
    					current = current.right;
    				}
     
    				result = current.element;
    				parent.right = current.left;
    			}
     
    			count--;
    		}
     
    		return result;
    	}
     
    	public T findMin() throws EmptyCollectionException {
    		T result = null;
     
    		if (isEmpty())
    			throw new EmptyCollectionException("binary search tree");
    		else {
    			BinaryTreeNode<T> current = root;
     
    			while (current.left != null)
    				current = current.left;
     
    			result = current.element;
    		}
    		return result;
    	}
     
    	public T findMax() throws EmptyCollectionException {
    		T result = null;
     
    		if (isEmpty())
    			throw new EmptyCollectionException("binary search tree");
    		else {
    			BinaryTreeNode<T> current = root;
     
    			while (current.right != null)
    				current = current.right;
     
    			result = current.element;
    		}
    		return result;
    	}
     
    	public T find(T targetElement) throws ElementNotFoundException {
    		BinaryTreeNode<T> current = root;
    		BinaryTreeNode<T> temp = current;
     
    		if (!(current.element.equals(targetElement))
    				&& (current.left != null)
    				&& (((Comparable) current.element).compareTo(targetElement) > 0))
    			current = findAgain(targetElement, current.left);
     
    		else
    			if (!(current.element.equals(targetElement))
    					&& (current.right != null))
    				current = findAgain(targetElement, current.right);
     
    		if (!(current.element.equals(targetElement)))
    			throw new ElementNotFoundException("binary search tree");
    		return current.element;
    	}
     
    	private BinaryTreeNode<T> findAgain(T targetElement, BinaryTreeNode<T> next) {
    		if (!(next.element.equals(targetElement)) && (next.left != null)
    				&& (((Comparable) next.element).compareTo(targetElement) > 0))
    			next = findAgain(targetElement, next.left);
     
    		else if (!(next.element.equals(targetElement)) && (next.right != null))
    			next = findAgain(targetElement, next.right);
     
    		return next;
    	}
     
    	protected BinaryTreeNode<T> replacement(BinaryTreeNode<T> node) {
    		BinaryTreeNode<T> result = null;
     
    		if ((node.left == null) && (node.right == null))
    			result = null;
     
    		else if ((node.left != null) && (node.right == null))
    			result = node.left;
     
    		else if ((node.left == null) && (node.right != null))
    			result = node.right;
     
    		else {
    			BinaryTreeNode<T> current = node.right;
    			BinaryTreeNode<T> parent = node;
     
    			while (current.left != null) {
    				parent = current;
    				current = current.left;
    			}
     
    			if (node.right == current)
    				current.left = node.left;
     
    			else {
    				parent.left = current.right;
    				current.right = node.right;
    				current.left = node.left;
    			}
     
    			result = current;
    		}
     
    		return result;
    	}
     
    }

    the node in this tree should have an extra attribute counter, Every time the node is found with the find
    methods its hit count is incremented by one. and the node with highest count will be the new root.

    just need an idea how the node could be the new root.
    one possible solution could be, check counter for every node and update the tree or replace...

  4. #4
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,147
    My Mood
    Mellow
    Thanks
    187
    Thanked 660 Times in 647 Posts

    Default Re: need ideas for implemeting special Binary search tree

    Again, I'm curious what you're trying to accomplish, but absent that . . .

    Since a BST has a specific structure to be a BST, let's agree that once you start moving a BST's nodes around, it's no longer a BST. You've described how a node becomes promoted to be the root, but you haven't indicated what happens to the existing root. Two immediate options occur:

    1. the existing root and new root nodes swap places, or
    2. after being replaced by the new root, the existing root is demoted according to some rule, perhaps following normal BST construction.

    The 'some rule' of number 2 could become problematic as the tree spirals away from anything resembling a BST. Executing either option 1 or 2 requires a Node swap() method, so I suggest you write that and then determine the promotion/demotion rules.

  5. #5
    Junior Member
    Join Date
    Mar 2014
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: need ideas for implemeting special Binary search tree

    it's first option about swap root with an node..
    but how to do it? i have no clue..

    and here is my node class:

     
     
    public class BinaryTreeNode<T>
    {
       protected T element;
       protected BinaryTreeNode<T> left, right;
       protected int counter;
       protected BinaryTreeNode<T> node;
     
     
       BinaryTreeNode (T obj) 
       {
          element = obj;
          left = null;
          right = null;
          counter = 0;
       }
       BinaryTreeNode (T obj, int hits) 
       {
          element = obj;
          left = null;
          right = null;
          this.counter = hits;
       }
     
     
       public void setLeft(BinaryTreeNode<T> left)
       {
    	   this.left = left;
       }
       public void setRight(BinaryTreeNode<T> right)
       {
    	   this.right = right;
       }
     
       public BinaryTreeNode<T> getLeft()
       {
    	   return left;
       }
     
       public BinaryTreeNode<T> getRight()
       {
    	   return right;
       }
     
       public T getElement()
       {
    	   return element;
       }
     
       public int numChildren() 
       {
          int children = 0;
     
          if (left != null)
             children = 1 + left.numChildren();
     
          if (right != null)
             children = children + 1 + right.numChildren();
     
          return children;
       }
     
       public void increment()
       {
    	   counter++;
       }
    }

Similar Threads

  1. Binary Search Tree inorder tree traversal
    By Maukkv in forum What's Wrong With My Code?
    Replies: 17
    Last Post: January 26th, 2013, 04:28 PM
  2. Binary Tree Search[HELP]
    By husain2213 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 13th, 2012, 10:33 PM
  3. Binary Search Tree
    By lex25288 in forum Algorithms & Recursion
    Replies: 3
    Last Post: January 19th, 2011, 08:10 AM
  4. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  5. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 08:27 AM