The Stack Overflow podcast is back! Listen to an interview with our new CEO.
13

The most obvious answer is that trees can be traversed in their natural order very efficiently. If you need to visit every element of a dictionary in alphabetical order, a tree can support this directly, where a hash table cannot. Another answer is that trees can be made immutable - where insertion and deletion only involve recreating a small number of ...


11

According to this book (Chapter 3.2), a node in a BST has rank $k$ if precisely $k$ other keys in the BST are smaller. So, if you order all the BST nodes according to their keys, then each node with rank $k$ will take $k$-th place.


9

Binary search trees (BSTs) of various sorts and their variations are widely used data structures today, so they are hardly a "historical note". For example, both the .NET Framework and the Java Standard Library provide a tree-based implementation of a dictionary. A red-black tree no less in the latter case. One of the reasons for this is that tree-based ...


9

Yes. The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST assumption; let's call this node $v$. Now, there are two ways $v$ could break the BST assumption. One way is if there's a node in $v$'s left subtree with label ...


5

I don't know how to do this is in $O(n)$ time and $O(1)$ space, but I can show you how to do it in $O(n)$ time and $O(\lg \lg n)$ space. In particular, given any tree of depth $O(\lg n)$, I'll show how to do an in-order traversal in $O(n)$ time and $O(\lg \lg n)$ space. That will be enough to solve this problem. Warmup Let me first establish some ...


5

You are right now thinking of a data structure from which just three operations are expected, Insertion Lookup Deletion But if you extend these range of operations, to let's say finding number of elements greater than a certain value, one can see how BST's can be useful. A BST can still manage this operation in $\log n$ time but a hash table can't. ...


4

If what you mean is that you want to build a BST and you only have the $<$ operation, and you only know the algorithms with the $\leq$ operation, you can notice that : $$a \leq b \Leftrightarrow \neg (a > b)$$ $$\Leftrightarrow \neg(b < a )$$ Hence, using a negation in the right place, you can build your usual algorithm.


3

Aspects other than asymptotic worst case time are also important. For example Actual speed in practice Memory consumption Implementation difficulty Algorithmic analysis almost never tells you the complete story and never should be used to justify blanket statements like "this data structure is the best if you need operations x,y,z".


3

The internal keys come from values also stored in leaves, but if you allow deletions, the value could be deleted from the leaf after it is created and used in the internal node. Deleting the value from a leaf won't change any internal nodes, unless the leaf becomes underfilled. With the insertion you list, it would have the property you are thinking of if ...


3

The two disadvantages of hash tables: 1. They don't support ordering. Search trees naturally support processing all items in sorted order, or processing all items in some range. 2. The speed will depend on the speed of the hashing function, which may be rather slow. One brutal approach that I have seen recently is a datastructure that just uses an unsorted ...


3

One needs three subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other. The operation can be seen as a associative property: $T_1\;p\; (T_2\; q\; T_3) = (T_1\; p\; T_2)\; q\; T_3$ of the inorder traversal of the nodes in a binary tree. Both the left and right diagram have the inorder $\...


3

What the author means by implementing a HashTable as a BST is simply implementing a BST with $insert(), \space delete() \space and \space search()$ with slight modifications The node of the BST would have the following structure. $Node \space := (Key,Value)$. Insert a key-value pair by performing comparisons on the keys of two different pairs. Avoids nodes ...


3

You can test whether $a=b$ as follows: if it's not true that $a<b$ and not true that $b<a$, then it follows that $a=b$. (Disclaimer: this requires that it be possible to order all of the elements using $<$, i.e., $\le$ be a total order. I imagine you were assuming this. But if it's not, you're screwed anyway and the problem is not solvable -- ...


3

You must refer to the definition of a Binary Heap: A Binary heap is by definition a complete binary tree ,that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right. It is by definition that it is never unbalanced. The ...


3

Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's $n$ nodes. For the second vertex, it's at most $\epsilon n$ nodes. For the third vertex, it's at most $\epsilon^2 n$ nodes. For the $t$'th vertex, it's at most $\epsilon^{t-1} n$ nodes. If the path has ...


2

