/usr/lib/gdesklets/utils/BinTree.py is in gdesklets 0.36.1-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | #
# Class for a generic comparator-sorted binary tree.
#
class BinTree(object):
def __init__(self, value = None):
self._parent = None
self._left_child = None
self._right_child = None
self._value = value
def _find_node(self, value, comparator):
if (self._value == None):
return (self, False)
else:
comp = comparator(value, self._value)
if (comp < 0 and self._left_child):
return self._left_child._find_node(value, comparator)
elif (comp > 0 and self._right_child):
return self._right_child._find_node(value, comparator)
elif (comp == 0):
return (self, True)
else:
return (self, False)
def _get_successor(self):
succ = self._right_child
while (succ._left_child):
succ = succ._left_child
return succ
def insert(self, value, comparator):
node, success = self._find_node(value, comparator)
if (node._value == None):
node._value = value
else:
new_node = BinTree(value)
new_node._parent = node
if (comparator(value, node._value) < 0):
node._left_child = new_node
else:
node._right_child = new_node
def find(self, value, comparator):
node, success = self._find_node(value, comparator)
if (success): return node._value
def remove(self, value, comparator):
node, success = self._find_node(value, comparator)
if (success):
if (not node._left_child or not node._right_child):
y = node
else:
y = node._get_successor()
if (y._left_child):
x = y._left_child
else:
x = y._right_child
if (x):
x._parent = y._parent
if (not y._parent):
if (x):
self._value = x._value
else:
self._value = None
else:
if (y == y._parent._left_child):
y._parent._left_child = x
else:
y._parent._right_child = x
if (y != node):
node._value = y._value
|