Questions about search trees, a class of data structures used for storing sorted data for efficient access.
0
votes
2answers
53 views
Worst case scenario in binary search tree retrieval
Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$).
What is the number of comparisons that will occur in the worst case scenario, if we ask ...
3
votes
1answer
43 views
van Emde Boas tree: why store max recursively?
In both CLRS (third edition) and Erik Demaine's lecture, the van Emde Boas tree is defined to store max but not min recursively. ...
1
vote
1answer
38 views
Sequential hash tree traversal
A lot of articles say that hash tree traversal cost to any randomly chosen leaf is $\mathcal{O}(\log_2 N)$ ($N$ is a number of leafs) and that is right. If we have a tree of 8 leafs it will take us at ...
2
votes
1answer
37 views
Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$
We're asked to prove the above mentioned lemma but I having a hard time proving this rigorously.
We did prove that given $n$ values AVL's height is $\Theta\left (\log \left ( n \right ) \right )$ So ...
6
votes
2answers
118 views
Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?
The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an ...
5
votes
1answer
89 views
Is there a binary search tree datastructure which can avoid becoming badly weight-balanced?
This is a follow-up question of "Not all Red-Black trees are balanced?" and "AVL trees are not weight-balanced?".$\def\le{\leqslant}\def\ge{\geqslant}$
Definition: For a rooted tree $T$ and a ...
1
vote
2answers
59 views
Did I correctly prune this min-max search tree using alpha-beta pruning?
I am studying some old past test questions. Is this search tree correctly pruned?
3
votes
2answers
76 views
Finding no. of leaf nodes for each node in a BST
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is
$\qquad ...
3
votes
1answer
86 views
AVL tree with fixed height and as few elements as possible
I have been reading about AVL trees, at the moment I'm trying to figure out how to determine the height of a tree and how to draw an AVL tree of some height with minimum number of elements.
In a ...
3
votes
1answer
75 views
Number of possible search paths when searching in BST
I have the following question, but don't have answer for this. I would appreciate if my method is correct :
Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
5
votes
2answers
178 views
Colour a binary tree to be a red-black tree
A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition).
I was wondering if we can do something similar with Red-Black trees.
...
6
votes
2answers
102 views
Are probabilistic search data structures useful?
A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these ...
4
votes
2answers
146 views
Uniform-cost Search Problem
Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem?
Definitions: ...
2
votes
1answer
104 views
B-tree branching factor boundaries
A BTree has a $k$ value that determines that every node has $k$ to $2k$ children. When a node has $2k$ keys it needs to be split into two nodes.
Let's say I want to create a $k/(2k-x)$ tree. (like a ...
2
votes
1answer
71 views
Height of AVL after entries
Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$
elements. After the insertion of $n^2$ elements, what would be its
height?
My idea: the height of an AVL tree ...
2
votes
1answer
397 views
What is the time complexity of calling successor $n$ times during tree traversal?
According to some sources, the time complexity of finding the successor of a node in a tree is $O(h)$. So, if the tree is well balanced, the height $h=\log n$, and the successor function takes time ...
1
vote
1answer
97 views
Can you have a binary search tree with O(logn + M) property for the following case
Let $n$ be the number of strings which are sorted in lexicographical order and stored in a balanced binary search tree. You are provided with a prefix $x$ of which $M$ strings have the prefix $x$. I ...
1
vote
1answer
564 views
Nim game tree + minimax
Problem : Two players have in front of
them a single pile of objects, say a stack of 7 pennies. The first player divides the original
stack into two stacks that must be unequal. Each player ...
0
votes
1answer
36 views
Can you have three consecutive black nodes in red-black search tree?
Suppose I am making a red-black search tree, and in my right subtree, I have a black node, then a red node, and it has two black children, the black children further black childrens. As such a lemma ...
0
votes
1answer
402 views
Proof that a randomly built binary search tree has logarithmic height
How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't ...
3
votes
1answer
337 views
Explanation of recursive structure of Van Emde Boas Tree
From Van Emde Boas trees lecture:
We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of
a bit vector, but shrink the universe size recursively by a square
root at each ...
3
votes
1answer
484 views
Average number of comparisons to locate item in BST
This is a GRE practice question.
If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items ...
2
votes
2answers
211 views
Binary Search Tree Property
In the book 'Introduction to Algorithms 3/e', I have found the following definition of Binary Search Tree property:
Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree
...
16
votes
1answer
379 views
Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.
I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
3
votes
1answer
230 views
Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?
I've been given the following problem:
Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$:
$\text{Insert}(x)$ – add $x$ to $S$
...
7
votes
2answers
480 views
Hashing using search trees instead of lists
I am struggling with hashing and binary search tree material.
And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
11
votes
1answer
614 views
Why does the splay tree rotation algorithm take into account both the parent and grandparent node?
I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why ...
6
votes
3answers
566 views
Logarithmic vs double logarithmic time complexity
In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ?
This is the case when one use for instance van Emde Boas ...
11
votes
2answers
354 views
Creating a Self Ordering Binary Tree
I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the ...
8
votes
1answer
931 views
AVL trees are not weight-balanced?
In a previous question there was a definition of weight balanced trees and a question regarding red-black trees.
This question is to ask the same question, but for AVL trees.
The question is, ...
14
votes
2answers
800 views
Not all Red-Black trees are balanced?
Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes.
Of course, when we talk about red-black trees*(see ...
