Stack Overflow
Stack Overflow

Questions tagged [avl-tree]

Named after its inventors, Adelson-Velskii and Landis, an AVL tree is a self-balancing binary search tree.

Named after its inventors, Adelson-Velskii and Landis, an AVL tree is a self-balancing binary search tree. They were the first dynamically balanced trees to be proposed.

Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time.

923 questions
166
votes
6 answers

Red-black tree over AVL tree

AVL and Red-black trees are both self-balancing except Red and black color in the nodes. What's the main reason for choosing Red black trees instead of AVL trees? What are the applications of Red black trees?
suren
  • 1,744
  • 2
  • 12
  • 7
88
votes
4 answers

When to choose RB tree, B-Tree or AVL tree?

As a programmer when should I consider using a RB tree, B- tree or an AVL tree? What are the key points that needs to be considered before deciding on the choice? Can someone please explain with a scenario for each tree structure why it is chosen…
Palladin
  • 983
  • 1
  • 7
  • 10
84
votes
9 answers

Difference between red-black trees and AVL trees

Can someone please explain what the main differences between these two data structures are? I've been trying to find a source online that highlights the differences/similarities, but I haven't found anything too informative. In what cases would…
Bob John
  • 3,688
  • 14
  • 43
  • 57
75
votes
1 answer

Statistical performance of purely functional maps and sets

Given a data structure specification such as a purely functional map with known complexity bounds, one has to pick between several implementations. There is some folklore on how to pick the right one, for example Red-Black trees are considered to be…
t0yv0
  • 4,714
  • 19
  • 36
67
votes
9 answers

The best way to calculate the height in a binary search tree? (balancing an AVL-tree)

I'm looking for the best way to calculate a nodes balance in an AVL-tree. I thought I had it working, but after some heavy inserting/updating I can see that it's not working correct (at all). This is kind of a two-part question, the first part…
thr
  • 19,160
  • 23
  • 93
  • 130
55
votes
2 answers

Difference between AVL trees and splay trees

I am studying about various trees, and came across AVL trees and splay trees. I want to know What is difference between AVL trees and splay trees? On what basis do we select these tress? What are positive's and negative's of these trees? What are…
venkysmarty
  • 11,099
  • 25
  • 101
  • 184
49
votes
10 answers

AVL tree vs. B-tree

How is an AVL tree different from a B-tree?
neuromancer
  • 53,769
  • 78
  • 166
  • 223
31
votes
4 answers

Concatenating/Merging/Joining two AVL trees

Assume that I have two AVL trees and that each element from the first tree is smaller then any element from the second tree. What is the most efficient way to concatenate them into one single AVL tree? I've searched everywhere but haven't found…
liviucmg
  • 1,310
  • 3
  • 18
  • 26
31
votes
1 answer

How do you know where to perform rotations in an AVL tree?

So I'm self teaching AVL trees and I understand the basic idea behind it, but I just want to make sure my intuition of actually implementing it is valid: I'll examine it with the left rotation- So, the following situation is simple: 8 /…
Skorpius
  • 2,135
  • 2
  • 26
  • 31
28
votes
3 answers

Computational Complexity of TreeSet methods in Java

Is the computational complexity of TreeSet methods in Java, same as that of an AVLTree? Specifically, I want to know the computational complexity of the following methods: 1.add 2.remove 3.first 4.last 5. floor 6. higher Java Doc for method…
user1628340
  • 901
  • 4
  • 14
  • 27
24
votes
6 answers

Are AVL Trees Evil?

I was reading the article from Steve Yegge about singletons. In it he mentions his teacher told him AVL Trees were evil. Is it just that red and black trees are a better solution?
Chap
  • 2,776
  • 24
  • 31
23
votes
3 answers

How to generate maximally unbalanced AVL trees

I have written a C language library of AVL trees as general purpose sorted containers. For testing purposes, I would like to have a way to fill a tree so that it is maximally unbalanced, i.e., so that it has the maximum height for the number of…
Walter Tross
  • 12,237
  • 2
  • 40
  • 64
21
votes
4 answers

balancing an AVL tree (C++)

I'm having the hardest time trying to figure out how to balance an AVL tree for my class. I've got it inserting with this: Node* Tree::insert(int d) { cout << "base insert\t" << d << endl; if (head == NULL) return (head = new…
gregghz
  • 3,925
  • 7
  • 40
  • 69
15
votes
2 answers

Difference between the time complexity required to build Binary search tree and AVL tree?

While I was learning Binary search tree(Balanced and unbalanced), I come up with questions which I need to resolve: If I construct a Binary search tree(Not necessary to be balanced) , using n elements then what is the total time complexity for tree…
Kshitij Jain
  • 1,793
  • 5
  • 19
  • 30
15
votes
3 answers

Why red-black tree based implementation for java TreeMap?

The third paragraph of wikipedia's article on AVL trees says: "Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications." So, shouldn't TreeMap be implemented using AVL trees instead of…
Nikunj Banka
  • 11,117
  • 16
  • 74
  • 112
1
2 3
…
61 62