Newbe Dev Stack

Answer : One advantage that no one else has pointed out is that binary search tree allows you to do range searches efficiently. In order to illustrate my idea, I want to make an extreme case. Say you want to get all the elements whose keys are between 0 to 5000. And actually there is only one such element and 10000 other elements whose keys are not in the range. BST can do range searches quite efficiently since it does not search a subtree which is impossible to have the answer. While, how can you do range searches in a hash table? You either need to iterate every bucket space, which is O(n), or you have to look for whether each of 1,2,3,4... up to 5000 exists. (what about the keys between 0 and 5000 are an infinite set? for example keys can be decimals) Remember that Binary Search Trees (reference-based) are memory-efficient. They do not reserve more memory than they need to. For instance, if a hash function has a range R(h) = 0...100 , then you need to allocate an array of...

Answer : Let's assume that width of the array is bigger than height, otherwise we will split in another direction. Split the array into three parts: central column, left side and right side. Go through the central column and two neighbour columns and look for maximum. If it's in the central column - this is our peak If it's in the left side, run this algorithm on subarray left_side + central_column If it's in the right side, run this algorithm on subarray right_side + central_column Why this works: For cases where the maximum element is in the central column - obvious. If it's not, we can step from that maximum to increasing elements and will definitely not cross the central row, so a peak will definitely exist in the corresponding half. Why this is O(n): step #3 takes less than or equal to max_dimension iterations and max_dimension at least halves on every two algorithm steps. This gives n+n/2+n/4+... which is O(n) . Important detail: we split...

Answer : AVL trees are intended for in-memory use, where random access is relatively cheap. B-trees are better suited for disk-backed storage, because they group a larger number of keys into each node to minimize the number of seeks required by a read or write operation. (This is why B-trees are often used in file systems and databases, such as SQLite.) Both the AVL tree and the B-tree are similar in that they are data structures that, through their requirements, cause the height of their respective trees to be minimized. This "shortness" allows searching to be performed in O(log n) time, because the largest possible number of reads corresponds to the height of the tree. 5 / \ 3 7 / / \ 1 6 9 This is an AVL tree, and is a binary search tree at its core. However, it is self-balancing, which means that as you add elements to the tree, it will restructure itself to maintain as uniform of a height as it can. Basically, it will not allow long branches. ...