Questions tagged [avl-trees]
The avl-trees tag has no usage guidance.
12
questions with no upvoted or accepted answers
2
votes
0answers
231 views
Optimizing AVL Tree operations for sequential data
I'm working on an implementation of a data structure that needs a tree-like data structure for accelerating look-ups.
The interesting part about this data structure is that the only operations on the ...
1
vote
1answer
110 views
Every AVL tree can be colored to be a red-black tree
I want to prove any AVL tree can be turnt into a red-black tree by coloring nodes appropriately.
Let $h$ be the height of a subtree of an AVL tree.
It is given that such a coloring is constrained by ...
1
vote
0answers
862 views
Find the median element of two AVL trees in $O(\log n)$
I'm attempting the problem of finding the median element in two AVL BST's in $O(\log n)$ time. In this problem, we are given two AVLs, with a combined size of $n$ (the distribution across the two ...
0
votes
1answer
46 views
AVL-tree insertion complexity proof
I tried to figure out the proof of insertion operation in AVL-tree is O(log n), but I do not know how.
I also tried to find it somewhere on the Internet, but I could not find any good results. Do you ...
0
votes
1answer
100 views
proof non-empty AVL tree
The vertex of a binary tree is called an single child if it has a father's vertex but does not have a neighbor.
The root is not considered an single child.
let mark in numOnly a number of vertices ...
0
votes
0answers
87 views
What is the maximal difference between the depths of 2 leaves in AVL tree?
I'm wondering what's the answer of the following question:
What is the maximal difference between the depths of 2 leaves in an AVL tree?
Intuitively I think that it shouldn't exceed $log n$ but have ...
0
votes
0answers
14 views
What is the insertion algorithm for an AVL tree with balance constraint of 2?
What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?
0
votes
0answers
12 views
Parsing text, then searching it: one entry per position, vs. 1 JSON column per text
I have a Rails application using Postgresql.
Texts get added to the application (ranging in size -- as short as a few words, to as long as, say, 5,000 words?).
The text gets parsed, both ...
0
votes
1answer
399 views
Rank of root in AVL tree
Find a function that bounds from above and below (asymptotic) the rank of the root r in an AVL tree,
i.e. find a function $f(n)$ so there exists a constant $c>0$ that for every AVL tree with $n$ ...
0
votes
0answers
166 views
Finding rank of newly inserted node in AVL tree augmented with rank of node
My prof was talking about how to augment a tree to efficiently find the key with a given rank. On the way to getting the right answer (store the size of the subtree rooted at each node), he proposed ...
0
votes
0answers
341 views
How to create an AVL tree, given it's pre-order traversal?
Given the pre-order traversal, we can easily obtain the necessary Binary Search Tree(BST- not necessarily balanced). However, the problem arises when we have to decide the balancing manually(this was ...
0
votes
0answers
124 views
How many maximum height AVL trees given height?
I am having some trouble finding a recursive formula for finding the number of maximum height AVL trees of height h. Height 0 has 1, height 1 has 2, height 2 has 4, height 3 has 8, etc. is that ...
