# Questions tagged [avl-trees]

The tag has no usage guidance.

31 questions
Filter by
Sorted by
Tagged with
21 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 ...
222 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$ ...
31 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 ...
37 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 ...
34 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 ...
85 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, ...
12 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?
31 views

118 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$. ...
86 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 ...
1k 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.
528 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?
51 views

### Starting with an initially empty AVL-tree, draw the resulting AVL-tree after insertion

Starting with an initially empty AVL-tree, draw the resulting AVL-tree after inserting the following elements one after another. 50, 70, 30, 10, 20, 15. I'm not sure if I am doing it correctly since ...
26 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 ...
69 views

### Is the following a AVL tree? [closed]

I have a tree as Is it an AVL tree? it seems to balanced for me.
98 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 ...
668 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 ...
177 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 ...
221 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 ...
149 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 ...
4k views

### AVL trees are not weight-balanced?

In a previous question there was a definition of weight balanced trees and a question regarding red-black trees. This question is to ask the same question, but for AVL trees. The question is, ...
390 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 ...
87 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?