Questions tagged [search-trees]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
167 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
680 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
39 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
215 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
110 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
27 views

Unusual function - operations on lists / sets - possible optimization

I have a problem. Below I present a function in Python. ...
1
vote
0answers
310 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
158 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
3k 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
154 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 ...
1
vote
1answer
201 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
221 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
318 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
0answers
53 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
41 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?
1
vote
1answer
376 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
448 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
36 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
84 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
695 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
4k 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
60 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
501 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$, ...
2
votes
1answer
225 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
1k 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
111 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, ...
2
votes
1answer
52 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
641 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
84 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
52 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 ...
4
votes
1answer
68 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 ...
2
votes
1answer
74 views

Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
4
votes
1answer
608 views

Should one limit the maximum level of a skip list node?

In Skip Lists: A Probabilistic Alternative to Balanced Trees by Pugh he suggests different strategies for choosing the level of an inserted node. One such strategy, called fix the dice, limits the ...
0
votes
1answer
254 views

Link-cut trees: how to code cut(u,v)

In most bibliography, only cut(v) is defined. More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree. The pseudo-code and code for this is: ...
0
votes
1answer
484 views

Forming red-black tree from binary tree conserving in-order traversal

What is the optimal algorithm (in terms of time complexity) that can transform any binary tree to a red-black tree, with the requirement that in-order traversal must yield the same values for the new ...
2
votes
0answers
35 views

Dividing a set of goals among two search agents

Say we had two agents and we want them both to traverse a map concurrently. Their goal is to collectively visit a collection of certain points on the map. If there was just one agent, it would be ...
3
votes
1answer
445 views

Link-cut trees: using access() and link()

I am having some trouble on understanding link-cut trees, so I need some help. Suppose that we have nodes $A, B, C, D$ and we want to do the following operations: Link(A,B) Link(B,C) Link(C,...
2
votes
2answers
127 views

Tree structure that is like a quadtree/octree but splits a different number of times in each dimension?

I'm looking for a data structure that is like a quadtree where each level is a subdivision of the previous. However, unlike a quadtree I need the subdivision to occur a different number of times in ...
0
votes
0answers
52 views

Can't reach a balance in a DFS search?

Below is a question based on CLRS, about using an algorithm to reach a balance between a group of friends. I figured the best way to do this, is through the use of a DFS algorithm. Below the question ...
3
votes
0answers
257 views

What is the intuition behind balancing in AVL trees?

I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance ...
2
votes
2answers
2k views

Interval tree: find all intervals containing a given interval

Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$...
3
votes
0answers
396 views

B+tree implementation using single file on disk

I'm studying B+trees and I'm trying to understand how actual data can be stored in a physical file and still allow fast lookups. None of it would be in memory, all of the pointers would be "seeks" to ...
1
vote
0answers
470 views

Using rotate to balance a red-black tree?

You have a Black-Red Tree of height h that has two childs: Left child is a full binary tree of height h-1 Right child ...
2
votes
1answer
137 views

When an ISAM index is built, how is the number of leaf nodes per index node (the “fan-out”) calculated?

I asked this question on DB.SE but it didn't get any traction, so I'll ask it here... The following statement is in the Ramakrishnan text (2nd ed. page 252): (emphasis in bold is mine) The non-...
2
votes
0answers
340 views

Estimating size of state space search problem

Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It'...
0
votes
1answer
358 views

Why is it that any graph traversal method can be described as pre-order, in-order, or post-order? What do those terms mean?

There are several graph traversal algorithms in computer science ( vis. depth first, breadth first, etc. ). Furthermore, each of these algorithms can be implemented in pre-order, in-order, and post-...
2
votes
0answers
515 views

Time complexity of the operations on a b-tree if deletion is performed by marking nodes inactive

I'm given a B-tree where the delete-operation is not implemented, but instead keys are deleted using tombstones (so they stay in the tree, but are marked as deleted). Now when at least 90% of all keys ...
3
votes
1answer
36 views

Why divide by $b-1$ when computing size of a tree

In one of the lectures I went to, my professor stated that in order to determine the size of a search tree, we use the following formula: $$\frac{b^{d+1}-1}{b-1},$$ whee $b$ is the branching factor ...
0
votes
0answers
131 views

What is a good metric to choose the degree of a B-Tree?

What is a good metric to pick the degree of a B-Tree? I assume this depends on the number of expected elements? Degree 2 gives us a 2-3-4 tree (each node contains 1-3 items and 2-4 children). How can ...
4
votes
2answers
425 views

Number of different binary search trees storing n distinct keys?

How many different binary search trees are possible that store the values 1,2,...,n ? So far I found a recursive formula for the number (by case distinction what's at the root): $ T(n) = 2T(n-1) + \...