Hacker News Reader

Comment by tgv | Hacker News Reader

This feels written by ChatGPT, certainly the first and last paragraph. And it omits a few important characteristics. Balanced trees were known, but balancing was expensive. AVL trees have an O(log n) cost for search, insertion and deletion, and achieves this not by balancing but by almost balancing.

View on HN

It was mostly written by me, although I do admit to using ChatGPT to help out in generating some of my material. Most of the recent blog posts are Feynman style lecture notes I wrote for myself to learn new concepts and this piece I actually wrote well over 10 years ago and I figured to share it in case anyone else wanted a quick and visual overview. Apologies for missing out any important concepts. At the time I wrote down material that I found important so there are definitely things I may have not explained correctly.

All examples rotate a node with a single child, what about the case where you have two children?

AVL trees are binary trees so they can only have 2 children.

There can be nodes with a single child. Otherwise an AVL tree would always have 2^n - 1 or 2^n - 2^(n-2) - 1 nodes. Imagine adding a node to a balanced tree with 3 nodes.

You would only rotate a node when it becomes un-balanced (i.e. so the only case you would deal with is the instance where a new child-node is added to another child within the tree). There are no cases where you would need to re-balance when you add a 2nd child - the balance factor would be larger than 1 in the instance of adding the 1st child element to the node and thus you could never find cases like this (unless I'm misunderstanding what you're asking).

In the case of 3 with children 1 and 5 and 5 with children 4 and 6. 3 and 5 have two nodes. If you add 7 as a child of 6, the tree is unbalanced. This is not one of the cases shown.

Reply on news.ycombinator.com