| #!/usr/bin/env python |
| #coding:utf-8 |
| # Author: mozman |
| # Purpose: binary tree module |
| # Created: 28.04.2010 |
| # Copyright (c) 2010-2013 by Manfred Moitzi |
| # License: MIT License |
| |
| from __future__ import absolute_import |
| |
| from .treemixin import TreeMixin |
| |
| __all__ = ['BinaryTree'] |
| |
| |
| class Node(object): |
| """ Internal object, represents a treenode """ |
| __slots__ = ['key', 'value', 'left', 'right'] |
| |
| def __init__(self, key, value): |
| self.key = key |
| self.value = value |
| self.left = None |
| self.right = None |
| |
| def __getitem__(self, key): |
| """ x.__getitem__(key) <==> x[key], where key is 0 (left) or 1 (right) """ |
| return self.left if key == 0 else self.right |
| |
| def __setitem__(self, key, value): |
| """ x.__setitem__(key, value) <==> x[key]=value, where key is 0 (left) or 1 (right) """ |
| if key == 0: |
| self.left = value |
| else: |
| self.right = value |
| |
| def free(self): |
| """ Set references to None """ |
| self.left = None |
| self.right = None |
| self.value = None |
| self.key = None |
| |
| |
| class BinaryTree(TreeMixin): |
| """ |
| BinaryTree implements an unbalanced binary tree with a dict-like interface. |
| |
| see: http://en.wikipedia.org/wiki/Binary_tree |
| |
| A binary tree is a tree data structure in which each node has at most two |
| children. |
| |
| BinaryTree() -> new empty tree. |
| BinaryTree(mapping,) -> new tree initialized from a mapping |
| BinaryTree(seq) -> new tree initialized from seq [(k1, v1), (k2, v2), ... (kn, vn)] |
| |
| see also TreeMixin() class. |
| |
| """ |
| def __init__(self, items=None): |
| """ x.__init__(...) initializes x; see x.__class__.__doc__ for signature """ |
| self._root = None |
| self._count = 0 |
| if items is not None: |
| self.update(items) |
| |
| def clear(self): |
| """ T.clear() -> None. Remove all items from T. """ |
| def _clear(node): |
| if node is not None: |
| _clear(node.left) |
| _clear(node.right) |
| node.free() |
| _clear(self._root) |
| self._count = 0 |
| self._root = None |
| |
| @property |
| def root(self): |
| """ root node of T """ |
| return self._root |
| |
| @property |
| def count(self): |
| """ count of items """ |
| return self._count |
| |
| def _new_node(self, key, value): |
| """ Create a new tree node. """ |
| self._count += 1 |
| return Node(key, value) |
| |
| def insert(self, key, value): |
| """ T.insert(key, value) <==> T[key] = value, insert key, value into Tree """ |
| if self._root is None: |
| self._root = self._new_node(key, value) |
| else: |
| parent = None |
| direction = 0 |
| node = self._root |
| while True: |
| if node is None: |
| parent[direction] = self._new_node(key, value) |
| break |
| if key == node.key: |
| node.value = value # replace value |
| break |
| else: |
| parent = node |
| direction = 0 if key <= node.key else 1 |
| node = node[direction] |
| |
| def remove(self, key): |
| """ T.remove(key) <==> del T[key], remove item <key> from tree """ |
| node = self._root |
| if node is None: |
| raise KeyError(str(key)) |
| else: |
| parent = None |
| direction = 0 |
| while True: |
| if key == node.key: |
| # remove node |
| if (node.left is not None) and (node.right is not None): |
| # find replacment node: smallest key in right-subtree |
| parent = node |
| direction = 1 |
| replacement = node.right |
| while replacement.left is not None: |
| parent = replacement |
| direction = 0 |
| replacement = replacement.left |
| parent[direction] = replacement.right |
| #swap places |
| node.key = replacement.key |
| node.value = replacement.value |
| node = replacement # delete replacement! |
| else: |
| down_dir = 1 if node.left is None else 0 |
| if parent is None: # root |
| self._root = node[down_dir] |
| else: |
| parent[direction] = node[down_dir] |
| node.free() |
| self._count -= 1 |
| break |
| else: |
| direction = 0 if key < node.key else 1 |
| parent = node |
| node = node[direction] |
| if node is None: |
| raise KeyError(str(key)) |
