weight-balanced-tree/weight_balanced_tree.py
Ryan Febriansyah 222f176a95 initial commit
2023-06-08 08:00:26 +07:00

166 lines
5.2 KiB
Python

import requests
class TreeNode:
def __init__(self, key, num_of_anomaly):
self.key = key
self.left = None
self.right = None
self.weight = 1
self.anomalies = 0 or num_of_anomaly
class WeightBalancedTree:
def __init__(self) -> None:
self.root = None
def detect_anomalies(self, threshold, features):
if self.root is not None:
return self._detect_anomalies(self.root, threshold, features)
def search(self, key) -> bool:
if self._search(self.root, key):
return True
return False
def insert(self, key):
if self.root is None:
# num of anomaly occurrences shouldn't be started from 1
self.root = TreeNode(key=key, num_of_anomaly=1)
else:
self.root = self._insert(self.root, key)
return key
def delete(self, key):
self.root = self._delete(self.root, key)
if self.root is None:
return True
return False
@staticmethod
def size(node):
if node is None:
return 0
return node.weight
def _delete(self, node, key):
if node is None:
return
# personally, i'd to believe this logic here isn't quite right
# upon looking up node is successful and there's nothing else to find,
# still there's a condition to check the weightage between sub-tree
# on the left and on the right and rotate among them
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
elif node.left is None:
return node.right
elif node.right is None:
return node.left
elif self.size(node.left) > self.size(node.right):
node = self._rotate_right(node)
node.right = self._delete(node.right, key)
elif self.size(node.right) > self.size(node.left):
node = self._rotate_left(node)
node.left = self._delete(node.left, key)
self._update_size(node)
return self._balanced(node)
def _update_size(self, node):
# size of the internal nodes, sum between
# two sub-trees (left, right, plus 1)
node.weight = 1 + self.size(node.left) + self.size(node.right)
def _rotate_left(self, node):
new_root = node.right
node.right = new_root.left
new_root.left = node
self._update_size(node)
self._update_size(new_root)
return new_root
def _rotate_right(self, node):
new_root = node.left
node.left = new_root.right
new_root.right = node
self._update_size(node)
self._update_size(new_root)
return new_root
def _balanced(self, node):
if node is None:
return node
# balancing the operations, to get the balanced nodes for both sides
# ensure that length of the node left is approximately equal to the path
# length of the right node. it is also worth to noting that the
# rotation operation (exchange between right and left node should be similar)
if self.size(node.left) < (2 * self.size(node.right)):
if self.size(node.right.left) > self.size(node.right.right):
node.right = self._rotate_right(node.right)
node = self._rotate_left(node)
if self.size(node.right) < (2 * self.size(node.left)):
if self.size(node.left.right) > self.size(node.left.left):
node.left = self._rotate_left(node.left)
node = self._rotate_right(node)
return node
def _search(self, node, key):
if node is None or node.key == key:
return node
if key > node.key:
return self._search(node.right, key)
else:
return self._search(node.left, key)
def _detect_anomalies(self, node, threshold, features):
if node is None:
return None
# how about if the features parameter accepts list or tuple argument?
if node.weight > threshold and node.key in iter(features):
raise OverflowError(
"Anomaly is being detected: {0}, with weight of tree is : {1}".format(
node.key, node.weight
)
)
self._detect_anomalies(node.left, threshold, features)
self._detect_anomalies(node.right, threshold, features)
def _insert(self, node, key):
if node is None:
return TreeNode(key=key, num_of_anomaly=1)
if node.key == key:
node.anomalies += 1
elif key < node.key:
node.left = self._insert(node.left, key)
else:
node.right = self._insert(node.right, key)
self._update_size(node)
return self._balanced(node)
class HttpRequest:
def __init__(self, url) -> None:
self.session = requests.Session()
self.url = url
def send_request(self):
if self.url is None:
raise ValueError("argument of URL is required")
try:
response = self.session.get(url=self.url)
return response.status_code
except requests.exceptions.RequestException:
raise Exception