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

learn more… | top users | synonyms

0
votes
1answer
32 views

Reb-black tree amortized cost of the rebalancing

I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions). How can it be proved?
1
vote
1answer
35 views

Difference between heuristic-based searching and optimal path searching

I'm currently studying for an AI computer-science course. One thing is difficult for me to grasp and somewhat vaguely explained in my course-material: I understand that with search-methods like e.g. ...
3
votes
1answer
30 views

Is it possible to use a copy-on-write strategy to modify a B+ tree?

Alright, I'm not sure if this is more of a stack overflow question, but I'm going to try here because you folks seem more suited. CouchDB makes an interesting claim about using an "append only" B+ ...
4
votes
3answers
56 views

Depth first or breadth first ordering in binary search trees?

Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array. The binary tree is full on ...
-1
votes
1answer
54 views

Every AVL tree may be red black tree

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof. Induction for height. Let's ...
1
vote
2answers
96 views

AVL tree such that each insert causes rotation (single or double)

Could you give me an example of an AVL tree for which inserting an element at an arbitrary (i.e. every) position causes a rotation (double or single)? I have tried to come up with an example, but I ...
0
votes
1answer
33 views

Two red children in a red-black tree

My data structures exam contains the following question: Which of the statements below about red-black trees is true? (select one or more) Every path from the root to a leaf has the same ...
0
votes
1answer
23 views

Identify balanced and full binary search tree insert order

I'm inserting numbers 1 thru 15 into a binary search tree one by one. I need to come up with an order to insert these elements for it to result in a full and balanced binary tree. I've tried to create ...
0
votes
1answer
58 views

Effective finding height of avl tree

I am searching effective way to find out height of AVL tree. In each node there is balance factor ($bf$). $$bf(root)=height(root.left) - height(root.right). $$ And now we can find height in $O(\log ...
0
votes
1answer
37 views

How the deletion takes place in B+ Tree

My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree: ...
0
votes
0answers
45 views

kd-tree for triangular range queries

Any Ideas for a linear size data structure that can answer triangular range queries, but only for triangles whose edges are either horizontal, vertical, or have slope +1 or −1. It's queries should ...
1
vote
0answers
43 views
0
votes
1answer
44 views

Example of height-balanced tree that is not weight-balanced

Following this question : Two definitions of balanced binary trees I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is ...
21
votes
0answers
362 views

Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

Let's assume the following definition of a red-black tree: It is a binary search tree. Each node is colored either red or black. The root is black. Two nodes connected by an edge cannot be red at ...
1
vote
1answer
68 views

Balance factor changes after local rotations in AVL tree

I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation: ...
1
vote
1answer
71 views

Starting BFS at s and t

INPUT: undirected graph, s, t OUTPUT: connectivity of s and t I perform BFS on s AND t, each taking turns to make one traversal. When a vertex exists in both s and t's BFS tree, we can assume it is ...
3
votes
0answers
93 views

Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289 Please have a look at this paper, specifically page 18 in which he tries to prove his ...
0
votes
1answer
52 views

Why not use large $k$ in a $k$-ary tree?

Obviously binary trees are great because of $O(\log_2 n)$ search, inserts, and deletes in best case. To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, ...
1
vote
0answers
18 views

Why do we not store the min in any of the recursive clusters in a Van Emde Boas tree?

I was reading the chapter of van Emde Boas in CLRS (page 547 section 20.3 3rd edition) and it says: Furthermore, the element stored in min does not appear in any of the recursive $vEB( ...
2
votes
2answers
398 views

Average depth of a Binary Search Tree and AVL Tree

My professor recently mentioned that the average depth of the nodes in a binary search tree will be $O(log(n))$ where $n$ is the amount of nodes in the tree. I ended up drawing out a bunch of binary ...
3
votes
1answer
37 views

Corner cases in the Interleave Lower Bound for BSTs

The Interleave lower bound is a lower bound for the amount of operations any Binary Search Tree needs to make for a sequence of accesses. It is used in the construction of Tango Trees, and is based on ...
1
vote
1answer
224 views

Can a Red Black tree be constructed of only black nodes using RB insert only?

I am trying to construct a red black tree out of only black nodes. I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders. Is it possible? I ...
2
votes
3answers
185 views

Memory usage of a BST or hash table?

I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time. 1) What is the exact ...
1
vote
1answer
36 views

Bounds on the number of rotations in the insertion operation of a Red Black Tree

I am having some trouble understanding why people say that contrary to what happens with AVL trees, there is a bound on the number of rotations occurring in an insertion with a Red Black Tree. From ...
0
votes
0answers
55 views

Adaptive Radix Tree - Question regarding child indexing

i have to write an exam in a course given by one of the contributing professors of this paper: http://www-db.in.tum.de/~leis/papers/ART.pdf Of course this could also be a possible topic in the exam. ...
1
vote
0answers
10 views

Saving a pointer to the n/4 node in AVL tree [duplicate]

I have an AVL Tree which every node has a filed with a key which is an integer. I need to save a pointer to the Minimum , Maximum and the $\left \lfloor \frac{n}{4} \right \rfloor $ nodes. the first ...
3
votes
0answers
98 views

Alpha beta algorithm with Iterative Deepening analysis

I'm implementing a chess engine. Like many engines, the search for the next best move is done with the alpha-beta algorithm. There are many improvements that can be made to make the algorithm faster ...
1
vote
1answer
81 views

Traversals from the root in AVL trees and Red Black Trees

We all know that for insertion() operation in AVL tree following can happen: We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance ...
4
votes
1answer
170 views

Why aren't tries generally used?

To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in ...
0
votes
0answers
33 views

Augment B+ Tree to support given search query

Given a B+ tree with M=3. We assume that the tree is static and it is not necessary to update the B+ tree. Also we know that all key-value pairs are stored in the leaves of the B+ tree. Internal nodes ...
4
votes
2answers
250 views

Split in AVL tree with complexity $O(\log n)$

Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject. The split operation divides the ...
2
votes
0answers
169 views

Segment trees with insertion/deletion

I have a range query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in ...
1
vote
0answers
66 views

Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
0
votes
0answers
124 views

How to represent an improper binary tree by means of proper binary tree

By definition: a binary tree needs to fulfill 3 requirements: 1) Each node must have at most 2 children. 2) Each node must have a left and right child 3) Left children is written before the right ...
2
votes
1answer
55 views

Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases: ...
1
vote
1answer
42 views

