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.

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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!