Recitation04 Notes
From 6.006 Wiki
(Difference between revisions)
m (→BST / AVL implementation) |
(→BST / AVL implementation) |
||
| Line 2: | Line 2: | ||
* [http://mit.edu/mng_520/Public/r03_BSTobjects2.py Binary Search Tree] | * [http://mit.edu/mng_520/Public/r03_BSTobjects2.py Binary Search Tree] | ||
* [http://mit.edu/mng_520/Public/r04_AVLobjects2.py AVL Tree template] | * [http://mit.edu/mng_520/Public/r04_AVLobjects2.py AVL Tree template] | ||
| + | |||
| + | <pre> | ||
| + | def left_rotate(self, x): | ||
| + | y = x.right #Step 1 | ||
| + | y.parent = x.parent | ||
| + | if y.parent is None: | ||
| + | self.root = y | ||
| + | else: | ||
| + | if y.parent.left is x: | ||
| + | y.parent.left = y | ||
| + | elif y.parent.right is x: | ||
| + | y.parent.right = y | ||
| + | x.right = y.left #Step 2 | ||
| + | if x.right is not None: | ||
| + | x.right.parent = x | ||
| + | y.left = x #Step 3 | ||
| + | x.parent = y | ||
| + | |||
| + | def right_rotate(self, x): | ||
| + | y = x.left #Step 1 | ||
| + | y.parent = x.parent | ||
| + | if y.parent is None: | ||
| + | self.root = y | ||
| + | else: | ||
| + | if y.parent.left is x: | ||
| + | y.parent.left = y | ||
| + | elif y.parent.right is x: | ||
| + | y.parent.right = y | ||
| + | x.left = y.right #Step 2 | ||
| + | if x.left is not None: | ||
| + | x.left.parent = x | ||
| + | y.right = x #Step 3 | ||
| + | x.parent = y | ||
| + | </pre> | ||
Revision as of 19:41, 17 September 2008
BST / AVL implementation
def left_rotate(self, x):
y = x.right #Step 1
y.parent = x.parent
if y.parent is None:
self.root = y
else:
if y.parent.left is x:
y.parent.left = y
elif y.parent.right is x:
y.parent.right = y
x.right = y.left #Step 2
if x.right is not None:
x.right.parent = x
y.left = x #Step 3
x.parent = y
def right_rotate(self, x):
y = x.left #Step 1
y.parent = x.parent
if y.parent is None:
self.root = y
else:
if y.parent.left is x:
y.parent.left = y
elif y.parent.right is x:
y.parent.right = y
x.left = y.right #Step 2
if x.left is not None:
x.left.parent = x
y.right = x #Step 3
x.parent = y
