- # Updates the internal data of the current node
- #
- # Concretely, updates the length and the height of the node
- private fun update_data
- do
- self.length = 0
- self.height = 1
- if left_child != null then
- self.length += left_child.length
- if left_child.height + 1 > self.height then self.height = left_child.height + 1
- end
- if right_child != null then
- self.length += right_child.length
- if right_child.height + 1 > self.height then self.height = right_child.height + 1
- end
- end
-
- # Computes and returns the balance factor (used for AVL trees)
- #
- # Formula : left.height - right.height
- redef private fun balance_factor
- do
- var left_height = 0
- var right_height = 0
- if left_child != null then left_height = left_child.height
- if right_child != null then right_height = right_child.height
- return left_height - right_height