Tag Info

14

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 ...

12

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.

11

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 ...

10

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 ...

6

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. ...

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 ...

4

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 $\... 4 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 ... 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. 4 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 -- ... 4 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 ... 4 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 ... 4 AVL trees are a kind of binary search trees. As such, they implement the following operations, among else: Initialize an empty tree. Add a value to the tree. Remove a value from the tree. Search a value in the tree. Try to use some of these operations to answer your question. 4 Your question is not the right one. An AVL tree is a binary tree that has additional properties. First it is a search tree, which means we can easily find each number in the tree. Second it is balanced, meaning that there are no leafs very far form the root. (Formal definitions on request.) Assume you have a set of$n$numbers in advance, and an arbitrary &... 3 You don't quote the reasoning of P. Braß, if he gives any, so we can only guess. I would like to distinguish two cases. Data are stored as values, i.e. in place. Data are stored by reference. In the first case, the size of the "inner" tree would blow up arbitrarily. For every step in the search, we would have to load a potentially big node into the cache. ... 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 In order to analyse the time complexity of a tree traversal you have to think in the terms of number of nodes visited. If a tree has$n$nodes, then each node is visited only once in inorder traversal and hence the complexity is$O(n)$. Here, the input is in terms of number of nodes in the tree and hence the complexity. The notion that each recursive call is ... 3 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 ... 3 Remember that an in-order traversal lists the elements from left-to-right, descending the tree: Left, Root, and Right. This means that starting from the root (a), we will traverse the whole left branch, then print a, and finally traverse the right branch. You started off correct; however, your mistake was that you put m beforee h. It is an easy mistake to ... 3 This is not a valid binary search tree, since 26 is greater than 20 and is in its left subtree. 3 Let us prove by induction on depth that for every node$v$, there exist$a_v,b_v$(possibly$\pm \infty$) such that the input$x$reaches$v$iff$a_v < x < b_v$. This is true for the root since we can take$a_r = -\infty$and$b_r = +\infty$. Now suppose that it is true for some node$v$, and let$v_<,v_>$be its two children. Suppose that node$...

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

Since all intervals are non-overlapping, the use of an interval tree is unnecessary. We will store our intervals in an AVL tree $T$ sorted by start points and use the fact that bulk deletion of a set of contiguous keys $q_i,...q_{i+k-1}$ can be done in $O(\log n + \log k)$ amortized time (see non-open access and open access). Let $x=[a,b)$ be an interval ...

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

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 ...

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