<jupyter_start><jupyter_text>Binary Search TreesSome fun with binary search trees	These trees are simple Traditional binary trees.    Ok, Thats it. Now load some data, for example (9, 4, 1, 4, 2, 6, 4, 5, 7, 4, 6)<jupyter_code>import collections

debugging = False
#debugging = True
debug2 = False

logging = True

def dbg(f, *args):
    if debugging:
        print(('  DBG:' + f).format(*args))

def dbg_cont(f, *args):
    if debugging:
        print(('  DBG:' + f).format(*args), end='')

def dbg2(f, *args):
    if debug2:
        print((' -DBG2:' + f).format(*args))
        
def log(f, *args):
    if logging:
        print((f).format(*args))
        
def logError(f, *args):
    if logging:
        print(('*** ERROR:' + f).format(*args))
        
def className(instance):
    return type(instance).__name__

def isstr(obj): 
    return isinstance(obj, basestring)

def iterable(obj):
    return isinstance(obj, collections.Iterable)
# %load TestHarness.py
class TestCase(object):
    def __init__(self, name, method, inputs, expected, catchExceptions=False):
        self.name = name
        self.method = method
        self.inputs = inputs
        self.expected = expected
        self.catchExceptions = catchExceptions
        
    def run(self):
        if self.catchExceptions:
            try:
                return self.method(*self.inputs)
            except Exception as x:
                return x
        else:
                return self.method(*self.inputs)

import time
from datetime import timedelta

class TestSet(object):
    def __init__(self, cases):
        self.cases = cases
    
    def run_tests(self):
        count = 0
        errors = 0
        total_time = 0
        for case in self.cases:
            count += 1
            start_time = time.time()
            result = case.run()
            elapsed_time = time.time() - start_time
            total_time += elapsed_time
            if callable(case.expected):
                if not case.expected(result):
                    errors += 1
                    logError("Test {0} failed. Returned {1}", case.name, result)
            elif result != case.expected:
                errors += 1
                logError('Test {0} failed. Returned "{1}", expected "{2}"', case.name, result, case.expected)
        if errors:
            logError("Tests passed: {0}; Failures: {1}", count-errors, errors)
        else:
            log("All {0} tests passed.", count)
        log("Elapsed test time: {0}", timedelta(seconds=total_time))
# Definition for a binary tree node.
# class TreeNode(object):

class TreeNode():
    """ A tree node """
    def __init__(self, value=None):
        self.value = value
        self.left  = None
        self.right = None
        
    def link(self, left, right):
        self.left  = left
        self.right = right
        
    def minv(self):
        if self.left:  return self.left.minv()
        if self.value: return self.value
        return self.right.minv()
        
    def maxv(self):
        if self.right: return self.right.maxv()
        if self.value: return self.value
        return self.left.maxv()
    
    def depth(self, current=0):
        ldepth = current if self.left  is None else self.left.depth(current+1)
        rdepth = current if self.right is None else self.right.depth(current+1)
        d = max(ldepth, rdepth)
        dbg("--- [{0}] c={1} d={2}", self.value, current, d)
        return d
    
    def find(node, val):
        """ returns the node containing val or None """      
        if node:
            if node.value < val:
                node = node.left
                if node: return node.find(val) 
            elif node.value > val:
                node = node.right
                if node: return node.find(val)
        return node

    def ldepth(self):
        return 0 if self.left is None else self.left.depth(1)

    def rdepth(self):
        return 0 if self.right is None else self.right.depth(1)
    
    def insert(self, v):
        rootv = self.value
        if rootv is None:
            self.value = v
        elif v < rootv:
            if self.left is None:
                self.left = TreeNode(v)
            else:
                self.left.insert(v)
        else:
            if self.right is None:
                self.right = TreeNode(v)
            else:
                self.right.insert(v)

    def load(node, *args):
        ''' When only a single argument is passed, iterate it when its
            a list, otherwise just insert it. '''
        if len(args) == 1:
            arg = args[0]
            if iterable(arg):
                for v in arg:
                    node.insert(v)
            else:
                node.insert(arg)
        else:
            for arg in args:
                node.insert(arg)
        return node
        
    def formatNode(self):
        return '' if self is None else '"{0}"'.format(self.value)                   
            
    def __str__(self):
        if not self:
            return "()"
        else:
            leftstr = '.' if self.left is None else "{0}, ".format(str(self.left))
            rightstr = '.' if self.right is  None else ", {0}".format(str(self.right))
            return "({0}[{1}]{2}])".format(leftstr, str(self.value), rightstr)
        
    def liststr(self):
        if not self:
            return "(*)"
        else:
            leftstr = '' if self.left is None else "{0}".format(self.left.liststr())
            rightstr = '' if self.right is None else "{0}".format(self.right.liststr())
            return "{0}{1}, {2}".format(leftstr, str(self.value), rightstr)
        
    def tolist(self):
        llist = [] if self.left  == None else self.left.tolist();
        rlist = [] if self.right == None else self.right.tolist();
        return llist + [self.value] + rlist
    
    def inorder(self, reversed=False):
        """ A recursive generator that generates Tree leaves in in-order """
        if self:
            nxt = self.right if reversed else self.left
            if nxt:
                for x in nxt.inorder(reversed):
                    yield x
            yield self.value
            nxt = self.left if reversed else self.right
            if nxt:
                for x in nxt.inorder(reversed):
                    yield x               
                    
    def __iter__(self):
        """ Return node values in order """
        if self:
            if self.left: 
                for x in self.left: yield x
            yield self.value
            if self.right: 
                for x in self.right: yield x
        
    def display(self, level=0):
        """ prints an clockwise rotates tree (right nodes at top) """
        indent = '    ' * level
        if self.right:
            self.right.display(level + 1)
            print(indent, '    /')

        print('{0}  "{1}"'.format(indent, self.value))

        if self.left:
            print(indent, '    \\')
            self.left.display(level + 1)

    __repr__ = __str__
import math
import pprint

def tree_list(tree):
    layers = [] # The set of nodes in display form
    widths = [] # The average widths of each level

    def listLayer(node, layers, off='C', p=None, index=1):
        if node is not None:
            level = math.floor(math.log(index,2))
            if len(layers) <= level:
                layers.append([])
            f = ' ' +  node.formatNode() + ' '
            c = index - 2**level
            datum = { 'parent':p, 'text':f, 'level':level, 'offset':off, 'col':c }
            layers[level].append(datum)
            listLayer(node.left,  layers, 'L', node, index*2)
            listLayer(node.right, layers, 'R', node, index*2+1)
    listLayer(tree, layers)
    #pprint.pprint(layers)

    # Find a good maximum width for the displayed tree.
    count = 1
    maxwidth = 1
    for layer in layers:
        avg = math.floor(0.5 + sum(len(x['text']) for x in layer) / len(layer))
        lwidth = avg*count 
        widths.append({ 'avg':avg, 'layerwidth':lwidth})
        count *= 2
        maxwidth = max(maxwidth, lwidth)
    dbg2("-- Maxwidth={0} widths={1}",maxwidth,widths)

    # Format the actual text lines
    count = 1
    output = ""
    for layer in layers:
        line = ""
        arrow = ""
        center = maxwidth / 2
        dbg2("Layer: {0}", count)
        for node in layer:
            colwidth = maxwidth / count
            text = node['text']
            colnum = node['col']
            leadingoffset = math.floor(colnum * colwidth) # Offset of cell from left.
            celloffset = math.floor(0.5 + (colwidth - len(text))/2)
            offset = leadingoffset + celloffset
            math.floor(0.5 + (colwidth * colnum - len(text)/2) / 2)
            dbg2("offset={1} colwidth={2} colnum={3} text={0}", text, offset, colwidth, colnum)
            if len(line) < offset:
                fill = offset - len(line)
                line += ' '*fill
            rightarrowoffset = len(line)+1      
            line += text
            leftarrowoffset = len(line)-2
            # For non root nodes, format the link arrows.
            if count > 1:
                arrowoffset = leftarrowoffset if node['offset'] == 'L' else rightarrowoffset
                offset = arrowoffset
                dbg2("offset={1} arrowoffset={2} colnum={3} text={0} ", text, offset, arrowoffset, colnum)
                if len(arrow) < offset:
                    fill = offset - len(arrow)
                    arrow += ' '*fill
                arrow += '/' if node['offset'] == 'L' else '\\'
        if count>1:
            output += arrow + '\n'
        output += line + '\n'
        count *= 2
    return output
x = TreeNode()
x.insert(55)
x.insert(22)
x.insert(11)
x.insert(5)
x.insert(2)
x.insert(3)
x.insert(1)

print(str(x))
print(x.liststr())
x
#print(tree_list(x))
x.display()
y = TreeNode()
y.insert(3)
y.insert(12)
y.insert(5)
y.insert(1)
y.insert(9)

print(y.liststr())
y
y.insert(2)
print(y)
y.insert(0)
print(y)
y.insert(4)
y.insert(8)
y.insert(11)
y.insert(1)

print(y.liststr())
y

def findPairSlow(tree, sumv):
    ''' 
        Fairly understandable, but expensive way to compute the pair since in
        addition to the traversal, we look up each possible remainder resulting
        in O(n * (n-1)log n) worst case cost -- BUT it uses no extra storage.
    '''
    for v in tree:
        rem = sumv - v
        if rem != v: # The pair can't be equal with a BST
            nde = tree.find(rem)
            if nde:
                return (v, rem)
    return None
def findPairR(tree, sumv):
    ''' 
        Do a double traversal from start and end until an answer is
        found, or we use up all the values.
    '''
    front = tree.inorder()
    back  = tree.inorder(reversed=True)
    vlow  = next(front)
    vhigh = next(back)
    while vlow < vhigh:
        if vlow + vhigh == sumv:
            return (vlow, vhigh)
        if vlow + vhigh < sumv:
            vlow = next(front)
        if vlow + vhigh > sumv:
            vhigh = next(back)
    return 'None'
y = TreeNode().load([6, 15, 10, 25, 8, 12, 20, 30, 9, 18, 22])
y
print([x for x in y])
["{0}:{1}".format(v, findPairR(y, v)) for v in range(70)]


"+".join(["x","uuu","z"])

def parrot(voltage, state='a stiff', action='voom'):
     print("-- This parrot wouldn't", action, end=' ')
     print("if you put", voltage, "volts through it.", end=' ')
     print("E's", state, "!")

d = {"voltage": "four million", "state": "bleedin' demised", "action": "VOOM"}
parrot(**d)
a = [range(0, 5), 33, 5]
print(list([1, 2, 3, 4]))
#print tuple(range(5))
list(range(10, 20)[2:5])
a = list(range(10, 20))

print(a)
import types

def merge(ia, ib):
    a = None
    b = None
    aok = False
    bok = False
    if not isinstance(ia, types.GeneratorType): ia = iter(ia)
    if not isinstance(ib, types.GeneratorType): ib = iter(ib)
    while ia or ib:
        if not aok and ia: # load a
            try:
                a = next(ia)
                log('load a={0}', a)
                aok = True
            except StopIteration:
                ia = None
                aok = False
        if not bok and ib: # load b
            try:
                b = next(ib)
                bok = True               
                log('load b={0}', b)
            except StopIteration:
                ib = None
                bok = False
        if aok and bok: # return the least of the loaded values.
            if a < b:
                aok = False
                yield a
            else:
                bok = False
                yield b
        else:
            if aok:
                aok = False
                yield a               
            if bok:
                bok = False
                yield b

a = list(range(10, 20))
b = list(range(5,22,2))
print(a)
print(b)
#a=[]
[x for x in merge(a,b)]

# -*- coding: utf-8 -*-
##  Implementation of AVL tree
#
#   Author: <NAME>
#           <EMAIL>
#           http://coder.si

