McGraw-Hill OnlineMcGraw-Hill Higher EducationLearning Center
Student Center | Instructor's Center | Introduction to Algorithms | Home
Glossary A-B
Glossary B-D
Glossary D-F
Glossary F-J
Glossary J-M
Glossary M-O
Glossary O-P
Glossary P-S
Glossary S-T
Glossary T-Z
Chapter Objectives
Chapter Overview
Glossary
PowerPoint Slides
Algorithm Pseudocode
Feedback
Help Center


small text cover image
Introduction to Algorithms, 2/e
Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University
Binary Search Trees

Chapter Objectives

Search trees

  • Data structures that support many dynamic-set operations.
  • Can be used as both a dictionary and as a priority queue.
  • Basic operations take time proportional to the height of the tree.
  • For complete binary tree with n nodes: worst case Θ(lg n).
  • For linear chain of n nodes: worst case Θ(n).
  • Different types of search trees include binary search trees, red-black trees (covered in Chapter 13), and B-trees (covered in Chapter 18).

We will cover binary search trees, tree walks, and operations on binary search trees.










Copyright2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.