描述 Merkle Tree是密码学中一种非常重要的数据结构。它可以高效、安全的验证大量数据的完整性。本题考虑二叉Merkel tree和上面的主要操作，其结构如下图（来源：Wikipedia）。

给定初始输入数据后，Merkle tree首先使用哈希函数将每个数据块映射到固定长度字符串，其满足以下性质：（1）给定输入字符串，可以很快地计算输出字符串；（2）给定输出字符串，很难找出对应的输入字符串；（3）很难找到两个不同的输入字符串对应相同的输出字符串，即通常所说的哈希碰撞。选手可直接调用SHA256哈希函数，其使用方式如下： Python： import hashlib def SHA256(input):     return hashlib.sha256(input.encode('utf-8')).hexdigest() Java： import java.nio.charset.StandardCharsets; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException;

public class SHA256{     public static String SHA256(String input) {         try {             MessageDigest digest = MessageDigest.getInstance("SHA-256");             byte[] hashBytes = digest.digest(input.getBytes(StandardCharsets.UTF_8));                         StringBuilder hexString = new StringBuilder();             for (byte b : hashBytes) {                 String hex = Integer.toHexString(0xff & b);                 if (hex.length() == 1) {                     hexString.append('0');                 }                 hexString.append(hex);             }                         return hexString.toString();         } catch (NoSuchAlgorithmException e) {             throw new RuntimeException(e);         }     } }

其中输入长度不限，输出长度为32字节。

*Merkle Tree每个叶节点存储一个数据块的哈希值，按照从左到右的顺序依次存储。 *在本题中我们考虑平衡二叉Merkle Tree：每个非根节点都有兄弟节点；且对于每个非叶节点，其左子树的叶节点个数大于等于右子树的叶节点个数，但最多只相差1； *每个非叶节点存储两个子节点的存储内容拼接后的字符串的哈希值，拼接时左子节点的内容在前，右子节点的内容在后。

例如，对于只有三个数据块的输入[‘aaa’, ‘bbb’, ‘ccc’] 构造Merkle Tree，则对应的哈希值分别为： Hash00 = SHA256(‘aaa’) = 9834876dcfb05cb167a5c24953eba58c4ac89b1adf57f28f2f9d09af107ee8f0

Hash01 = SHA256(’bbb’) = 3e744b9dc39389baf0c5a0660589b8402f3dbb49b89b3e75f2c9355852a3c677

Hash0 = SHA256(‘9834876dcfb05cb167a5c24953eba58c4ac89b1adf57f28f2f9d09af107ee8f03e744b9dc39389baf0c5a0660589b8402f3dbb49b89b3e75f2c9355852a3c677’) = 7607b2809ae92fffc220deb8af1e4c2878180c29e9f861d79efb0f8bb9961548

Hash1 = SHA256(‘ccc’) = 64daa44ad493ff28a96effab6e77f1732a3d97d83241581b37dbd70a7a4900fe

root = SHA256(‘7607b2809ae92fffc220deb8af1e4c2878180c29e9f861d79efb0f8bb996154864daa44ad493ff28a96effab6e77f1732a3d97d83241581b37dbd70a7a4900fe’) = 985f0137b0de9241e51dbbe5285d8d717ccc464f65d4213d40dea34c5db2d061 你需要实现以下功能： 一、基础功能 1.树构造(tree-construction)：给定任意数量的原始数据块，构造Merkle tree并返回根节点的哈希值。 2.数据证明(data-proof)：在构造完Merkle tree后，输入任一原始数据块，输出其对应路径和路径上每个节点的兄弟节点的哈希值，哈希值之间用-相隔。接上例，当输入为’bbb’时，输出的证明为 01, Hash1-Hash00。如数据不在原始文件中，输出nil。 3.数据获取(data-fetch)：构造完Merkle tree后，输入一个路径，输出叶节点对应的数据块和功能2中的哈希序列作为证明。 4.数据检验(data-verification)：假设你从可信第三方获取了某个数据集的Merkle tree根节点的哈希值root，接下来从某个不可信的数据源获取了一个数据块L，声称的存储路径和功能2中对应的哈希序列。验证该数据块是否确实在Merkle tree中，验证方式为：从叶节点开始沿路径回溯，对每个节点计算其对应的哈希值，最终计算出根节点哈希值root’，验证root’=root。验证通过返回True，不通过返回False。根据Merkle tree的构造方法可知，（1）L对应的叶节点存储的是数据块本身的哈希值，（2）每个非叶节点所需的两个子节点的哈希值之一通过上一步计算得到，另一个从哈希序列中获取，两个值的拼接方式为0节点在前，1节点在后。 二、进阶功能 5.数据更新 (data-update)：构造完Merkle tree后，输入一个路径，该路径位置存储的数据块发生变化，Merkle Tree需要更新路径上相关的哈希值，并输出新的Merkle tree根节点的哈希值。 6.数据添加 (data-insertion)：构造完Merkle tree后，输入一个路径和新数据块，需要在该路径存储的数据块之后添加这个数据块。需要更新Merkle Tree，并保持平衡二叉树的结构，返回新的Merkle tree根节点的哈希值。 7.数据删除 (data-deletion)：构造完Merkle tree后，输入一个路径，需要删除这一位置上的数据块，并更新Merkle Tree，保持二叉平衡树，返回新的Merkle tree根节点的哈希值。