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

learn more… | top users | synonyms

-1
votes
1answer
25 views

Priority Queue using an AVL tree, run time question

This is a question I want to answer in pseudocode: This is regarding a sort of priority queue using an AVL tree. I initialize a global variable (named GLOB) with 0. I receive from the user an input ...
1
vote
1answer
40 views

improving java 8's implement to hash map using avl tree

Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup. Will changing this implement to an avl tree change this O(n) case to ...
4
votes
1answer
69 views

KD-Tree implementation with lat/lon coordinates

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct ...
1
vote
0answers
43 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
1
vote
0answers
27 views

Trying to understand a way to split an AVL tree in O(log n)

I'm trying to understand a presentation about AVL trees. It says that the way to split AVL trees in node x is as follows: You search for the node x and mark every left son of every node when you turn ...
1
vote
0answers
50 views

Red black tree - Insert/Delete proof of correctness

From the Cormen book I was studying the chapter focused on the red black tree. I was particularly interested in why the procedures for insert/delete fixup works (namely a formal proof). I report both ...
0
votes
1answer
19 views

Lookup complexity in B-trees [Database]

Given that: B = n/R blocks in the file 2d index records per block (blocking factor): 2d > R an extra block access from the index to the datafile I am not able ...
0
votes
0answers
38 views

minimum and maximum number of internal nodes for given number of leaves in 2-3 tree

I came across following question: Suppose a 2-3 tree has 19 leaves. What are the largest and smallest numbers of interior nodes the tree may have? Identify the correct value for minimum or ...
1
vote
0answers
13 views

How to encode each possible b-tree of a sequence of n numbers?

Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of ...
4
votes
1answer
37 views

What to infer about maximum height of AVL tree from these three different formulae

I have came across following problem: What is the maximum height of any AVL-tree with 7 nodes? The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows: ...
1
vote
1answer
29 views

Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows: We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there ...
2
votes
2answers
84 views

Why do we need double-rotations to rebalance AVL trees?

I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree: Left High (LH) tree is a tree tree with the height of the left ...
6
votes
1answer
68 views

Data structure for efficient searching, when insertions and removals are only one-sided

I need a data structure for storing a number $n$ of elements, each of whom is associated with some different time $t_i$. $n$ varies and while it has a theoretical upper limit, this is many orders of ...
3
votes
1answer
37 views

Keeping a binary search tree by splitting nodes (like a B-Tree)

A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root. Can the same technique be used to keep ...
1
vote
1answer
51 views

Question on the properties of red black trees

Problem statement Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the ...
4
votes
1answer
50 views

UCT1 Algorithm: What does “total number of simulations” mean?

When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula. $$\frac{w_i}{n_i} + \sqrt{\frac{\ln t}{n_i}}$$ Wikipedia, this guy, and this guy all ...
5
votes
1answer
49 views

Persistent random-access queue

I need a queue $[x_0, ..., x_n]$ that supports the following operations: $\operatorname{enqueue}([x_0, ..., x_n], x) = [x_0, ..., x_n, x]$ $\operatorname{dequeue}([x_0, ..., x_n]) = [x_1, ..., x_n]$ ...
1
vote
1answer
47 views

Validate that a threaded binary tree works as intended

I am attempting to validate that my threaded binary tree’s insertion and deletion works as intended. Would it be safe to assume that the following procedure would have tested all corner cases at ...
2
votes
1answer
41 views

Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is $\log n$ of an AVL tree?

Recall the standard argument for showing an AVL free is of size $\log n$: Let $n_h = $ be the minimum number of nodes of an AVL tree of height $h$. Then we have: $$ n_{h} \geq 1 + n_{h-1} + ...
2
votes
1answer
34 views

Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?

I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate ...
2
votes
0answers
24 views

Can the right childs of a node in an AVL tree be both balanced after an insert and need rebalancing?

I was trying to come up with a case where one would need rebalance the following case in an AVL tree: I think that case impossible to happen during an insert. It seems to me that its impossible to ...
6
votes
1answer
50 views

Why Is KD-Tree-based Nearest Neighbor Exponential in K?

I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why. What I'm looking for is a solid runtime-complexity ...
1
vote
1answer
51 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?
2
votes
1answer
65 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. ...
0
votes
1answer
46 views

Can I speed up Insertion Sort by using a tree for finding insertion positions?

I want to implement an insertionSort-algorithm. Let's say I have these pseudocode. ...
3
votes
1answer
43 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+ ...
5
votes
3answers
90 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 ...
0
votes
1answer
85 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
128 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
42 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
27 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 ...
1
vote
2answers
120 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 ...
1
vote
1answer
68 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
81 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
76 views
0
votes
1answer
87 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 ...
34
votes
1answer
554 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 ...
2
votes
1answer
166 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
92 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
153 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
55 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
19 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
828 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 ...
4
votes
1answer
43 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 ...
2
votes
1answer
447 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 ...
3
votes
3answers
267 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
53 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
1answer
117 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
11 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 ...
4
votes
0answers
205 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 ...