Search trees , or in this chapter specifically binary search trees, are also recursively defined. A binary search tree is either an empty tree or a node containing a value and two trees, a left and a right subtree. Furthermore, we require that the value in a node is larger than all the values in its left subtree and smaller than all the values in its right subtree. It is the last property that makes search trees interesting for many algorithms. If we know that the smaller values are to the left, and the larger values are to the right, we can efficiently search in a tree, as we shall see.
© Thomas Mailund 2021
T. MailundPointers in C Programminghttps://doi.org/10.1007/978-1-4842-6927-5_1212. Search Trees
Thomas Mailund1
(1)
Aarhus N, Denmark
Get Pointers in C Programming: A Modern Approach to Memory Management, Recursive Data Structures, Strings, and Arrays now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