class avlnode(object):
    """
    A node in an avl tree.
    """

    def __init__(self, key):
        "Construct."

        # The node's key
        self.key = key
        # The node's left child
        self.left = None
        # The node's right child
        self.right = None

    def __str__(self):
        "String representation."
        return str(self.key)

    def __repr__(self):
        "String representation."
        return str(self.key)
    
class avltree(object):    
    """
    An avl tree.
    """
    
    def __init__(self):
        "Construct."

        # Root node of the tree.
        self.node = None
        # Height of the tree.
        self.height = -1
        # Balance factor of the tree.
        self.balance = 0
        
    def insert(self, key):
        """
        Insert new key into node
        """
        # Create new node
        n = avlnode(key)

        # Initial tree
        if not self.node:
            self.node = n
            self.node.left = avltree()
            self.node.right = avltree()
        # Insert key to the left subtree
        elif key < self.node.key:
            self.node.left.insert(key)
        # Insert key to the right subtree
        elif key > self.node.key:
            self.node.right.insert(key)
            
        # Rebalance tree if needed
        self.rebalance()
        
    def rebalance(self):
        """
        Rebalance tree. After inserting or deleting a node, 
        it is necessary to check each of the node's ancestors for consistency with the rules of AVL
        """

        # Check if we need to rebalance the tree
        #   update height
        #   balance tree
        self.update_heights(recursive=False)
        self.update_balances(False)

        # For each node checked, 
        #   if the balance factor remains −1, 0, or +1 then no rotations are necessary.
        while self.balance < -1 or self.balance > 1: 
            # Left subtree is larger than right subtree
            if self.balance > 1:

                # Left Right Case -> rotate y,z to the left
                if self.node.left.balance < 0:
                    #     x               x
                    #    / \             / \
                    #   y   D           z   D
                    #  / \        ->   / \
                    # A   z           y   C
                    #    / \         / \
                    #   B   C       A   B
                    self.node.left.rotate_left()
                    self.update_heights()
                    self.update_balances()

                # Left Left Case -> rotate z,x to the right
                #       x                 z
                #      / \              /   \
                #     z   D            y     x
                #    / \         ->   / \   / \
                #   y   C            A   B C   D 
                #  / \ 
                # A   B
                self.rotate_right()
                self.update_heights()
                self.update_balances()
            
            # Right subtree is larger than left subtree
            if self.balance < -1:
                
                # Right Left Case -> rotate x,z to the right
                if self.node.right.balance > 0:
                    #     y               y
                    #    / \             / \
                    #   A   x           A   z
                    #      / \    ->       / \
                    #     z   D           B   x
                    #    / \                 / \
                    #   B   C               C   D
                    self.node.right.rotate_right() # we're in case III
                    self.update_heights()
                    self.update_balances()

                # Right Right Case -> rotate y,x to the left
                #       y                 z
                #      / \              /   \
                #     A   z            y     x
                #        / \     ->   / \   / \
                #       B   x        A   B C   D 
                #          / \ 
                #         C   D
                self.rotate_left()
                self.update_heights()
                self.update_balances()

    def update_heights(self, recursive=True):
        """
        Update tree height

        Tree height is max height of either left or right subtrees +1 for root of the tree
        """
        if self.node: 
            if recursive: 
                if self.node.left: 
                    self.node.left.update_heights()
                if self.node.right:
                    self.node.right.update_heights()
            
            self.height = 1 + max(self.node.left.height, self.node.right.height)
        else: 
            self.height = -1

    def update_balances(self, recursive=True):
        """
        Calculate tree balance factor

        The balance factor is calculated as follows: 
            balance = height(left subtree) - height(right subtree). 
        """
        if self.node:
            if recursive:
                if self.node.left:
                    self.node.left.update_balances()
                if self.node.right:
                    self.node.right.update_balances()

            self.balance = self.node.left.height - self.node.right.height
        else:
            self.balance = 0 

            
    def rotate_right(self):
        """
        Right rotation
            set self as the right subtree of left subree
        """
        new_root = self.node.left.node
        new_left_sub = new_root.right.node
        old_root = self.node

        self.node = new_root
        old_root.left.node = new_left_sub
        new_root.right.node = old_root

    def rotate_left(self):
        """
        Left rotation
            set self as the left subtree of right subree
        """
        new_root = self.node.right.node
        new_left_sub = new_root.left.node
        old_root = self.node

        self.node = new_root
        old_root.right.node = new_left_sub
        new_root.left.node = old_root

    def delete(self, key):
        """
        Delete key from the tree

        Let node X be the node with the value we need to delete, 
        and let node Y be a node in the tree we need to find to take node X's place, 
        and let node Z be the actual node we take out of the tree.

        Steps to consider when deleting a node in an AVL tree are the following:

            * If node X is a leaf or has only one child, skip to step 5. (node Z will be node X)
                * Otherwise, determine node Y by finding the largest node in node X's left sub tree 
                    (in-order predecessor) or the smallest in its right sub tree (in-order successor).
                * Replace node X with node Y (remember, tree structure doesn't change here, only the values). 
                    In this step, node X is essentially deleted when its internal values were overwritten with node Y's.
                * Choose node Z to be the old node Y.
            * Attach node Z's subtree to its parent (if it has a subtree). If node Z's parent is null, 
                update root. (node Z is currently root)
            * Delete node Z.
            * Retrace the path back up the tree (starting with node Z's parent) to the root, 
                adjusting the balance factors as needed.
        """
        if self.node != None:
            if self.node.key == key:
                # Key found in leaf node, just erase it
                if not self.node.left.node and not self.node.right.node:
                    self.node = None
                # Node has only one subtree (right), replace root with that one
                elif not self.node.left.node:                
                    self.node = self.node.right.node
                # Node has only one subtree (left), replace root with that one
                elif not self.node.right.node:
                    self.node = self.node.left.node
                else:
                    # Find  successor as smallest node in right subtree or
                    #       predecessor as largest node in left subtree
                    successor = self.node.right.node  
                    while successor and successor.left.node:
                        successor = successor.left.node

                    if successor:
                        self.node.key = successor.key

                        # Delete successor from the replaced node right subree
                        self.node.right.delete(successor.key)

            elif key < self.node.key:
                self.node.left.delete(key)

            elif key > self.node.key:
                self.node.right.delete(key)

            # Rebalance tree
            self.rebalance()

    def inorder_traverse(self):
        """
        Inorder traversal of the tree
            Left subree + root + Right subtree
        """
        result = []

        if not self.node:
            return result
        
        result.extend(self.node.left.inorder_traverse())
        result.append(self.node.key)
        result.extend(self.node.right.inorder_traverse())

        return result

    def display(self, node=None, level=0):
        if not node:
            node = self.node

        if node.right.node:
            self.display(node.right.node, level + 1)
            print(('\t' * level), ('    /'))

        print(('\t' * level), node)

        if node.left.node:
            print(('\t' * level), ('    \\'))
            self.display(node.left.node, level + 1)

tree = avltree()
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

from random import randrange
for key in data:  
    tree.insert(key)

#for key in [4,3]:
#    tree.delete(key)

print(tree.inorder_traverse())
tree.display()<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
			 11
		     /
		 10
		     \
			 9
	     /
	 8
	     \
			 7
		     /
		 6
		     \
			 5
     /
 4
     \
		 3
	     /
	 2
	     \
		 1
{'fraction_non_alphanumeric': 0.10546245919477693, 'fraction_numerical': 0.01027203482045702, 'mean_word_length': 1.3728183414231128, 'pattern_counts': {'":': 3, '<': 19, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '29875', 'license': 'Unlicense', 'n_tokens_mistral': 6947, 'n_tokens_neox': 6521, 'n_words': 2039, 'path': 'BSTTree.ipynb', 'repo_name': 'jfogarty/python-code-practice', 'size': '22985'}