Thread: 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..

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?

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...

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.

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++;
   }
}