-3

Binary Trees have a root node. Typically with such a data structure implementation, a function is provided to "peek" the root node, as well as the smallest and largest elements.

In other words, in Rust world, I would like to be able to do this:

let map = BTreeMap::new(); // contains T

map.first(); // -> Option<T>
map.last(); // -> Option<T>

I would have expected to find such a function in the documentation, but did not.

What I did find is a function called first_entry and similarly a function called last_entry.

I assume first_entry does something like what I want, but I don't understand how to use it since it returns a type OccupiedEntry. (doc link)

I would assume that first_entry is O(log(N)) and last_entry is O(log(N)), and should there be a similar function for the root, then that would be O(1). (Less important.)

FreelanceConsultant
  • 13,167
  • 27
  • 115
  • 225
  • The nomenclature is confusing but `BTreeMap` is **not a binary tree**, it's a [b-tree](https://en.wikipedia.org/wiki/B-tree). – Masklinn Aug 22 '23 at 08:13
  • @Masklinn either way, I would expect to have a function to "get the root" – FreelanceConsultant Aug 22 '23 at 08:15
  • 1
    The root of a btree is an internal node (though a special case thereof), it has no content. Hell, that barely make sense in binary trees, in a BST (like an rbtree or an avltree) the root is just a median-ish value. – Masklinn Aug 22 '23 at 08:21
  • Your complexity bounds also don't make sense, trees generally work in logarithmic time, why would `last_entry` ever be linear. That's the complexity of a sorted association list. – Masklinn Aug 22 '23 at 08:25
  • @Masklinn yes, don't know why I put `O(N)` there, have updated it – FreelanceConsultant Aug 22 '23 at 10:58

2 Answers2

1

first_entry() and last_entry() are for manipulating the entries. For just accessing them, there are first_key_value() and last_key_value().

If I understand correctly, both first and last functions are O(log N).

Chayim Friedman
  • 47,971
  • 5
  • 48
  • 77
-1

One possible way to make this work is as follows. (However there are better solutions described in other answers.)

There is a function on the object OccupiedEntry called get. This returns a reference to the underlying data.

https://doc.rust-lang.org/std/collections/btree_map/struct.OccupiedEntry.html#method.get

Dharman
  • 30,962
  • 25
  • 85
  • 135
FreelanceConsultant
  • 13,167
  • 27
  • 115
  • 225
  • The auxiliary object is just the interface map/set data structures in std use. The idea is that, while you hold this auxiliary object, depending on if you have an exclusive borrow, a shared borrow or own it, you don't have the same "rights" to access the underlying data, yet a single interface is provided. However, you don't *need* to go through it, you can also call [`first_key_value`](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#method.first_key_value) for instance. – jthulhu Aug 22 '23 at 08:09
  • 2
    This answer still reads as if you are asking another question. I would advise to stop using rhetorical questions. – Dharman Aug 28 '23 at 11:21
  • @Dharman it's not a rhetorical question? Why would you come to that conclusion? – FreelanceConsultant Aug 28 '23 at 12:42
  • 2
    Because this is an answer... You cannot expect to receive an answer to an answer. So either this is not an answer and should be removed, or it's a rhetorical question that is part of the solution you are providing. – Dharman Aug 28 '23 at 12:44