Support Binary Search Tree in Solidity

maxareo · January 6, 2024, 12:46pm

Hi there, I found two examples of binary search tree written in Solidity given below and I'm wondering if OpenZeppelin has any plan implementing a formal version of this extremely useful data structure. Thanks.

github.com

rob-Hitchens/OrderStatisticsTree/blob/master/contracts/HitchensOrderStatisticsTreeLib.sol

pragma solidity 0.5.1;

/* 
Hitchens Order Statistics Tree v0.99

A Solidity Red-Black Tree library to store and maintain a sorted data
structure in a Red-Black binary search tree, with O(log 2n) insert, remove
and search time (and gas, approximately)

https://github.com/rob-Hitchens/OrderStatisticsTree

Copyright (c) Rob Hitchens. the MIT License

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

This file has been truncated. show original

github.com

d3or/sol-trees/blob/master/src/BinaryTree.sol

//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.0;

contract BinaryTree {
    struct Node {
        uint256 value;
        bytes32 left;
        bytes32 right;
    }
    
    mapping (bytes32 => Node) private tree;
    
    bytes32 private rootAddress;
    constructor() {}

    
    /* 
        * These are insertion and deletion functions.
            - Insertion (average log(n)), worst case O(n)):
                - Start at the root node (rootAddress)

This file has been truncated. show original

ernestognw · January 8, 2024, 3:22pm

Hey @maxareo,

We currently don't have plans to support a binary tree data structure but are open to it if there's a demanded general use case that we can fit in the library.

Seems like the HitchensOrderStatisticTreeLib is too specialized and is unclear what the BinaryTree would be used for. Do you know concrete popular use cases of binary trees out there?

maxareo · January 8, 2024, 3:57pm

I thought Binary Search Tree is a fundamentally useful data structure in maintaining a sorted array of values such that fast verification, insertion and retrieval can be done in O(1) complexity. I could not think of a use case immediately, but given how fundamental this truly is, it may open up many use cases, just like how this sorted double linked list made the project Liquity possible.

github.com

livepeer/protocol/blob/master/contracts/libraries/SortedDoublyLL.sol

pragma solidity ^0.4.17;

import "zeppelin-solidity/contracts/math/SafeMath.sol";


/*
 * @title A sorted doubly linked list with nodes sorted in descending order. Optionally accepts insert position hints
 *
 * Given a new node with a `key`, a hint is of the form `(prevId, nextId)` s.t. `prevId` and `nextId` are adjacent in the list.
 * `prevId` is a node with a key >= `key` and `nextId` is a node with a key <= `key`. If the sender provides a hint that is a valid insert position
 * the insert operation is a constant time storage write. However, the provided hint in a given transaction might be a valid insert position, but if other transactions are included first, when
 * the given transaction is executed the provided hint may no longer be a valid insert position. For example, one of the nodes referenced might be removed or their keys may
 * be updated such that the the pair of nodes in the hint no longer represent a valid insert position. If one of the nodes in the hint becomes invalid, we still try to use the other
 * valid node as a starting point for finding the appropriate insert position. If both nodes in the hint become invalid, we use the head of the list as a starting point
 * to find the appropriate insert position.
 */
library SortedDoublyLL {
    using SafeMath for uint256;

    // Information for a node in the list

This file has been truncated. show original

Topic		Replies	Views
Which custom data structures do you use in Solidity? General	5	3169	June 3, 2021
Solidity implementation for Skip list? Support	1	1315	February 11, 2021
Will there be an OpenZeppelin Contracts implementation of exponentiation by squaring algorithm? General	3	1522	March 20, 2020
Why is abdk-libraries not in OpenZeppelin Contracts? Contracts	1	1329	December 22, 2020
Designing Fixed Point Math in OpenZeppelin Contracts General	30	10263	May 15, 2021

Support Binary Search Tree in Solidity

Related Topics