cher-nov/Gena

Enchance flexibility for gentree* containers

cher-nov opened this issue · 0 comments

  1. Separate binary tree structure from AVL tree implementation, leaving support for tree-specific data ("balance factor" for AVL, "color" for red-black, etc).
  2. Add other tree implementations: red-black, AA (made simple™), WAVL, etc.
  3. Allow to select necessary tree algorithm in instantiation macros by specifying either macro definition argument (e.g. GENA_2TREE_BACKEND_AVL, what is preferable and desirable) or constant interface structure with methods (like in interators now, but I would like to leave that approach there and won't apply it more anywhere).

Such functionality will be also needed for hash-based data structures in the future.

All of this is somewhat related to #18 because of multimap / multiset capabilities we need.

Also:

  1. Think about non-binary trees and their usability in such context (e.g. for multimaps / multisets).
  2. Think about the possibility of tree implementations with flattened array, which seems to be quite effective for balanced trees.
  3. Think about storing nodes in a realloc-based or chunk-based buffer.

https://en.wikipedia.org/wiki/Template:CS_trees
https://en.wikipedia.org/wiki/Template:Data_structures

https://lj.rossia.org/users/ketmar/1599420.html
http://lj.rossia.org/users/ketmar/1605246.html