TWiki > Doc > CodeExamples > BinarySearchTreeExample	TWiki webs: Dev | Doc | Main | TWiki | Sandbox
	Doc . { Changes | Index | Search | Go }

public <Comparable T,U> ?U getValue(?IntTreeNode<T,U> node, T key);
getValue(null, key) = null;

<Comparable T,U>
class IntTreeNode <T,U> {
  private !T m_key;
  private U m_value;
  private ?IntTreeNode<T,U> left = null;
  private ?IntTreeNode<T,U> right = null;
    
  public void add (!T key, U value) {
    if (key == m_key) 
    {
      m_value = value;
    } 
    else if (key < m_key)
    { 
      let theleft = left; 
      if (theleft == null) {
        left = new IntTreeNode (m_key: key, m_value: value);
      } else { 
        theleft.add (key, value);
        left = theleft;
      }
    } 
    else  
    { 
      let theright = right;
      if (theright == null) {
        right = new IntTreeNode (m_key: key, m_value: value);
      } else {
        theright.add (key, value);
        right = theright;
      }
    }
  } 
    
  override ?U getValue(T key) {
    if (key == m_key) {
      return m_value;
    } else if (key < m_key) {
      return left.getValue(key);
    } else {
      return right.getValue(key);
    }
  }
}

<Comparable T,U> 
class IntTree <T,U> {
  ?IntTreeNode<T,U> content = null;
    
  public void add (!T key, !U value) {
    let mycontent = content;
    if (mycontent == null) {
      content = new IntTreeNode (m_key: key, m_value: value);
    } else {
      mycontent.add (key, value);
      content = mycontent;
    }
  }
  
  public ?U getValue(!T key)
  { 
    return content.getValue(key);
  }
}

-- Raboof - 11 Apr 2005