Learn the basic algorithms for traversing trees and graphs.
Binary Search Tree
Optional NodePremium Content - Free Preview
The Tree data structure is used in many different areas of programming. For example, file systems use trees to store directories and files hierarchically. Another common usage of Trees is to sort data, such as in the Binary Search Tree.
Data - Keys and Values
Many types of data consist of keys and values. For example, books (values) in libraries are stored based on their ISBN number (keys) and you can look up topics (keys) in a book index to find the page (value) that the topic is discussed.
Computers also use keys and values to help find information faster. As in the above examples, data is often associated with a key (usually a unique one), which can then be accessed to find the relevant data quickly. For example, a unique ID can be associated, with a book, song, user account, node, module and more. The data is then accessed by looking up the key in a data structure.
Good Data Structure for Storing Data
Depending on the type of data involved, different data structures can be used that allow items to be stored, retrieved and deleted from the structure. The goal of the data structure is to allow these actions to be performed in an optimal manner.
Q: Why can't everything just be stored in unsorted Arrays?
A: Every time you want to retrieve an item, the computer will need to search through the whole array until it find the item.
Q: OK, so keep all the keys in the array sorted, and then find them quickly with Binary Search.
A: This would work if you have unchanging data that just needs to be set up once. However, a sorted array isn't a good choice if you need to add items too, since the whole arrays constantly needs to be shifted around. instead, we can use other structures, such as the Binary Search Tree.
End of Free Content Preview. Please Sign in or Sign up to buy premium content.
Comments
mike
Aug 18, 9:54 AMstatic class Node{
Node left;
Node right;
int key;