Data Structures & Algorithms Notes Page

Dictionary Abstract Data Type:

• Elements are comparable (Type T)

  • Which means they can be fully ordered

• No null values → No duplicates allowed

• Operations: Insert, delete, search, min, max, size, isEmpty

• Additional Operations:

  • successor(x) → Element in dictionary after x when sorted
  • predecessor(x) → Element in dictionary before x when sorted

Motivation:

• O(n) for insert / delete is expensive if dictionary is dynamic.

Binary Search Tree: