Questions about search trees, a class of data structures used for storing sorted data for efficient access.
1
vote
1answer
49 views
Searching and inserting in $O(n)$ when $n$ is the size of the key
Edit: The solution to my problem is called a trie ; according to Section 8.1 of Peter Brass book "Advanced Data Structures", for a given alphabet $A$ and a word $w$ of length $n$ on this alphabet, a ...
1
vote
1answer
27 views
3
votes
2answers
312 views
Time Complexity to find height of a BST
Below is a question I was asked in an Interview
What is the best case time complexity to find the height of a Binary Search Tree?
I answered it explaining using the below algorithm
$\mathrm{...
1
vote
0answers
17 views
Example of binary trees with maximum rotation distance
In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them ...
2
votes
0answers
33 views
Analysis expected depth of a binary search tree given random values?
I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
0
votes
0answers
27 views
How many roots are there in an undirected root
Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
1
vote
0answers
17 views
Search tree with associative union and worst case insert/delete better than O(n)? [duplicate]
Is there a search tree where union is associative, so $a \cup (b \cup c) = (a \cup b) \cup c$ gives a tree with the same structure?
A complete binary tree would be such a tree, but for example a red-...
0
votes
0answers
14 views
Find optimal path in BFS and DFS
In UCS it is clear that we find the cheapest cost path. In BFS and DFS we can get the order of output nodes. But How can we find the optimal path in BFS ans DFS in following cases?
0
votes
0answers
17 views
Generation vs expansion BFS
I can not understand the difference between generation and expansion of nodes. How the time and space complexity of BFS are different in each two scenarios?
...
2
votes
0answers
11 views
Segment-tree construction: do we recurse into both children?
This question is about segment-tree as described in this Wikipedia article.
When constructing the tree (inserting the new input-interval), if the input-interval doesn't contain the node-interval we ...
0
votes
1answer
54 views
Optimal data structure for sorted list
Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)".
Even though B-trees are a generalization ...
3
votes
1answer
63 views
Can ropes (AVL trees) be interned?
Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time?
I recently implemented a rope ...
2
votes
2answers
59 views
Infix search in millions of strings
Let's say we have millions of strings (each of them < 100 characters):
alpha
allo
blah
hello world
orlando
...
I know how a binary search tree or a trie can ...
1
vote
0answers
24 views
Number of AVL trees with maximum height
If you have a set of n distinct elements, is there any kind of formula to get how many possible insertion sequences would result in an AVL tree of maximum height?
0
votes
1answer
50 views
All possible Red Black Trees with this set {1,2,3,4,5}
I have to write all possible Red Black Trees which can represent these 5 numbers {1,2,3,4,5}.
Now we have 120 ways to write 1,2,3,4,5
...
1
vote
1answer
45 views
how does rotation works in AVL trees and what is a good way to understand it?
If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 ...
0
votes
1answer
143 views
How to calculate number of nodes opened by BFS?
In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I
I know that the equation for BFS is
b1 + b2 + ...... + (bd+1 - b)
Where b is ...
1
vote
1answer
28 views
data structure admitting top items with prefix
A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and ...
0
votes
0answers
28 views
proof of time complexity $O(i)$ of calling successor $i$ times in AVL tree when starting from the minimum node?
This question related to this one, but not the same.
I'm sure that the time complexity is $O(i)$ and my intuitive way to proof it is that for any expensive action ($O(logn)$) like from finding the ...
0
votes
0answers
76 views
Time complexity of inorder run on B+ tree (without leavesa link)
I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each ...
0
votes
0answers
56 views
Time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder
I'm looking for time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder run. when $h$ is the height of the tree.
0
votes
0answers
26 views
Unusual function - operations on lists / sets - possible optimization
I have a problem.
Below I present a function in Python.
...
1
vote
0answers
79 views
Deletion of record from B+ tree
I was going through the B+ tree deletion operation from the book Database System Concepts, 6th Edition by Henry F. Korth. One particular thing caught my attention.
A B+ tree is given. We have to ...
0
votes
1answer
78 views
Avarage height of Red-Black tree [closed]
I wrote a program to discover how height of the tree is relative to the number of elements in the tree (nodes).
On first test I filled array with 10-50-100-200...-1000 elements of random numbers from ...
0
votes
1answer
172 views
How many node does the final B-tree have?
I'm currently studying the B-Trees chapter of Introduction to Algorithms. One of the question from the chapter is:
Suppose that we insert the keys $\{1,2,...,n\}$ into an empty B-tree with minimum ...
1
vote
0answers
63 views
Iterate over two different non-binary tree graph [closed]
I'm working to solve a problem based on two non-binary tree graphs, that they need to be iterated together in order to find a valid combination.
I did a basic implementation that works, but it have a ...
0
votes
0answers
34 views
Understanding B tree key deletion step from CLRS algorithm
CLRS explains B tree key deletion as follows:
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 ...
3
votes
1answer
63 views
How to validate a connect X game (Tick-Tak-Toe,Gomoku,…)?
Currently I am working on a Gomoku AI (or generally Connect-X games).
Implementing the search tree was no problem, but then I got to the point where I had to implement the value function and was ...
0
votes
1answer
141 views
return a key of a node with maximum value within a range of keys in B+ tree
I've been asked a question about B+ Tree.
The question is: Suppose we have object of the following type:
...
0
votes
1answer
58 views
How to delete element from B*-tree?
Every article on web (and books I have checked) gives detailed explanation on insertion operation in B*-trees but most of them don't even mention deletion (or if they do they just state that it's ...
0
votes
0answers
39 views
Comparison of Depth First Search Trees
Does anyone know of an algorithm who is able to return how similar a DFS Tree is from another DFS Tree? (Or any kind of tree in general)
I'm not looking for a true or false. Instead, I would like it ...
0
votes
0answers
24 views
AVL Tree Inner Nodes
If k is the height of an AVL Tree, the minimal number of inner nodes is:
N(k) = N(k-1) + N(k-2) +1.
Why is this formula true?
0
votes
0answers
64 views
Show that the successor of a node is the lowest ancestor of the node whose left child is also an ancestor of that node
Consider a binary search tree $T$ whose keys are distinct. Show that if the right subtree of a node $x$ in $T$ is empty and $x$ has a successor $y$, then $y$ is the lowest ancestor of $x$ whose left ...
0
votes
0answers
40 views
AVL vs (2, 3) vs (2, m) trees
I understand the difference in how to use AVL/(2, 3)/(2, m) trees but when would you use one method vs another? Thank you
1
vote
1answer
84 views
What do we benefit from using ternary search trees rather than binary search trees?
Ternary search trees are very common in the text editing area. They could be used to implement Auto complete feature, spell checking, Partial-Match searching, Near-Neighbor Searching & many many ...
2
votes
0answers
204 views
Tight upper bound on height of a red-black tree
"Introduction to Algorithms" by Cormen et al., 3rd edition, Lemma 13.1 states that
A red-black tree with $n$ internal nodes has height at most $2\log(n+1)$,
i.e. $h \le 2\log(n+1)$.
Can equality ...
1
vote
1answer
33 views
Is it possible to obtain dynamic tree with two dimensions in big matrix
Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions).
In some of the coordinates of the matrix ...
0
votes
0answers
47 views
Average solutions in infinite search tree
I have the following problem:
Consider a balanced infinite search tree with branching number $κ$. Consider a
search problem with solutions which may be located at any node of the tree.
The ...
0
votes
1answer
273 views
How is the data stored in AVL tree in a memory? [duplicate]
I have been struggling to visualize how is the AVL tree is stored in memory?
Does it store data in array or list, If so how is it connected with its child and parents.
0
votes
1answer
666 views
Maximum depth of a B+ tree
Given $K$...# key values, $n$...# pointers in a node.
I read somewhere, that the maximum depth is defined as $\lceil\log_{\...
0
votes
1answer
43 views
Check if current interval is overlapping some intervals, or is being overlapped
Let's say we have array of $K$ integers, and we have given $N$ intervals in the form $l_{i}, r_{i}$, both inclusive, the interval $i$ means that all elements in the range $[l_i, r_i]$ are covered. Our ...
3
votes
1answer
177 views
AVL tree partition
The statement sais the following
Design a function to partition an AVL tree such that, given an AVL tree and a key $x$, it returns two AVL trees, one containing the keys lower or equal than $x$, ...
3
votes
1answer
156 views
What is the branching factor for nondeterministic games?
Given a nondeterministic game how could one know the branching factor of it? Is it the number of all possible outcomes?
I have an example game in which you have some cards. The goal is to get rid of ...
2
votes
2answers
452 views
What are drawbacks of Tree Sort algorithm (with balanced tree) vs Tree Sort (with unbalanced tree)?
Tree Sort algorithm with unbalanced tree may yield $O(n^2)$ worst-case time complexity/performance. But Tree Sort algorithm with balanced tree guarantees $O(n\log n)$ worst-case time performance.
So ...
1
vote
0answers
60 views
Advantage of bulkloading in a B-Tree
https://en.wikipedia.org/wiki/B-tree#Initial_construction
Currently I know of 2 ways for building a B-Tree : bulkloading and just inserting key after key.
In the wiki example the keys are sorted, ...
3
votes
1answer
49 views
Construct Optimal Directory Trees Efficiently
Question:
I want to construct a optimal directory tree structure to access $n$ ($n < 256$) elements using only the keyboard with as few key presses as possible. For this one could consider the ...
1
vote
1answer
216 views
BVL Balanced Tree
I have an issue about proving the next problem:
Let's define a BVL tree, which is a binary tree, who satisfied the feature that the difference between the heights of the children of a node, is at ...
0
votes
0answers
70 views
Treaps are expected weight-balanced?
In a previous question there was a definition of weight-balanced and a question regarding red-black trees.
This question is to ask the similar question, but for treaps.
The question is:
Is there ...
3
votes
1answer
41 views
Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$
Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child ...
5
votes
1answer
61 views
Make appends not degrade a splay tree
Splay trees offer armotized O(log n) access to tree elements. However, if you keep repeatedly appending elements to a splay tree, without splaying any other elements, it degrades into a linked list ...
