Mercurial > public > think_complexity
comparison redblacktree.py @ 20:0326803882ad
Finally completing Ch. 3, exercise 5: write a TreeMap that uses a red-black
tree.
| author | Brian Neal <bgneal@gmail.com> |
|---|---|
| date | Thu, 27 Dec 2012 15:30:49 -0600 |
| parents | 3c74185c5047 |
| children |
comparison
equal
deleted
inserted
replaced
| 19:3c74185c5047 | 20:0326803882ad |
|---|---|
| 368 if self.root: | 368 if self.root: |
| 369 self.root.color = BLACK | 369 self.root.color = BLACK |
| 370 | 370 |
| 371 return remove_flag | 371 return remove_flag |
| 372 | 372 |
| 373 def find(self, key): | |
| 374 """Looks up the key in the tree and returns the corresponding value, or | |
| 375 raises a KeyError if it does not exist in the tree. | |
| 376 | |
| 377 """ | |
| 378 p = self.root | |
| 379 while p: | |
| 380 if p.key == key: | |
| 381 return p.value | |
| 382 else: | |
| 383 d = p.key < key | |
| 384 p = p.link[d] | |
| 385 | |
| 386 raise KeyError | |
| 387 | |
| 373 | 388 |
| 374 if __name__ == '__main__': | 389 if __name__ == '__main__': |
| 375 import random | 390 import random |
| 376 | 391 |
| 377 for n in range(30): | 392 for n in range(30): |