An n-dimensional index where the search key specifies an exact match on certain dimensions?

I'm working on a project where I want to to search for vectors in the form (x1, x2, x3,...xn), and be able to search for them by specifying a specific x value and getting all vectors with that x value ...
18
votes
2answers
852 views

Why are Red-Black trees so popular?

It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary ...
4
votes
2answers
431 views

A median of an AVL. How to take advantage of the AVL?

Here is the source of my question. Given a self-balancing tree (AVL), code a method that returns the median. (Median: the numerical value separating the higher half of a data sample from ...
1
vote
1answer
113 views

Can nodes in red-black trees have one nil child and one non-nil child?

I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is ...
3
votes
0answers
93 views

How to apply path compression to Multi-Bit Trie

Reading a bit about the subject of Multi-Bit tries and IP matching in: High Performance Switches and Routers H. Jonathan Chao, Bin Liu. Page 33 Network Routing: Algorithms, Protocols, and ...
3
votes
2answers
498 views

Can one insert non-unique elements into an AVL tree?

Is it possible to insert a sequence of non-unique elements into an AVL tree? For example, what is the AVL tree result of inserting 3, 3, and 3 into an initially empty AVL tree? Is it: ...
1
vote
2answers
67 views

Red Black Tree clarification

I am quite new to Red-Black trees, and therefore I am having a bit of difficult time trying to understand them. One of the properties of the Red-Black tree is that every red vertex must have two ...
0
votes
1answer
251 views

What is the advantage of Day-Stout-Warren algorithm for balancing BST?

While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in O(n) time. In my opinion I can ...
0
votes
1answer
222 views

How to efficiently use an AVL tree to store partial sums?

Let $a_{1} , ... , a_{m} $ be real numbers $\geq 1$, where $m$ is at least 1. I am supposed to store them in an augmented AVL structure with the following operations: -PartialSum (i): Return the ...
0
votes
1answer
35 views

A BST can be broken by accessing one of its nodes, how can I always make sure this happens? [closed]

I have an assignment that asks for this. So I am not looking for the answer itself but a hint on how to find a value that will always break the BST condition by myself. If I have access to any node N ...
2
votes
1answer
418 views

Time Complexity proof for Segment Tree implementation of the ranged sum problem

I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here. However I'm not able to prove ...
0
votes
3answers
55 views

Complexity of BST [duplicate]

I have the following pseudo-code for printing all nodes of a BST : ...
0
votes
0answers
38 views

Finding and Grouping like children

I'm working on a dependency managemen solution for a JavaScript. I'm trying to find the best pattern for grouping similar items in a graph into their own 'modules'. Given a dependency tree like ...
1
vote
1answer
172 views

How to do high performance string matching when comparing unordered sets of tokens [closed]

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
1
vote
1answer
90 views

Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

My best attempt at a specific case of the problem where $n =$ 256: For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq ...