You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
126 lines
4.2 KiB
126 lines
4.2 KiB
#!/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 .abctree import ABCTree
|
|
|
|
__all__ = ['BinaryTree']
|
|
|
|
|
|
class Node(object):
|
|
"""Internal object, represents a tree node."""
|
|
__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):
|
|
"""N.__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):
|
|
"""N.__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(ABCTree):
|
|
"""
|
|
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 abctree.ABCTree() class.
|
|
"""
|
|
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))
|
|
|