Packages

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

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

This implementation uses a resizing array and binary search.

The get' and contains as well as the tow-argument size, the floor and the ceiling operations take logarithmic time. The minimum, maximum and select as well as is-empty and the one-argument size operations are constant in time. The put operation is linear in time in the worst case.

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

See also

Section 3.1 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. BinarySearchTable
  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
    BinarySearchTable → 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
    BinarySearchTable → 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
    BinarySearchTable → 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
    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
    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
    BinarySearchTable → 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
    BinarySearchTable → 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
    BinarySearchTable → OrderedSymbolTable
    Exceptions thrown

    NoSuchElementException if table is empty

  25. def min: Key

    returns

    the smallest key

    Definition Classes
    BinarySearchTable → 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
    BinarySearchTable → OrderedSymbolTable
  30. def rank(key: Key): Int

    returns

    the number of keys less than the specified key

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

    returns

    the key of rank k

    Definition Classes
    BinarySearchTable → OrderedSymbolTable
    Exceptions thrown

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

  32. def size: Int
    Definition Classes
    BinarySearchTable → 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
    BinarySearchTable → 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
    BinarySearchTable → 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