Binary Search Trees(BSTs)

A Problem with arrays is adding and deleting elements to an arrays is computationally expensive, particularly when the array needs to stay sorted. BSTs are similar to arrays in that the keys are in a sorted order but they are easier to perform insertions and deletions into. But BSTs require more space than arrays.
The key lookup, insert, and delete operations for BSTs take time proprotional to the height of the tree, which can in worst case be O(n), if inserts and deletes are naively implemented. However there are implementations of insert and delete which gurantee the tree has height O(logn). These requires sorting and updating additional data at the tree nodes. Red-black trees are an example of such balanced BSTs and they are used in the C++ STL library to implement sets.

BSTs are different from trees. Specifically, in a BST, there is positionality as well as order associated with the children of nodes. Furthermore, the values stored at nodes have to respect the BST property - key stored at a node is greater than or equal to the keys stored in the nodes of its left subchild and less than or equal to the values stored in the nodes of its right subchild.

Below is video lecture related to red-black tree.

Hashing

Hashing is another approach to searching. The idea of hashing is to store keys in an array of length m. keys are stored in array locations based on the "hash code" of the key. The hash code is an integer computed from the key by a hash function. If the hash function is chosen well, the keys are distributed across the array locations uniformly randomly.

There is always the possibility of two keys mapping to the same location, in which case a "collision" is said to occur. The standard mechanism to deal with collisions is to maintain a linked list of keys at each location. Look ups, inserts, and deletes take O(1+n/m) complexity, where n is the number of keys. If the "load" n/m grows large, the table can be rehashed to one with a larger number of locations; the keys are moved to the new tables. Rehashing is expensive.

One disadvantage of hashing is the need for a good hash function.


Here below is lecture which discuss hashing in details.

Free Online Learning

Here are few site links which provide on line learning for free. They distribute lectures and notes for free.
You can see lectures of your interest and increase your knowledge.

NPTEL provides E-learning through online Web and Video courses in Engineering, Science and humanities streams.
http://nptel.iitm.ac.in/

MIT OpenCourseware - contains lectures and notes provided by MIT professors.
http://ocw.mit.edu/index.htm

Coursera contains lectures provided by prof of some of the good university of US.
https://www.coursera.org

You can also find a large set of video lectures shared on you tube.
Below are few you tube links.
http://www.youtube.com/user/StanfordUniversity
http://www.youtube.com/user/Harvard
http://www.youtube.com/user/UCBerkeley
http://www.youtube.com/user/nptelhrd

Security tube- contains lectures and demo related to hacking, information security, wireless security, hacking tools etc.
http://www.securitytube.net/

videolectures.net

learnerstv.com

Khan Academy - contains teaching materials related to  mathematics, history, healthcare and medicine, finance, physics, chemistry, biology, astronomy, economics, cosmology, organic chemistry, American civics, art history, microeconomics and computer science
http://www.khanacademy.org/

Google also provides learning tutorials that are present at site mentioned below. These contains lectures, presentations, assignments shared by some US Grad College Professors and some Google employees.
http://code.google.com/edu/


itunes U

Itunes U is an application provided by apple for your your iphone, ipads, ipod touch using which allow you can download lectures and read it on your iphone, ipads, ipod. you can gain access to these lectures on your personal computers too via installing itunes on your computer.