Skip to content

Instantly share code, notes, and snippets.

@jnpn
Created June 10, 2019 15:03
Show Gist options
  • Save jnpn/e5c1c902d0b01704f40878a1ea66e180 to your computer and use it in GitHub Desktop.
Save jnpn/e5c1c902d0b01704f40878a1ea66e180 to your computer and use it in GitHub Desktop.
trying ways to create random trees
import random
class Node:
def __init__(self, v, l=None, r=None):
assert v is not None, "can't create a node with value = None"
self.v = v
self.l = l
self.r = r
def __repr__(self):
rl = repr(self.l)
rr = repr(self.r)
if self.l or self.r:
return f'Node({self.v}\n\tl:{rl},\n\tr:{rr})'
else:
return f'Leaf({self.v})'
class RTree:
def __init__(self, root):
self.root = root
self.boundary = set([root])
def rebound(self, parent, child):
"""
Adds a new child in the boundary,
Remove parent if it has left and right node.
"""
self.boundary.add(child)
if parent.l and parent.r:
self.boundary.remove(parent)
def insert(self, value):
parent = random.choice(list(self.boundary))
insert_left = random.choice([True, False])
child = Node(value)
if insert_left:
parent.l = node
else:
parent.r = node
self.rebound(parent, child)
def __repr__(self):
return f'<RTree\n\tboundary:{self.boundary}\n\n\ttree:{self.root}>'
def test0(count=4):
t = RTree(Node(1))
for i in range(count): t.insert(i)
return t
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment