Skip to main content

Questions tagged [avl-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
61 views

Possible values of root of AVL tree

I have a question: given that an AVL tree holds numbers 1, 2, 3, ..., 1000, what are the smallest and largest possible values of the root? I have a feeling it is 500 and 501, but I don't know how to ...
HBH's user avatar
  • 21
0 votes
0 answers
63 views

Sub-Grouping AVL tree based on nodes amount in O(log(n))

I need to find a way to split an AVL tree based on the amount of nodes in the tree, lets assume you get a number $k$ and if the number of nodes in the tree is multiplication of $k$ you need to find ...
3xhaust's user avatar
0 votes
1 answer
54 views

Time Complexity: Determining if a binary tree is balanced

I found an algorithm for determining if a binary tree is height-balanced. It Gets the height of left and right subtrees using dfs traversal. Return true if the difference between heights is not more ...
Ali Naseri's user avatar
0 votes
2 answers
66 views

AVL tree with balance factor equal to depth

If you were to define an altered AVL tree where the balance factor (the difference between the height of the left and right subtree) of a node must be less than or equal to the depth of the node (in ...
Remeraze's user avatar
1 vote
2 answers
385 views

Ordered sequence with logarithmic insert and remove

Problem: we have a sequence of numeric values, e.g. [102, 25, 77, 17, 2, 13]. We need to implement 3 operations, each can be at most logarithmic time complexity. <...
YogoWafel's user avatar
0 votes
0 answers
128 views

Number of ways to insert elements into an AVL tree such that there are no rotations

How many ways can we insert elements { 1, 2, 3, .... 7 } to make an AVL tree so that it does not have any rotation? I broke it down into 2 cases: Case 1: height of tree = 2, (a complete binary tree) ...
Arun Madhav's user avatar
0 votes
1 answer
54 views

What does h indicate in this diagram of avl trees?

Looking at the tree on the left it seems that the triangles represent leaves of the avl tree. To arrive at the balancing of -2 besides the node y the right subtree must have 2 nodes while the left ...
Rubus's user avatar
  • 123
2 votes
1 answer
83 views

Find a key in a BBST for which sum of values of keys smaller then it - is maximal

I'm required to describe an implementation of a data structure that holds key,value pairs, which can be signed integers. We need to be able to init() in O(1), insert(x) in O(logn), delete(x) in O(logn)...
sadcat_1's user avatar
  • 241
1 vote
0 answers
182 views

logarithmic height AVL trees

AVL trees are height balanced binary search trees. As a consequence of this balance, the height of an AVL tree is logaritmic in its number of nodes. Then, searching and updating AVL-trees can be ...
Hendrik Jan's user avatar
  • 30.7k
4 votes
1 answer
744 views

Big O vs. Big Theta for AVL tree operations

On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ...
573hgkaf's user avatar
1 vote
1 answer
268 views

Interval Tree by Augmenting an AVL Tree

According to Wikipedia: An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. ...
Vectorizer's user avatar
0 votes
1 answer
518 views

Height of AVL Tree

I found an AVL tree implementation on the internet and experimented: For a tree with node count of 2^20, the minimal and maximal tree heights are 16 and 24. While these heights are lg(n)-ish, I am ...
Vectorizer's user avatar
0 votes
1 answer
375 views

AVL Tree rotations

What size is the largest AVL tree for which an insertion could trigger a double rotation?
jon pierre's user avatar
-1 votes
1 answer
78 views

Are AVL&RB Trees without additional storage for balance information in each node feasible?

One advantage claimed for scapegoat trees over other balanced trees like AVL or red-black(RB trees - just mentioning AVL henceforth) is not needing to store additional balance information. But can't ...
greybeard's user avatar
  • 1,074
0 votes
0 answers
126 views

Rebalance the following AVL tree after inserting G. You need to show the middle step if it happens. Briefly explain the operations

I recently learned AVL Trees but I still lack a complete understanding of the concept. I understand that an AVL tree is a Binary search tree that checks for the height of the tree, but I still don't ...
Thomas Wang's user avatar
2 votes
0 answers
161 views

How is red-black tree insertion more effective than avl tree insertion

I'm having trouble understanding why RB tree insertion is called more effective in all sources. It's said that AVL trees require "more rotations" than RB trees, but from what I've learned I ...
Sviatozar Petrenko's user avatar
0 votes
0 answers
54 views

Question about AVL properties

Assume that the oil company saves for each person that works in the company a record with its name, its salary, its age and its date of birth. You can assume that no two fields are identical for any ...
MathCurious's user avatar
0 votes
0 answers
61 views

Minimum number of elements in AVL tree to make it worth creating

Given an AVL tree containing nodes ordered by unique integer I.D's and data as pointers to some struct, what would be the expected minimum number of elements that will justify the creation and ...
Eminem's user avatar
  • 131
0 votes
0 answers
98 views

Suggest a Data Structure that support the following operations with time complexity O(log(n))

I’m looking for a data structure that supports that store the salaries of it’s employees. Insert(e) – Insert employee e into the data structure. AvgDecile(k) – Returns the average salary of the k’th ...
Miriam Nam's user avatar
2 votes
2 answers
80 views

Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?

Given a self-balancing binary search tree of size $n$, I want to perform the following operations: InsertInOrderSequentialBatch an ordered sequence of $k$ values (...
Warty's user avatar
  • 141
0 votes
2 answers
362 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 ...
Byteq's user avatar
  • 1
1 vote
2 answers
656 views

is it possible to create an avl tree given any set of numbers?

I am studying balanced trees, especially AVL trees. My question is whether is it possible to create an avl tree given any set of numbers. is it possible to prove the following statement? Let $A$ be ...
user avatar
1 vote
1 answer
1k 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 ...
PsychoKitten's user avatar
2 votes
1 answer
2k views

What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?

I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <...
nTuply's user avatar
  • 469
2 votes
1 answer
187 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 ...
Eden Gilad's user avatar
0 votes
0 answers
430 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 ...
Combinatoric's user avatar
3 votes
1 answer
2k views

Worst Case for AVL Tree Balancing after Deletion

After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST). The Balancing ...
alienated-vocalist-251's user avatar
0 votes
1 answer
862 views

Augmenting AVL tree to calculate sum of subtree

Suggest a way to augment an AVL tree to support a $O(\log n)$ implementation of the function calculateSum(key), which receives a key of a node and returns the sum ...
Lee's user avatar
  • 167
2 votes
2 answers
172 views

Managing an hotel using AVL trees - Data Structures

I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$ and it can be occupied or not. Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, ...
CSch of x's user avatar
0 votes
1 answer
2k views

Prove that AVL tree has this kind of property with Fibonacci sequence

Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$) and has a height of $h$ this property is true: $n \geq F(h)$ where $F(h)$ is the $h$-th element in the Fibonacci sequence: $F(0) =0, F(1)=...
CSch of x's user avatar
0 votes
0 answers
14 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 ...
michaelsking1993's user avatar
0 votes
1 answer
694 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$ ...
Emma's user avatar
  • 241
1 vote
0 answers
1k 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 ...
BarTM's user avatar
  • 11
1 vote
1 answer
632 views

Efficiently finding the min-cost path of an AVL tree

It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree: The min-cost path would be 8-6-5. ...
Andrew's user avatar
  • 111
3 votes
1 answer
298 views

Dynamic data structure that checks all prefix sums of a subsequence are >= 0 and sum is = 0

Lets consider sequences whose elements are $-1,0,1$. Subsequence $A[i...j]$ is $good$ if sum of its elements $=0$. Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is $good$. ...
TurboGuma's user avatar
  • 207
3 votes
1 answer
85 views

Structure for getting $| \{ a,b \} \subset S : a+b \le d|$ in O(1)

I am struggling with exercise from the old algorithmic exam: $d$ is const for the whole structure. Propose a structure for which you can do: Init(S) //called only 1 time Insert(x, S):: $ S := S \...
TurboGuma's user avatar
  • 207
1 vote
1 answer
840 views

Why multiple rotations might be needed after deletion in an AVL tree if after insertion there can be at most one needed?

I understand that after deletion you have to retrace to update ancestors and after insertion you do the similar however at most one rotation will be performed. The question is why is there the ...
kade99's user avatar
  • 13
0 votes
2 answers
3k views

is AVL tree is better than heap for sorting purpose?

for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?
Vishal Upadhayay's user avatar
1 vote
1 answer
3k views

How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$

I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a ...
Siladittya's user avatar
0 votes
1 answer
81 views

AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?

I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them ...
King Cold's user avatar
  • 127
-1 votes
1 answer
380 views

Is the following a AVL tree? [closed]

I have a tree as Is it an AVL tree? it seems to balanced for me.
jason's user avatar
  • 109
0 votes
0 answers
429 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 ...
antonky's user avatar
  • 133
1 vote
1 answer
2k views

AVL Tree - Print ascending using in-order

Trying to understand how to write proof of correctness. Searched over the internet on how to write proof of correctness but can't find a good solution for it. The following sorting algorithm is ...
Gil's user avatar
  • 49
2 votes
0 answers
408 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 ...
rationalcoder's user avatar
0 votes
0 answers
643 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 ...
Shubhayu's user avatar
1 vote
1 answer
281 views

Is it possible to balance a already constructed un-balanced AVL tree, with no prior information of last insert?

Im learning about tree data structures, and had a question that i couldnt find answer to so I came here. Usually when we balance a tree, we insert keys and keep checking balance factor, as soon as it ...
Kamran khan's user avatar
3 votes
2 answers
5k views

AVL tree worst case height proof

The worst case height of AVL tree is $1.44 \log n$. How do we prove that? I read somewhere about Fibonacci quicks but did not understand it.
Manoharsinh Rana's user avatar
1 vote
1 answer
143 views

avl trees rotations question

As you can see in this tree its unbalanced at the root with a balanced factor of $-2$. You can also perform a Right left rotation or a Right Right rotation. Which do you have to pick in this case?
Tinler's user avatar
  • 139
0 votes
0 answers
133 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 ...
Jasmine's user avatar
2 votes
3 answers
2k views

How do I know which direction I should rotate a node in an AVL Tree?

I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL ...
xxxtentacion's user avatar