Python – Usage of a Binary Tree with List in Python

Posted on July 7, 2015 by

Vitosh Posted in Python

After the article here, concerning the building of the binary trees and their usefulness, today I will show how to use these trees in action 🙂

Imagine that we have the following problem, used in arena.hackbulgaria.com:

Implement a program in Java, Python or C++ which starts with an initial list of number and then implements the following two commands. set [index] [value] – replaces the value at index in the list with the specified value. index <= length of the list. min [start_index] [end_index] – returns the minimum value from the elements between start_index and end_index. start_index <= end_index. Indices in both operations are zero-based. The first line of the input will contain two integers – the length of the list and the number of commands. The second line of the input will contain the elements of the list, separated by space. Each of the following lines will contain a single command in the format specified above.

Example
Input	Output
16 8
19 11 15 4 7 13 11 2 3 5 12 7 23 17 4 6
min 0 4	4
min 5 10	2
set 4 3
min 4 8	2
min 0 6	3
set 15 8
min 15 15	8
min 10 13	7

And I have managed to achieve it with the help of a binary tree:

What have I done? Pretty much, I have made the following functions, to help me build the tree. This is their explanation, although their names are self-explanatory:

import math

def locate_parent(position,levels):
    #Locates a parent of the position, taking into account the levels above.

def logarithm(n):
    #log base 2 of n is m

def is_left(number):
    #answers whether the branch is left (true) or right

def get_parent_on_levels(node,level):
    #returns the node, on which a parent is located. 
    #or a grandparent, if the level is 2 :)

def set_value(position, number):
    #sets a value in the initial array.
    #then rebuilds part of the tree, to make sure it is still working

def create_a_binary_tree(list_first_line):
    #creates a binary tree from the given input

def parent_in_range(node_parent,a,b,level):
    #checks whether a node is a parent of given 2 other nodes.
    #levels are taken into account as well

def get_left_and_right_children(node, level):
    #gets the child which is in the leftmost position
    #and the child in the rightmost
    #concerning the level

def locate_minimal(a, b):
  #locates minimal value within two nodes

import math

def locate_parent(position,levels):

#Locates a parent of the position, taking into account the levels above.

def logarithm(n):

#log base 2 of n is m

def is_left(number):

#answers whether the branch is left (true) or right

def get_parent_on_levels(node,level):

#returns the node, on which a parent is located.

#or a grandparent, if the level is 2 :)

def set_value(position, number):

#sets a value in the initial array.

#then rebuilds part of the tree, to make sure it is still working

def create_a_binary_tree(list_first_line):

#creates a binary tree from the given input

def parent_in_range(node_parent,a,b,level):

#checks whether a node is a parent of given 2 other nodes.

#levels are taken into account as well

def get_left_and_right_children(node, level):

#gets the child which is in the leftmost position

#and the child in the rightmost

#concerning the level

def locate_minimal(a, b):

#locates minimal value within two nodes

Pretty much, that is all. 🙂 The functions work as they are supposed to.

If you need the whole code, it is available in GitHub here:

Or simply below:

import math

def locate_parent(position,levels):
    #Locates a parent of the position, taking into account the levels above.
    for i in range (0 ,levels):
        position = int((position-1)/2)
    return position

def logarithm(n):
    #log base 2 of n is m
    return int(math.log(n,2))

def is_left(number):
    #answers whether the branch is left (true) or right
    if number%2 ==1:
        return True
    else:
        return False

def get_parent_on_levels(node,level):
    #returns the node, on which a parent is located. 
    #or a grandparent, if the level is 2 :)
    while level>0:
        node = int((node-1)/2)
        level-=1
    return node

def set_value(position, number):
    #sets a value in the initial array.
    #then rebuilds part of the tree, to make sure it is still working
    position = starting_position+position
    tree[position] = number

    our_number = number
    our_position = position    
    
    while(True) and our_position != 0:     
        
        if is_left(number):
            compare_with = tree[our_position+1]
        else:
            compare_with = tree[our_position-1]
        
        if number= 0:
        tree[start_at] = min(tree[2*start_at+1], tree[2*start_at+2])
        start_at -= 1
    
    return tree

def parent_in_range(node_parent,a,b,level):
    #checks whether a node is a parent of given 2 other nodes.
    #levels are taken into account as well
    list_children = get_left_and_right_children(node_parent,level)
    if list_children[0]>=a and list_children[1]<=b:
        return True
    return False

def get_left_and_right_children(node, level):
    #gets the child which is in the leftmost position
    #and the child in the rightmost
    #concerning the level
    nodeRightChild = node
    nodeLeftChild = node
    
    while level>0:
        nodeLeftChild = 2*nodeLeftChild + 1
        nodeRightChild  = 2*nodeRightChild +2
        level-=1
    return ([nodeLeftChild, nodeRightChild])

#Input starts here
list_n_and_k = list(input().split())
list_n_and_k = list(map(int, list_n_and_k))

list_first_line = list(input().split())
list_first_line = list(map(int, list_first_line))

total_entries = list_n_and_k[1]
list_orders = []

for i in range (0, total_entries):
    order = []
    order = list(input().split())
    
    if order[0] != "min":
        order[0] = 0
    else:
        order[0] = 1
    
    order[1] = int(order[1])
    order[2] = int(order[2])
    list_orders.append(order)
#Input ends here

tree = create_a_binary_tree(list_first_line)
starting_position = int(len(tree)/2)

def locate_minimal(a, b):
  #locates minimal value within two nodes
    a+= starting_position
    b+= starting_position
    result = []
    
    if a%2 == 0:
        result.append( tree[a])
        a+=1
    if b%2 == 1:
        result.append(tree[b])
        b-=1
    while (a

100

101

102

103

104

105

106

107

108

109

110

import math

def locate_parent(position,levels):

#Locates a parent of the position, taking into account the levels above.

for i in range (0 ,levels):

position = int((position-1)/2)

return position

def logarithm(n):

#log base 2 of n is m

return int(math.log(n,2))

def is_left(number):

#answers whether the branch is left (true) or right

if number%2 ==1:

return True

else:

return False

def get_parent_on_levels(node,level):

#returns the node, on which a parent is located.

#or a grandparent, if the level is 2 :)

while level>0:

node = int((node-1)/2)

level-=1

return node

def set_value(position, number):

#sets a value in the initial array.

#then rebuilds part of the tree, to make sure it is still working

position = starting_position+position

tree[position] = number

our_number = number

our_position = position

while(True) and our_position != 0:

if is_left(number):

compare_with = tree[our_position+1]

else:

compare_with = tree[our_position-1]

if number= 0:

tree[start_at] = min(tree[2*start_at+1], tree[2*start_at+2])

start_at -= 1

return tree

def parent_in_range(node_parent,a,b,level):

#checks whether a node is a parent of given 2 other nodes.

#levels are taken into account as well

list_children = get_left_and_right_children(node_parent,level)

if list_children[0]>=a and list_children[1]<=b:

return True

return False

def get_left_and_right_children(node, level):

#gets the child which is in the leftmost position

#and the child in the rightmost

#concerning the level

nodeRightChild = node

nodeLeftChild = node

while level>0:

nodeLeftChild = 2*nodeLeftChild + 1

nodeRightChild = 2*nodeRightChild +2

level-=1

return ([nodeLeftChild, nodeRightChild])

#Input starts here

list_n_and_k = list(input().split())

list_n_and_k = list(map(int, list_n_and_k))

list_first_line = list(input().split())

list_first_line = list(map(int, list_first_line))

total_entries = list_n_and_k[1]

list_orders = []

for i in range (0, total_entries):

order = []

order = list(input().split())

if order[0] != "min":

order[0] = 0

else:

order[0] = 1

order[1] = int(order[1])

order[2] = int(order[2])

list_orders.append(order)

#Input ends here

tree = create_a_binary_tree(list_first_line)

starting_position = int(len(tree)/2)

def locate_minimal(a, b):

#locates minimal value within two nodes

a+= starting_position

b+= starting_position

result = []

if a%2 == 0:

result.append( tree[a])

a+=1

if b%2 == 1:

result.append(tree[b])

b-=1

while (a

Enjoy it!

Tagged with: binary list usage, binary tree list, binary tree list in python, Python, range minimal query

Python – Usage of a Binary Tree with List in Python

Related posts: