Binary Search Trees
A Binary Search Tree (BST) is a binary tree with the following additional property. The value at the root node is greater (or equal) than all the values in the left subtree. Likewise, the value is lesser than (or equal) all the values in the right subtree.
We keep things simple and don't consider the multiple equal values case. Rather, we implement dictionaries using binary trees.
A dictionary is a list of (key, value) pairs. A key can occur only once, that is, the key is unique. For example, we could use dictionaries to compute the count of words in a given text input.
The word count algorithm is simple:
words[] = split a string on space characters. for each word, search the dictionary if it is already present. if not in dictionary, ...
Get Learning Functional Data Structures and Algorithms 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.
