A Merkle tree is a tree that defines each non-leaf node with a value or a label and contains a hash of its children. This builds a hash trees and are used to provide a verification of large-scale data structures.
Merkle tree - hash tables |
Coding
The following is an outline:
from hippiehug import Tree from hippiehug import Leaf import sys import binascii def utf8ify(list): '''Encode a list of strings in utf8''' return [item.encode('utf8') for item in list] vals = ['Hello', 'World'] search = "Hello" if (len(sys.argv)>1): v=sys.argv[1] vals = eval(v) if (len(sys.argv)>2): search=str(sys.argv[2]) print("Input values:",vals) print("Search:",search) print("\n") t = Tree() t.multi_add(utf8ify(vals)) val = search.encode() in t if (val==True): print(search, "is in the tree") else: print(search, "is not in the tree") print("Root:",binascii.hexlify(t.root())) print("\n\nLeaf method") l = Leaf(vals[0].encode(),key=vals[0].encode()) store = {l.identity() : l} for item in vals: b = l.add(store, item.encode(),key=item.encode()) print("Leaf identity:",binascii.hexlify(l.identity())) print (store) val = search.encode() in store if (val==True): print(search, "is in the tree") else: print(search, "is not in the tree")