AVL trees python question
Go to solution
Solved by Yamoto42,
By definition, the heights of the two branches of any SUBtree can differ in height by more than one. That is the key, and why it can be balanced with only a single restructuring. Trees are naturally recursive structures. We can categorize root, interior, and leaf nodes, but interior nodes are all roots as well. This recursive nature propagates upwards as well, meaning while the error effects the tree as a whole, it is only sourced at a single node. Fixing the (sub)tree rooted at that imbalanced node fixes the source of the error, and thereby the entire tree.
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now