Binary Search Tree

Optional Node
Premium 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

  • static class Node{
    Node left;
    Node right;
    int key;

        Node(int key){
            this.key = key;
        }
    }
    
    static void doStuff(int[] ar){
        Node top = ar2SortedTree(ar);
    
    cont...
Contact Us
Sign in or email us at [email protected]