Please
note that "get leftmost key" operation was not O(1) in Lua 5.3, see the
following example:
while next(t) do t[next(t)] = nil end
#(3) Operations "move M elements to the left/right" will be O(log(N)) for large M.
Hence, we could access a table in a specific way which is independent on the base index:
old style: tbl[1] new style: get_leftmost(tbl)
old style: tbl[5] new style: move_right(get_leftmost(tbl), 4)
Of course, this syntax is not neat, it just gives the idea of operation.
#(4) Operation "split diapason key1..key2 into two equal parts" will be O(log(N)).
The primitive "dichotomy the range of keys" might be useful for many cases, including parallelization.
#(5) Balanced trees are immune to DDOS attacks (unlike hash-tables).
Lua would not have to pseudo-randomly shuffle the order of keys used by
next()
function on each VM initialization.
Sequence of keys generated by pairs() will be deterministic
(unless tables are used as keys).
For example, it would be convenient if all numerical keys go in their natural order when traversed with pairs():
-1.5, 0, 1, 2, 3, math.pi, 4, ..., math.huge
#(6) Memory block size for storing a balanced tree may be not equal to a power of 2 (as for hash tables).
For example, when extending a "tree" part of a growing table, any memory block 2x...4x of the previous size would be OK.
Memory for storing a balanced tree also can be fragmented into several continuous chunks without making the implementation more slower or more complex (unlike hash-tables).
These would make memory manager's life a bit easier.
Drawbacks:
#(-1) Table indexing will be slightly slower (hash tables, despite of collisions when indexing, are faster than balanced trees).
#(-2) Tables would take more memory (trees consume more space than hash-tables).
#(-3) Didn't actually solve the "problem of accustomed 0-based arrays".