{"id":418,"date":"2024-04-21T09:06:00","date_gmt":"2024-04-21T08:06:00","guid":{"rendered":"https:\/\/noiseonthenet.space\/noise\/?p=418"},"modified":"2024-04-21T20:55:41","modified_gmt":"2024-04-21T19:55:41","slug":"embedding-a-binary-tree","status":"publish","type":"post","link":"https:\/\/noiseonthenet.space\/noise\/2024\/04\/embedding-a-binary-tree\/","title":{"rendered":"Embedding a (binary) Tree"},"content":{"rendered":"

\"rutpratheep-nilpechr-P5tWtdtY2AY-unsplash_reduced.jpg\" <\/p> <\/div>\n\n

Photo by Rutpratheep Nilpechr<\/a> on Unsplash<\/a> <\/p>\n\n

In this post I will show how to create a binary tree in Rust language, which is suitable to be used in embedded devices <\/p>\n\n

Here is the journey so far; I will mention some of the concepts already described in these posts. <\/p>\n\n

    \n
  1. Growing a (binary) Tree<\/a><\/li>\n
  2. Growing a (sorting) Tree<\/a><\/li>\n
  3. Stacking Bits<\/a><\/li>\n
  4. Prime Time<\/a><\/li>\n
  5. Climbing a (binary) Tree<\/a><\/li>\n<\/ol>\n\n

    The code for this post is here<\/a>. <\/p>\n\n

    So far we created and explored trees which grow into the application heap<\/b> memory, this allowed us to have almost arbitrary size and use the type system to guarantee consistent states <\/p>\n\n

    What if we cannot use the heap? This happens in some “embedded” devices, which are an important target of Rust. <\/p>\n\n

    Our trees will have a maximum height (or depth using mainstream jargon) and this may seem a hard limitation, but has interesting cases in machine learning. <\/p>\n\n

    To simulate this case we are going to add the following line at the beginning of our file <\/p>\n\n

    \n
    #!<\/span>[<\/span>no_std<\/span>]<\/span>\n<\/pre>\n<\/div>\n\n
     This completely disable any access to the heap, as well as other libraries which may not work on bare metal platforms. <\/p>\n\n
     Let’s dive in. <\/p>\n
    \n
    Choosing compromises<\/h2>\n
    \n
     
    \"egor-myznik-DRs9XsNlAZw-unsplash._reduced.jpg\" <\/p> <\/div>\n\n
     Photo by Egor Myznik<\/a> on Unsplash<\/a> <\/p>\n\n
     When developing code we may have constraints of memory size, execution time, storage size, I\/O throughput, computation cores available. <\/p>\n\n
     Dealing with these constraints may require to give up perfect solutions and use some approximations; choosing carefully these approximations and account for the errors we expect is a critical path of a software architecture. <\/p>\n<\/div>\n
    \n
    Size compromise<\/h3>\n
    \n
     By forcing our data structure to work in the stack we need to know its size in advance<\/b> thus: <\/p>\n\n