O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

25

Online Dictionary Structures

Teofilo F. Gonzalez

University of California, Santa Barbara

25.1Introduction

25.2Trie Implementations

25.3Binary Search Tree Implementations

25.4Balanced BST Implementation

25.5Additional Operations

25.6Discussion

References

25.1Introduction

Given an initially empty set S, the dictionary problem consists of executing online any sequence of operations of the form S.membership(s), S.insert(s), and S.delete(s), where each element s is an object (or point in one-dimensional space). Each object can be stored in a single word, and it takes O(1) time to store or retrieve it. It is well known that the set may be represented by using arrays (sorted or unsorted), linked lists (sorted or unsorted), hash tables, binary search ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required