1.9.2 Trees

 A tree is a data structure that can be used to represent data hierarchically. Data values in a tree structure are linked through parent-child relationships. In a general tree, a parent may have an umlimited number of children. In a binary tree, a parent may have at most two children, which we term the left child and the right child, A binary search tree additionally requires an ordering between the parent's two children in which left_child <= right_child. Figure 1.20 provides an example of a binary search tree. When we search for an item in a binary search tree, the worst0case performance is O(n)(consider how this can occur). To remedy this situations, we can use an algorithm to create a balanced binary search tree. Here, a tree containing n items has at most lg n levels, thus ensuring worst-case performance of O(lg n). We shall see in Section 5.7.1 that Linux uses a balanced binary search tree (known as a red-black tree) as part its CPU-scheduling algorithm.