程序包 edu.princeton.cs.algs4

类 BTree<Key extends java.lang.Comparable<Key>,​Value>

  • public class BTree<Key extends java.lang.Comparable<Key>,​Value>
extends java.lang.Object
    The BTree class represents an ordered symbol table of generic key-value pairs. It supports the put, get, contains, size, and is-empty methods. A symbol table implements the associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike Map, this class uses the convention that values cannot be null—setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

    This implementation uses a B-tree. It requires that the key type implements the Comparable interface and calls the compareTo() and method to compare two keys. It does not call either equals() or hashCode(). The get, put, and contains operations each make logm(n) probes in the worst case, where n is the number of key-value pairs and m is the branching factor. The size, and is-empty operations take constant time. Construction takes constant time.

    For additional documentation, see Section 6.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • 构造器概要

      构造器 
      构造器 说明
      BTree()
      Initializes an empty B-tree.

    • 方法概要

      修饰符和类型 方法 说明
      Value get​(Key key)
      Returns the value associated with the given key.
      int height()
      Returns the height of this B-tree (for debugging).
      boolean isEmpty()
      Returns true if this symbol table is empty.
      static void main​(java.lang.String[] args)
      Unit tests the BTree data type.
      void put​(Key key, Value val)
      Inserts the key-value pair into the symbol table, overwriting the old value with the new value if the key is already in the symbol table.
      int size()
      Returns the number of key-value pairs in this symbol table.
      java.lang.String toString()
      Returns a string representation of this B-tree (for debugging).

      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    • 构造器详细资料

      • BTree

        public BTree()
        Initializes an empty B-tree.

    • 方法详细资料

      • isEmpty

        public boolean isEmpty()
        Returns true if this symbol table is empty.
        返回:
        true if this symbol table is empty; false otherwise

      • size

        public int size()
        Returns the number of key-value pairs in this symbol table.
        返回:
        the number of key-value pairs in this symbol table

      • height

        public int height()
        Returns the height of this B-tree (for debugging).
        返回:
        the height of this B-tree

      • get

        public Value get​(Key key)
        Returns the value associated with the given key.
        参数:
        key - the key
        返回:
        the value associated with the given key if the key is in the symbol table and null if the key is not in the symbol table
        抛出:
        java.lang.IllegalArgumentException - if key is null

      • put

        public void put​(Key key,
                Value val)
        Inserts the key-value pair into the symbol table, overwriting the old value with the new value if the key is already in the symbol table. If the value is null, this effectively deletes the key from the symbol table.
        参数:
        key - the key
        val - the value
        抛出:
        java.lang.IllegalArgumentException - if key is null

      • toString

        public java.lang.String toString()
        Returns a string representation of this B-tree (for debugging).
        覆盖:
        toString 在类中 java.lang.Object
        返回:
        a string representation of this B-tree.

      • main

        public static void main​(java.lang.String[] args)
        Unit tests the BTree data type.
        参数:
        args - the command-line arguments