I'm assuming the following model for a binary search tree of size $n$. Consider the following infinite process. At step 0, we have the empty tree. At step 1, we have the tree having some arbitrary value at the root. At step $m>1$, if the current (ordered) contents of the tree at the previous step are $x_1<\ldots<x_{m-1}$, we choose an interval ...


2

I believe you are correct. The hard part is convincing yourself why this is true, I guess. The key to the riddle is the root. preorder, postorder and levelorder all have the root at first or last position. Once the root is known all elements smaller go in the left subtree and those larger go right. Thus reconstructing the tree from its order is a recursive ...


2

The Range Tree is made from the input array. The array is sorted and then the tree is built. This means that in the standard construction we have started with the array, this may indicate the leaves. And this BST comes from the sorted array, so there is no point in changing it to e.g. self-balancing trees in the standard case and if there are modifications ...


2

If you knew the distribution of $n^*$, you could find an optimal binary decision tree (there are several $O(n\log n)$ algorithms) in terms of expected number of queries (you can't beat binary search if you care about worst case). There are also two simple algorithms which are nearly optimal. I will describe them as algorithms for locating $n^*$ given queries ...


2

In a BST we can't say anything regarding the order of elements that are on separate sides of a node (e.g. 4 and 8, because they are on separate sides of node 6), however, we know that if a node is a parent of another node, it must have been inserted before it. So 6 is always going to be the first element. Then either 4 or 7 can come (two choices). Then if ...


2

Actually the test is quite easy. If you consider the subsequence of numbers greater than the final number $363$, this sequence is supposed to decrease. Thus, in the case of $e: 925, 202, 911, 240, 912, 245, 363$, the subsequence is $925, 911, 912, 363$ and we see the problem. Why is that so? If we see a number $x$ larger than the target $363$, we are ...


2

Apparently, you want to rebalance the AVL tree. You can either do a simple left rotation or a right-left rotation. I prefer not to mention right-right rotation since that term is misleading and ambiguous. You can visualize what is happening. Go to AVL tree visualization, a page created by David Galles. Insert 2, 1, 4, 3, 5 in that order. Now look ...


2

Here is a natural approach to explore the extreme case. Let node $r$ be the root of a red-black tree. Let its left subtree be a red-black tree of black height $h$ that has the minimum number of the nodes among red-black tree of the same black height. Let its right subtree be a red-black tree of the same black height $h$ that has the maximum number of ...


2

Consider a constant set of $k$ insertions done directly at the max node, and the left and right sub-trees of the root node ($L$, $R$). If each rebalancing operation required only constant time, then only $O(\frac{log(n)}{k})$ of the inserted elements could be in $L$, since the maximal element is a leaf and the tree is balanced. While this simple analysis ...


2

The question is a little confusing, since a binary heap is usually implemented in an array, not a tree. The tree is used for visualization. Consider the following heap: It is given by the following array: $H=[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]$ Since a complete binary tree corresponds to an array, the opposite also holds. New elements are added to the ...


1

The number of trees with $n$ nodes of height $n-1$ is $2^{n-1}$. Indeed, every internal node has exactly one child, which can either be the left child or the right child. Since there are $n-1$ internal nodes, this gives $2^{n-1}$ options.


1

It would be $O(n^2)$ in the worst case. Suppose root of BST is $15$, all left nodes are $7$, and all right nodes are $21$. We want to find all pairs which their sum is $28$. Hence, you should report all $\frac{n}{2}\times \frac{n}{2}$ items (all left nodes with all right nodes). Hence, your algorithms should report $O(n^2)$ pairs in the worst case.


1

Instead of the classical $k$-means algorithm where you classify all points and then update the center of each cluster to be the average of all points of that cluster, you could use the sequential variant of $k$-means: centers = random(k) while True: p = next_point(points) c = find_center(centers, p) c = c + a * (p - c) next_point iterates all ...


1

Use a hash function. Since you have less than $2^{16}$ words, if you use a hash of 32 bits then you are likely to not have any collisions. If you do get collisions, you can try varying the key (hashes usually use some magic numbers, which in some cases are known as keys), or you can just use a longer hash. Another possibility is to store the dictionary as a ...


Only top voted, non community-wiki answers of a minimum length are eligible