Search Tree Rotation: Difference between revisions
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
Rotations are a set of primitives common to all binary search tree implementations, which preserve the [[Binary_Search_Trees#Binary_Search_Tree_Property|Binary Search Tree Property]] while locally rebalancing subtrees at a node in O(1) time. There are left rotations and right rotations. When invoking a rotation, is on a parent-child pair of a search tree. If it is the right child of the parent, use a left rotation. If it is the left child, use a right rotation. | Rotations are a set of primitives common to all binary search tree implementations, which preserve the [[Binary_Search_Trees#Binary_Search_Tree_Property|Binary Search Tree Property]] while locally rebalancing subtrees at a node in O(1) time. There are left rotations and right rotations. When invoking a rotation, is on a parent-child pair of a search tree. If it is the right child of the parent, use a left rotation. If it is the left child, use a right rotation. | ||
{{Note|Rotations preserve the [[Binary_Search_Trees#Binary_Search_Tree_Property|Binary Search Tree Property]]}} | {{Note|Rotations preserve the [[Binary_Search_Trees#Binary_Search_Tree_Property|Binary Search Tree Property]].}} | ||
=Left Rotation= | =Left Rotation= | ||
Revision as of 18:43, 13 October 2021
External
Internal
Overview
Rotations are a set of primitives common to all binary search tree implementations, which preserve the Binary Search Tree Property while locally rebalancing subtrees at a node in O(1) time. There are left rotations and right rotations. When invoking a rotation, is on a parent-child pair of a search tree. If it is the right child of the parent, use a left rotation. If it is the left child, use a right rotation.
Rotations preserve the Binary Search Tree Property.