which describes the limiting behavior of the function
when the argument trends towards a particular value of infinity
example :
f(x)= 3x^4 - 2x^3 + 1 ;
if we wanna simply function , using O notation, the highest growth rate is
3x^4, and we take x^4 from 3x^4. Thus, we say that f(x) is a 'big-O' of (x^4),
can be write as f(x)=O(x^4).
And from class we know O(1) ∈ O(lg n) ∈ O(n) ∈ O(n^2) ∈ O(n^3) ∈ O(2^n) ∈ O(n^n)
Also we learn the binary search tree(BST), there is some properties of BST(from Wikipedia):
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes.
in a list of size n is x=log_2 (n). the logarithm base two of n.
'''
'''
class BST:
def __init__(self, container=[]):
self.root = None
for item in container:
self.insert(item)
def __str__(self):
return BST._str("",self.root)
def _str(indent, root):
if root is None:
return ""
else:
return (BST._str(indent + "\t", root.right) +
indent + repr(root.item) + "\n" +
BST._str(indent + "\t", root.left))
def insert(self, item):
parent, current = None, self.root
while current is not None and current.item != item:
if item < current.item:
parent, current = current, current.left
else:
parent, current = currrnt, curren.right
if current is None:
parent = _BSTNode(item)
if parent is None:
self.root = current
elif item < parent.item:
parent.left = current
else:
parent.right = current
class _BSTNode:
"""A node in a BST."""
def __init__(self, item, left=None, right=None):
"""(_BSTNode, object, _BSTNode, _BSTNode) -> NoneType
Initialize this node to store item and have children left and right.
"""
self.item = item
self.left = left
self.right = right
'''
'''
x = _BSTNode(1,_BSTNode(2,_BSTNode(4),_BSTNode(7)),_BSTNode(3,_BSTNode(6),_BSTNode(5)))
print(x)
y = BST([1,2,3,4])
y.insert(2)
y.insert(1)
y.insert(9)
y.insert(5)
y.insert(4)
print(y._str(y.root))
'''
class BTNode:
"""Binary Tree node."""
"""initial the Binary tree node"""
def __init__(self: 'BTNode', data: object,
left: 'BTNode'=None, right: 'BTNode'=None) -> None:
"""Create BT node with data and children left and right."""
self.data, self.left, self.right = data, left, right
def __repr__(self: 'BTNode') -> str:
"""Represent this node as a string."""
return ('BTNode(' + str(self.data) + ', ' + repr(self.left) +
', ' + repr(self.right) + ')')
def is_leaf(self: 'BTNode') -> bool:
"""Is this node a leaf?"""
return self.data and not self.left and not self.right
"""
this line equal to
if self.data != None and self.left == None and self.right == None:
return True
else:
return False
>>>x=BTNode(1)
>>>print(x.is_leaf())
True
"""
"""binary search tree ADT"""
class BST:
"""Binary search tree."""
def __init__(self: 'BST', root: BTNode=None) -> None:
"""Create BST with BTNode root.
initial self to None, if dont hv BTNode
"""
self._root = root
def __repr__(self: 'BST') -> str:
"""Represent this binary search tree."""
return 'BST(' + repr(self._root) + ')'
def find(self: 'BST', data: object) -> BTNode:
"""Return node containing data, otherwise return None."""
return _find(self._root, data)
def insert(self: 'BST', data: object) -> None:
"""Insert data, if necessary, into this tree.
>>> b = BST()
>>> b.insert(8)
>>> b.insert(4)
>>> b.insert(2)
>>> b.insert(6)
>>> b.insert(12)
>>> b.insert(14)
>>> b.insert(10)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(12, BTNode(10, None, None), BTNode(14, None, None))))
"""
def __insert(node, data):
return_node = node
if not node:
return_node = BTNode(data)
elif node.data > data:
node.left = __insert(node.left, data)
elif node.data < data:
node.right = __insert(node.right, data)
else:
pass
return return_node
self._root = __insert(self._root, data)
def delete(self: 'BST', data: object) -> None:
"""Remove, if there, node containing data.
>>> b = BST()
>>> b.insert(8)
>>> b.insert(4)
>>> b.insert(2)
>>> b.insert(6)
>>> b.insert(12)
>>> b.insert(14)
>>> b.insert(10)
>>> b.delete(12)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(10, None, BTNode(14, None, None))))
>>> b.delete(14)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(10, None, None)))
"""
def __find_max(node):
return __find_max(node.right) if node.right else node
def __delete(node, data):
return_node = node
if not node:
pass
elif node.data > data:
node.left = __delete(node.left, data)
elif node.data < data:
node.right = __delete(node.right, data)
else:
if not node.right:
return_node = node.left
elif not node.left:
return_node = node.right
else:
node.data = __find_max(node.left).data
#go throught the left side and dine max again and replace as None
node.left = __delete(node.left, node.data)
return return_node
self._root = __delete(self._root, data)
def height(self: 'BST') -> int:
"""Return height of this tree."""
return _height(self._root)
def insert2(self, data):
return_node = self._root
if not self._root:
return_node = BTNode(data)
elif self._root > data:
self._root.left = self.insert2(self.left, data)
elif self._root < data:
self._root.right = self.insert2(self.right, data)
else:
pass
def _insert(node: BTNode, data: object) -> BTNode:
"""Insert data in BST rooted at node, if necessary, and return root."""
return_node = node
if not node:
return_node = BTNode(data)
elif data < node.data:
node.left = _insert(node.left, data)
elif data > node.data:
node.right = _insert(node.right, data)
else: # nothing to do
pass
return return_node
def _find(node: BTNode, data: object):
"""Return the node containing data, or else None."""
if not node or node.data == data:
return node
else:
return (_find(node.left, data) if (data < node.data)
else _find(node.right, data))
def _delete(node: BTNode, data: object) -> BTNode:
"""Delete, if exists, node with data and return resulting tree."""
# Algorithm for _delete:
# 1. If this node is None, return that
# 2. If data is less than node.data, delete it from left child and
# return this node
# 3. If data is more than node.data, delete it from right child
# and return this node
# 4. If node with data has fewer than two children,
# and you know one is None, return the other one
# 5. If node with data has two non-None children,
# replace data with that of its largest child in the left subtree,
# and delete that child, and return this node
return_node = node
if not node:
pass
elif data < node.data:
node.left = _delete(node.left, data)
elif data > node.data:
node.right = _delete(node.right, data)
elif not node.left:
return_node = node.right
elif not node.right:
return_node = node.left
else:
node.data = _find_max(node.left).data
node.left = _delete(node.left, node.data)
return return_node
def _find_max(node: BTNode) -> BTNode:
"""Find and return maximal node, assume node is not None"""
return _find_max(node.right) if node.right else node
def _height(node):
"""Return height of tree rooted at node."""
# use max to get the deeper node
return 1 + max(_height(node.left), _height(node.right)) if node else -1
if __name__ == '__main__':
import doctest
doctest.testmod()
b = BST()
b.insert(8)
b.insert(4)
b.insert(2)
b.insert(1)
b.insert(6)
b.insert(5)
b.insert(7)
b.insert(10)
b.insert(9)
b.insert(12)
print(b)
b.delete(4)
print(b)
print('1')
b.delete(14)
print(b)
print(b.height())
a = BTNode(2)
print(_find_max(a).data)
No comments:
Post a Comment