OLD | NEW |
1 # Copyright 2008 the V8 project authors. All rights reserved. | 1 # Copyright 2008 the V8 project authors. All rights reserved. |
2 # Redistribution and use in source and binary forms, with or without | 2 # Redistribution and use in source and binary forms, with or without |
3 # modification, are permitted provided that the following conditions are | 3 # modification, are permitted provided that the following conditions are |
4 # met: | 4 # met: |
5 # | 5 # |
6 # * Redistributions of source code must retain the above copyright | 6 # * Redistributions of source code must retain the above copyright |
7 # notice, this list of conditions and the following disclaimer. | 7 # notice, this list of conditions and the following disclaimer. |
8 # * Redistributions in binary form must reproduce the above | 8 # * Redistributions in binary form must reproduce the above |
9 # copyright notice, this list of conditions and the following | 9 # copyright notice, this list of conditions and the following |
10 # disclaimer in the documentation and/or other materials provided | 10 # disclaimer in the documentation and/or other materials provided |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
68 else: | 68 else: |
69 node.right = self.root | 69 node.right = self.root |
70 node.left = self.root.left | 70 node.left = self.root.left |
71 self.root.left = None | 71 self.root.left = None |
72 self.root = node | 72 self.root = node |
73 | 73 |
74 def Remove(self, key): | 74 def Remove(self, key): |
75 """Remove the node with the given key from the SplayTree.""" | 75 """Remove the node with the given key from the SplayTree.""" |
76 # Raise exception for key that is not found if the tree is empty. | 76 # Raise exception for key that is not found if the tree is empty. |
77 if self.IsEmpty(): | 77 if self.IsEmpty(): |
78 raise 'KeyNotFound' | 78 raise Exception('KeyNotFound') |
79 # Splay on the key to move the node with the given key to the top. | 79 # Splay on the key to move the node with the given key to the top. |
80 self.Splay(key) | 80 self.Splay(key) |
81 # Raise exception for key that is not found. | 81 # Raise exception for key that is not found. |
82 if self.root.key != key: | 82 if self.root.key != key: |
83 raise 'KeyNotFound' | 83 raise Exception('KeyNotFound') |
84 removed = self.root | 84 removed = self.root |
85 # Link out the root node. | 85 # Link out the root node. |
86 if not self.root.left: | 86 if not self.root.left: |
87 # No left child, so the new tree is just the right child. | 87 # No left child, so the new tree is just the right child. |
88 self.root = self.root.right | 88 self.root = self.root.right |
89 else: | 89 else: |
90 # Left child exists. | 90 # Left child exists. |
91 right = self.root.right | 91 right = self.root.right |
92 # Make the original left child the new root. | 92 # Make the original left child the new root. |
93 self.root = self.root.left | 93 self.root = self.root.left |
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
210 left = current | 210 left = current |
211 current = current.right | 211 current = current.right |
212 else: | 212 else: |
213 break | 213 break |
214 # Assemble. | 214 # Assemble. |
215 left.right = current.left | 215 left.right = current.left |
216 right.left = current.right | 216 right.left = current.right |
217 current.left = dummy.right | 217 current.left = dummy.right |
218 current.right = dummy.left | 218 current.right = dummy.left |
219 self.root = current | 219 self.root = current |
OLD | NEW |