Questions about search trees, a class of data structures used for storing sorted data for efficient access.

learn more… | top users | synonyms

-1
votes
0answers
4 views

Proving number of internal nodes in the subtree rooted at any node x of Red Black trees

Reading Lemma 13.1 from the book Introduction to Algorithms, 3rd Edition To prove: A red black tree with n nodes has height at most 2 lg(n+1) First it attempts to prove : the subtree rooted at any ...
0
votes
0answers
32 views

Implementing BTrees without pointers

I am trying to implement a BTree in a pointer-free language as a proof-of-concept. However, a question came to my mind: every time I need to split a node, I need to do a deep copy of all the nodes in ...
1
vote
1answer
99 views

Term for binary search tree using hashes?

I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, ...
0
votes
2answers
90 views

B-Tree and how it is used in practice

I understand what a B-Tree is (I already implemented a B-Tree in Java with insert and delete methods that preserve the invariant). However I do not understand exactly how it is used for example for ...
1
vote
1answer
36 views
1
vote
2answers
58 views

Don't understand one step for AVL tree height log n proof

I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand. Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since ...
-4
votes
1answer
35 views

Implement “from” function for AVL Tree java

I posted this same question on stackoverflow but I think it might be better suited here as I am having trouble with coming up with an algorithm with O(log(n)) running time. Question: I am ...
-1
votes
2answers
55 views

Is there only one optimal BST?

as i read some material about Optimal BST, i ran into a trouble. for following key i find two optimal BST with Average Cost = 30. 1 optimal BST using Dynamic programming Algorithm and 1 by hand ! ...
-3
votes
1answer
59 views

Building a Red Black tree out of a sorted array [closed]

If I have a sorted array of size $n$, can I build a Red Black tree out of it in $O(n)$ time in a different algorithm rather than splitting the tree in half every time or the straightforward way that ...
2
votes
1answer
84 views

(AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees? [duplicate]

Question: If an AVL tree has height h (assume h ≥ 2), what is the maximum possible difference between the number of nodes in its two subtrees? Prove your answer. Your answer should not use big-Oh or ...
0
votes
1answer
45 views

Top Down Insertion in a B Tree

I have a B-Tree of order 5. So the keys are between $\lceil n/2 \rceil- 1 \leq keys \leq n - 1$ and children are between $\lceil n/2 \rceil \leq children \leq n $. Am I doing it right? So a full node ...
0
votes
1answer
23 views

red black tree and 2-3-4 tree isomorphism

Are all cases of addition and removal in 2-3-4 trees isomorphic to cases of addition and removal in red black trees?
1
vote
2answers
52 views

Minimising height of a 2-3-4 tree

I'm wondering how a set of keys could be assigned to nodes in a 2-3-4 tree in order to minimize the height of the tree? Does the sequence of insertion matter with 2-3-4 trees?
3
votes
0answers
71 views

Finding a successor in a binary search tree in $O(1)$ [closed]

In my algorithms course I have learned about the binary search tree and its functions add, find and remove. I have also learned about how to find the successor and the predecessor in a balanced binary ...
1
vote
1answer
21 views

Inserting a sentence into search trees

Let's say you have the following sentence: "This is my first cs question posted here". How would I go about inserting the sentence into a search tree. Do I assign each word a number value and perform ...
1
vote
0answers
46 views

kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees ...
1
vote
2answers
81 views

Why should leaf nodes in a red-black tree be black?

From the property of Red-Black Trees we know that: All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms") But what is the reason that we ...
1
vote
1answer
38 views

Help in geometrically understanding “Linear Decision Trees”

In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as defining a hyperplane in $R^n$. Thus, tracing a path through the tree computes ...
1
vote
0answers
32 views

Binary search tree with $n$ internal vertices [closed]

How can we prove a binary search tree with $n$ internal vertices has height $h = \lceil \log(n+1) \rceil$?
-1
votes
1answer
223 views

AVL Trees - Maintaining Closest Pair information on a Delete [duplicate]

In the accepted answer to my question Data Structure For Closest Pair Problem, I do not see why deletion works. Let's say (x, y) are the closest pair before the delete. If the node to be deleted is ...
1
vote
0answers
41 views

LLRB Tree How to prove if left and left of left node are black, then this node must be a red node?

Im learning the delete operation on Left-leaning Red Black Tree invented by Prof. Sedgewick. In delete operation, a node could be only deleted from a 3-node or a 4-node but 2-node. In order to ensure ...
1
vote
1answer
27 views

Understanding expected time bound for unsuccessful search in R-way tries

As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log_R N)$. Can someone please ...
-1
votes
1answer
54 views

