Splay Tree

import splay_h as sp

def print_splay_tree(node, x):
    if node is not None:
        print_splay_tree(node.left, x+1)
        print("  " * x, node.data)
        print_splay_tree(node.right, x+1)

# print tree simply with appropriate indent
# the left-most node is the root of tree
def print_simple(node, title):
    print(title)
    print_splay_tree(node, 0)
    print('')

# retrieve node with the specified key, but do not splay.
def find_no_splay(node, x):
    if node is None:
        return None
    if node.data == x:
        return node
    elif x > node.data:
        return find_no_splay(node.right, x)
    else:
        return find_no_splay(node.left, x)

# prepare sample tree
def sample():
    a = None
    a = sp.insert(a, 0)
    a = sp.insert(a, 1)
    a = sp.insert(a, 2)
    a = sp.insert(a, 3)
    a = sp.insert(a, 4)
    a = sp.insert(a, 5)
    a = sp.insert(a, 6)
    a = sp.insert(a, 7)

    a, _ = sp.search(a, 2)
    a, _ = sp.search(a, 3)
    a, _ = sp.search(a, 1)
    a, _ = sp.search(a, 6)
    a, _ = sp.search(a, 5)
    return a



print('### Visualization of zig-zig ###\n')

tree1 = sample()
print_simple(tree1, 'Original splay tree: ')

partial1 = find_no_splay(tree1, 3)
print_simple(partial1, 'Partial tree of node 3: ')

partial1 = sp.rotate_right(partial1)
print_simple(partial1, 'After zig at node 3: ')

partial1 = sp.rotate_right(partial1)
print_simple(partial1, 'After zig at node 1: ')

actual1, _ = sp.search(sample(), 0)
print_simple(actual1, "Actual result after searching '0': ")

print('### Visualization of zig-zag ###\n')

tree2 = sample()
print_simple(tree2, 'Original splay tree: ')

partial2_1 = find_no_splay(tree2, 3)
partial2_2 = find_no_splay(tree2, 1)
print_simple(partial2_1, 'Partial tree of node 3: ')

partial2_1.left = sp.rotate_left(partial2_2)
print_simple(partial2_1, 'After zig at node 1: ')

partial2_1 = sp.rotate_right(partial2_1)
print_simple(partial2_1, 'After zag at node 3: ')

actual2, _ = sp.search(sample(), 2)
print_simple(actual2, "Actual result after searching '2': ")

from splay import SplayTree
# from splay_h import Splaytree as SplayTreeH
from standard import BinaryTree
from normal_dist import randint_nd
from random import randrange

'''
check balance of normal tree and splay tree
'''

MAX_KEY = 100000
MIN_KEY = 0

def show_result(st, bt):
    '''
    show count of nodes and maxLevel of tree.
    '''
    print('count of splay tree:', st.count())
    print('count of binary tree:', bt.count())
    print('max_level of splay tree:', st.max_level())
    print('max_level of binary tree:', bt.max_level())

def measure_random_insert():
    '''
    insert random keys
    '''
    st = SplayTree()
    bt = BinaryTree()
    for i in range(0, 100000):
        random_key = randrange(1, 100000)
        st.insert(random_key)
        bt.insert(random_key)
    show_result(st, bt)

def measure_random():
    '''
    combination of insert, find and delete
    '''
    st = SplayTree()
    bt = BinaryTree()
    for i in range(0, 10000):
        command = randrange(1, 10)
        random_key = randrange(1, MAX_KEY)
        if command < 5:
            st.insert(random_key)
            bt.insert(random_key)
        elif command < 9:
            st.find(random_key)
            bt.find(random_key)
        else:
            st.delete(random_key)
            bt.delete(random_key)
    show_result(st, bt)

def measure_ordered():
    '''
    process items in ascending order
    '''
    st = SplayTree()
    bt = BinaryTree()
    for i in range(1, 1000):
        command = randrange(1, 10)
        key = i
        if command < 5:
            st.insert(key)
            bt.insert(key)
        elif command < 9:
            key = randrange(1, i+1)
            st.find(key)
            bt.find(key)
        else:
            key = randrange(1, i+1)
            st.delete(key)
            bt.delete(key)
    show_result(st, bt)

def measure_nd():
    '''
    process items with key generatedy by peudo normal distribution
    '''
    st = SplayTree()
    bt = BinaryTree()
    keys = randint_nd(1, 10000, 100000)
    for random_key in keys:
        command = randrange(1, 10)
        if command < 5:
            st.insert(random_key)
            bt.insert(random_key)
        elif command < 9:
            st.find(random_key)
            bt.find(random_key)
        else:
            st.delete(random_key)
            bt.delete(random_key)
    show_result(st, bt)

if __name__ == '__main__':
    print('# measure_random_insert')
    measure_random_insert()
    print('# measure_random')
    measure_random()
    print('# measure_ordered')
    measure_ordered()
    print('# measure_nd')
    measure_nd()

import scipy.stats as ss
import numpy as np
import matplotlib.pyplot as plt

'''
# original code from http://stackoverflow.com/questions/37411633/how-to-generate-a-random-normal-distribution-of-integers
x = np.arange(-10, 11)
xU, xL = x + 0.5, x - 0.5

# norm means normal distribution
# cdf means 'cumulative density function'(累積分布関数)
# cdf(x: position, loc: expected value, scale: standard deviation)
prob = ss.norm.cdf(xU, scale = 3) - ss.norm.cdf(xL, scale = 3)
prob = prob / prob.sum()
print(prob)

nums = np.random.choice(x, size = 10000, p = prob)
plt.hist(nums, bins = len(x))
plt.show()
'''

def randint_nd(start, end, num=1, show_hist=False):
    # set random range, expected value, and pseudo standard deviation
    r_range = int(end - start)
    r_av = int((end + start) / 2)
    r_sd = int(r_range / 6)

    # get random value
    x = np.arange(-1 * (r_range / 2), (r_range / 2) + 1)
    xU, xL = x + 0.5, x - 0.5
    prob = ss.norm.cdf(xU, scale = r_sd) - ss.norm.cdf(xL, scale = r_sd)
    prob = prob / prob.sum()
    nums = np.random.choice(x, size = num, p = prob) + r_av

    # show histgram
    if show_hist:
        plt.hist(nums, bins = len(x))
        plt.show()
    return nums.tolist()