O'Reilly logo

Data Structures and Algorithms Using Python by Rance D. Necaise

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

Chapter 14. Search Trees

Searching, which has been discussed throughout the text, is a very common operation and has been studied extensively. A linear search of an array or Python list is very slow, but that can be improved with a binary search. Even with the improved search time, arrays and Python lists have a disadvantage when it comes to the insertion and deletion of search keys. Remember, a binary search can only be performed on a sorted sequence. When keys are added to or removed from an array or Python list, the order must be maintained. This can be time consuming since keys have to be shifted to make room when adding a new key or to close the gap when deleting an existing key. The use of a linked list provides faster insertions and deletions without having to shift the existing keys. Unfortunately, the only type of search that can be performed on a linked list is a linear search, even if the list is sorted. In this chapter, we explore some of the many ways the tree structure can be used in performing efficient searches.

The tree structure, which was introduced in the last chapter, can be used to organize dynamic data in a hierarchical fashion. Trees come in various shapes and sizes depending on their application and the relationship between the nodes. When used for searching, each node contains a search key as part of its data entry (sometimes called the payload)and the nodes are organized based on the relationship between the keys. There are many different types of 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