Please enable JavaScript.
Coggle requires JavaScript to display documents.
Tree-2 - Coggle Diagram
Tree-2
- Definition: Height-balanced Binary Search Tree.
- Balance Factor: height(right) - height(left).
- Insert as in a Binary Search Tree.
- Recalculate balance factors.
- Rotate if balance factors are 2 or -2.
- Single or double rotations.
- Delete as in a Binary Search Tree.
- Recalculate balance factors.
- Rotate if balance factors are 2 or -2.
- May require multiple rotations.
- Height-balanced: Heights of children differ by at most 1.
- Perfectly balanced: Height-balanced with leaves on one or two levels.
- Goal: Keep node depths at O(log(n)).
-
-
-
- Rebuild the tree using a balance method.
- Right Rotation: Rotate a node to the right about its left child.
- Left Rotation: Rotate a node to the left about its right child.
- Value of each node is greater than or equal to its children's values (max-heap).
-
-
-
PARENT (i) = floor((i-1)/2)
-
-
-
- Polish Notation and Expression Trees
- Eliminates parentheses from formulas.
- Example:
(5 − 6) * 7 = * − 5 6 7
-
-