Note that there are some explanatory texts on larger screens.

plurals
  1. POJava BinarySearchTrees: input key return value(lookup)
    primarykey
    data
    text
    <p>I'm trying to implement a database interface using BSTs. I have an inner class BTSEntry which represents a node with variables key, value and left/right nodes. Each left node is less(in alphabetical order) than its parent, while each right node is bigger than its parent.</p> <p>The first problem is that I don't know what is the "nextNode()" in the Entry inner class supposed to be. Is it simply the right node? Or is it what I have done below?</p> <pre><code>private BinarySearchTreeEntry getLeftMost() { BinarySearchTreeEntry n = this; while (n.left != null) { n = n.left; } return n; } public BinarySearchTreeEntry getNext() { if (right != null) { return right.getLeftMost(); } else { BinarySearchTreeEntry n = this; while (n.parent != null &amp;&amp; n == n.parent.right) { n = n.parent; } return n.parent; } } </code></pre> <p>The second problem is that I don't really know how to implement the "Int value get(Str key)" method. EDIT: I have tried to do the get(key) method. Is it correct? Will recursion work for this?</p> <pre><code>public Integer get(String key) throws NoSuchElementException { BinarySearchTreeEntry curr = root; if(curr == null){ return null; } else if(curr.getKey().equals(key)){ return curr.getValue(); } else if(key.compareTo(curr.getKey()) &lt; 0){ curr = curr.getLeft(); get(key); } else{ curr = curr.getRight(); get(key); } return null; } </code></pre> <p>Here is what I have done so far. Any help would be greatly appreciated! :) </p> <pre><code> package database; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Stack; public class BinarySearchTree&lt;K, V&gt; implements Dictionary&lt;String, Integer&gt; { private class BinarySearchTreeEntry implements DictionaryEntry&lt;String, Integer&gt;{ private String key; private Integer value; private BinarySearchTreeEntry left; private BinarySearchTreeEntry right; private BinarySearchTreeEntry parent; BinarySearchTreeEntry(String key, Integer value, BinarySearchTreeEntry left, BinarySearchTreeEntry right) { this.key = key; this.value = value; this.left = left; this.right = right; if (left != null) left.parent = this; if (right != null) right.parent = this; } private BinarySearchTreeEntry getLeftMost() { BinarySearchTreeEntry n = this; while (n.left != null) { n = n.left; } return n; } private BinarySearchTreeEntry getRightMost() { BinarySearchTreeEntry n = this; while (n.right != null) { n = n.right; } return n; } public BinarySearchTreeEntry getNext() { if (right != null) { return right.getLeftMost(); } else { BinarySearchTreeEntry n = this; while (n.parent != null &amp;&amp; n == n.parent.right) { n = n.parent; } return n.parent; } } public String getKey() { return key; } public Integer getValue() { return value; } public BinarySearchTreeEntry getLeft() { return left; } public BinarySearchTreeEntry getRight() { return right; } } private class ListIterator implements Iterator&lt;DictionaryEntry&lt;String, Integer&gt;&gt; { private BinarySearchTreeEntry current; Stack&lt;BinarySearchTreeEntry&gt; workList; public ListIterator(BinarySearchTreeEntry entry){ current = entry; } public boolean hasNext() { return current != null; } public BinarySearchTreeEntry next() { BinarySearchTreeEntry result = null; current = root; while(current!=null){ workList.push(current); current = current.getLeft(); } if(!workList.isEmpty()){ result = (BinarySearchTreeEntry) workList.pop(); current = result.getRight(); } return result; } public void remove() { } } private BinarySearchTreeEntry root; private int items; public BinarySearchTree(){ root = null; items = 0; } public int size() { ListIterator iter = iterator(); while(iter.hasNext()){ items += 1; } return items; } public boolean isEmpty() { return size() == 0; } public Integer get(String key) throws NoSuchElementException { BinarySearchTreeEntry curr = root; if(curr == null){ return null; } else if(curr.getKey().equals(key)){ return curr.getValue(); } else if(key.compareTo(curr.getKey()) &lt; 0){ //Now what? } return null; } public void put(String key, Integer value) { } public void clear() { ListIterator iter = iterator(); BinarySearchTreeEntry curr; curr = root; while(iter.hasNext()){ remove(curr.getKey()); curr = iter.next(); } remove(curr.getKey()); } public void remove(String key) throws NoSuchElementException { } public ListIterator iterator() { return (new ListIterator(root)); } } </code></pre>
    singulars
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload