16
votes
Why use binary search trees when hash tables exist?
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 ...
- 379
12
votes
Accepted
What is "rank" in a binary search tree and how can it be useful?
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 ...
- 3,048
11
votes
If inorder traversal of a tree is in ascending order will the tree definitely be a BST?
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 ...
- 7,038
10
votes
Why use binary search trees when hash tables exist?
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 ...
6
votes
Why use binary search trees when hash tables exist?
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 ...
- 161
6
votes
Accepted
Using pre-,post-, and in-order indexes to find information about a Binary Search Tree
Long story short: it is possible in constant time if the tree is a full binary tree. If not, there are some cases where there is not enough information to find the size of the subtree in constant time....
- 12.3k
5
votes
Balanced Binary Search Tree Two-Sum with Constraints
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 ...
D.W.♦
- 154k
5
votes
Why is Binary Heap never unbalanced?
You must refer to the definition of a Binary Heap:
A Binary heap is by definition a complete binary tree ,that is, all levels ...
- 1,195
5
votes
Accepted
Big O vs. Big Theta for AVL tree operations
This is a pedantic point which I suggest ignoring.
The intended interpretation of the "worst case" column seems not to be the worst-case complexity, but rather bounds on the complexity which ...
- 274k
4
votes
how does rotation works in AVL trees and what is a good way to understand it?
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: $...
- 29.6k
4
votes
Accepted
BST representation of Hash Tables
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 ...
4
votes
Accepted
Algorithm for searching in BST with only <
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 \...
- 632
4
votes
Algorithm for searching in BST with only <
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 ...
D.W.♦
- 154k
4
votes
Why is Binary Heap never unbalanced?
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 ...
- 1,659
4
votes
Accepted
Height of epsilon-balanced binary search tree
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 ...
- 274k
4
votes
is it possible to create an avl tree given any set of numbers?
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 ...
- 274k
4
votes
Accepted
is it possible to create an avl tree given any set of numbers?
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 ...
- 29.6k
4
votes
Accepted
finding an algorithm for creating a priority search tree in linear time with presorting
What you are looking for is essentially a Cartesian tree:
The Cartesian tree for a sequence of distinct numbers can be uniquely
defined by the following properties:
The Cartesian tree for a sequence ...
- 7,365
3
votes
What is the advantage of leaf trees vs. node trees?
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 ...
- 71.9k
3
votes
Data structure for handling intervals
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 ...
- 966
3
votes
Accepted
Why do we use multiple data structures?
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 ...
- 5,931
3
votes
Accepted
Should all internal node keys in B+ tree also be in the leaves?
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 ...
3
votes
Accepted
Facts about internal and external path lengths of binary tree
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 ...
- 274k
3
votes
Why use binary search trees when hash tables exist?
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 ...
- 27.8k
3
votes
Calculation of Inorder Traversal Complexity
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 ...
- 1,195
3
votes
in order of binary search tree
Remember that an in-order traversal lists the elements from left-to-right, descending the tree: Left, Root, and ...
- 31
3
votes
Accepted
Inorder tree tranversal on binary search tree doesn't give the elements in order?
This is not a valid binary search tree, since 26 is greater than 20 and is in its left subtree.
- 4,458
3
votes
Accepted
Splay Tree: Repeatedly searching for the same key that's not in the Tree
In a BST, a lookup for an key that isn't present traces out a path through that tree that ends at either that key's successor or that key's predecessor. We'll use this property to get the desired $O(m ...
- 9,027
3
votes
Accepted
Observations about the structure of an optimal Binary Search Tree
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 ...
- 274k
3
votes
Accepted
How does the Inorder-tree-walk algorithm move to a different node after hitting a leaf?
To understand what happens "when we hit the node with the key 11", let us isolate the call Inoder-tw(node17), which executes the following.
...
- 38.5k
Only top scored, non community-wiki answers of a minimum length are eligible