Case distinction in B-tree deletion

Here is how deletion in B-trees is described: If the key k is in node x and x is a leaf, delete the key k from x. If the key k is in node x and x is an internal node, do the following. ...
1
vote
1answer
43 views

Doesn't post-order traversal require subtrees to be evaluated separately?

Consider this tree: If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in ...
2
votes
2answers
212 views

Artificial Intelligence: Condition for BFS being optimal

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that: breadth-first search is optimal if the path cost is a nondecreasing function of ...
1
vote
1answer
327 views

Why is Iterative-deepening A* optimal, even without monotonicity?

Why is it that Iterative-deepening A* is optimal, even without monotonicity? How can I be sure that the first goal reached is the optimal one?
0
votes
0answers
128 views

Updating an AVL Tree Based On Balance Factors

I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it? Background: Let the balance factor ...
1
vote
1answer
154 views

Does inserting and immediately removing a node change a red-black tree?

I have the following problem: Does inserting a node into a red-black tree and then immediately deleting it always result in the original tree? Prove that it does or give a counter-example if it ...
0
votes
0answers
58 views

What is time complexity of in-order depth-first iteration over keys in a B-tree?

I can't figure out or find on the Internet what is the time complexity of B-tree in-order depth-first iteration. Can you help me out here, please? What is the characteristic operation we're using to ...
3
votes
0answers
105 views

Expected depth of modified kind of treap

If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
1
vote
1answer
132 views

finger search on a red black tree

I'm having trouble finding materials on what 'finger search' is, in the context of a red black tree. Even Wikipedia has a very short page about that, could you refer me or explain what kind of search ...
6
votes
3answers
518 views

What data structure would efficiently store integer ranges?

I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following: Insert a new integer Insert a range of contiguous integers Remove an integer Remove all ...
4
votes
2answers
636 views

Joining two red-black trees

I have two red-black trees $T_1$ of black height $H_1$ and $T_2$ of black height $H_2$ such that all the nodes $N$ belonging to $T_1$ are less than (in value) all the nodes $N$ of $T_2$ and a key ...
2
votes
1answer
211 views

How does insertion work in an AVL tree?

From the above image, while trying to maintain an AVL tree data structure, how would the tree look after inserting the value 10? Also, if anyone has any suggestions or simple method of rotating, ...
5
votes
2answers
98 views

Where are M-Trees applied in practice?

My similarity search seminar topic are M-trees. I would like to give some examples about where they are practically applied, but I can't find anything googling. Does someone know if M-trees are ...
4
votes
3answers
121 views

“Last Come => More Relevant” data structures

As I think of data structures I studied and dealt with, they are all optimized to retrieve/put a random element, to perform optimally based on unspoken assumption that each element has equal odds of ...
5
votes
2answers
125 views

Binary Search Tree: Replace $k$ min elements with their average

Given a valid binary search tree whose keys are unique real numbers, and a set of $k$ pointers to the $k$ minimum elements in the tree, will the BST property be maintained if I replace all $k$ ...
-1
votes
1answer
95 views

Find node with key of at least n in a binary search tree

Working on a project for my Data Structures class. I've implemented a Red/Black tree in Java. One of the operations required of the data structure is "find a node which has a key of at least n". The ...
0
votes
2answers
279 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 ...
4
votes
1answer
159 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
125 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
85 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 ...
7
votes
4answers
302 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 ...
6
votes
1answer
247 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 ...
0
votes
2answers
159 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
522 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
385 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
214 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 ...
7
votes
2answers
1k 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. ...
7
votes
2answers
151 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 ...