Packages

class BinarySearchTree[Key, Value] extends OrderedSymbolTable[Key, Value]

This class implements an ordered symbol table of generic key/value pairs.

This implementation uses a binary search tree.

The put, get and contains operations take linear time in the worst case, but logarithmic time on the average. All order-based operations take time proportional to the height of the tree in the worst case; this applies to minimum, maximum and select as well as floor, ceiling and the tow-argument size. The one-argument size and is-empty are constant in time.

Adapted from the book Algorithms 4 by R. Sedgewick and K. Wayne.

See also

Section 3.2 of Algorithms, 4th Edition

Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. http://algs4.cs.princeton.edu

Linear Supertypes
OrderedSymbolTable[Key, Value], BasicSymbolTable[Key, Value], AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. BinarySearchTree
  2. OrderedSymbolTable
  3. BasicSymbolTable
  4. AnyRef
  5. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. def apply(key: Key): Value

    returns

    value paired with key

    Definition Classes
    BinarySearchTree → BasicSymbolTable
    Exceptions thrown

    NoSuchElementException if key is not in table

  5. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  6. def ceil(key: Key): Key

    returns

    the smallest key greater than or equal to the specified key

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
    Exceptions thrown

    NoSuchElementException if key is greater than maximum key

  7. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  8. def contains(key: Key): Boolean
    Definition Classes
    BasicSymbolTable
  9. def delete(key: Key): Unit

    Removes key/value pair from table.

    Removes key/value pair from table.

    Definition Classes
    BinarySearchTree → BasicSymbolTable
    Exceptions thrown

    NoSuchElementException if key is not in table

  10. def deleteMax(): Unit

    Removes the node with the the largest key.

    Removes the node with the the largest key.

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
    Exceptions thrown

    NoSuchElementException if table is empty

  11. def deleteMin(): Unit

    Removes the node with the the smallest key.

    Removes the node with the the smallest key.

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
    Exceptions thrown

    NoSuchElementException if table is empty

  12. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  13. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  14. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  15. def floor(key: Key): Key

    returns

    the largest key less than or equal to the specified key

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
    Exceptions thrown

    NoSuchElementException if key is less than minimum key

  16. def get(key: Key): Option[Value]
    Definition Classes
    BasicSymbolTable
  17. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  18. def getOrElse(key: Key, default: ⇒ Value): Value
    Definition Classes
    BasicSymbolTable
  19. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  20. def isEmpty: Boolean
    Definition Classes
    BasicSymbolTable
  21. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  22. def keys(lo: Key, hi: Key): Iterable[Key]

    returns

    all keys in the table between lo and hi (inclusive) in sorted order

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
  23. def keys(): Iterable[Key]

    returns

    all keys in the table

    Definition Classes
    OrderedSymbolTable → BasicSymbolTable
  24. def max: Key

    returns

    the largest key

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
    Exceptions thrown

    NoSuchElementException if table is empty

  25. def min: Key

    returns

    the smallest key

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
    Exceptions thrown

    NoSuchElementException if table is empty

  26. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  27. final def notify(): Unit
    Definition Classes
    AnyRef
  28. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  29. implicit val ord: Ordering[Key]
    Attributes
    protected
    Definition Classes
    BinarySearchTree → OrderedSymbolTable
  30. def rank(key: Key): Int

    returns

    the number of keys less than the specified key

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
  31. def select(k: Int): Key

    returns

    the key of rank k

    Definition Classes
    BinarySearchTree → OrderedSymbolTable
    Exceptions thrown

    NoSuchElementException if k is less than 0 or greater than the maximum rank

  32. def size: Int
    Definition Classes
    BinarySearchTree → OrderedSymbolTable → BasicSymbolTable
  33. def size(lo: Key, hi: Key): Int

    returns

    the number of keys between lo and hi (inclusive)

    Definition Classes
    OrderedSymbolTable
  34. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  35. def toString(): String
    Definition Classes
    BinarySearchTree → OrderedSymbolTable → BasicSymbolTable → AnyRef → Any
  36. def update(key: Key, value: Value): Unit

    Inserts key/value pair into table.

    Inserts key/value pair into table. Replaces value if key is already there.

    Definition Classes
    BinarySearchTree → BasicSymbolTable
  37. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  38. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  39. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from OrderedSymbolTable[Key, Value]

Inherited from BasicSymbolTable[Key, Value]

Inherited from AnyRef

Inherited from Any

Ungrouped