From the course: Python Data Structures: Trees

Unlock the full course today

Join today to access over 22,600 courses taught by industry experts or purchase this course individually.

Fixing a tree with multiple points of imbalance

Fixing a tree with multiple points of imbalance - Python Tutorial

From the course: Python Data Structures: Trees

Start my 1-month free trial

Fixing a tree with multiple points of imbalance

“

- So let's say we have a tree that may be all sorts of screwed up, like this one. And maybe we just want to run it through some sort of an automagic fixer, and don't want to have to think about how exactly the tree is screwed up. So we know how to fix an imbalance at a node if we know which type of imbalance that node has. We also know how to iterate through every node on a tree. So, what if we iterated through every node in the tree, figured out what kind of imbalance, if any, that node has, and then fix it. The trick here, the thing we haven't really done yet, is classify the imbalances automatically. So, let's write a function in the node class called fixImbalanceIfExists. And the first thing this is going to do, is try to figure out what imbalance this node has. And in order to do that, we're going to need to know the height on the left and the right, and get the height difference between them. And we can do that…

Contents