01:198:112 Lecture Notes - Lecture 7: Binary Tree, Binary Search Algorithm, Linear Search
Document Summary
Given there is enough space, it will always be constant time as you have access to any part of the array directly. If you want to insert something into the front, you will have to first move everything over and then insert, which would take n time. While linear search is too slow and using binary search for insertion is too slow, we can use binary search trees for better efficiency. Trees are upside down with the root being at the top. At the top is the root node. The root node starts at depth 0, each branch towards a new lower node adds a depth level. The root can branch to the left and right to create new nodes that can also branch left or right to create new nodes as well i. e. subtrees. At the bottom of each path there are leaf nodes, which represent the final nodes for said path.