# Questions tagged [avl-trees]

The tag has no usage guidance.

31 questions
Filter by
Sorted by
Tagged with
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, ...
128 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$. ...
81 views

88 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 ...
45 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 ...
58 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 ...
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?
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 ...
248 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$ ...
22 views

### How do I know which node to do rotation on?

I'm wondering which node do I perform a rotation for on an AVL tree? I think in a single rotation it is always the grandparent of the node causing the imbalance (which could either be the root node ...
37 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 ...
119 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 ...
280 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 ...