Skip to content

106ohm/StackBST

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 

Repository files navigation

StackBST

stack-based Binary Search Tree (BST) implemented in the "struct of arrays" style. Actually, this is strongly inspired by the geeksforgeeks version.

Implementation choices

  • stack-based, i.e., no dynamic memory, cells are referred through integer indices. Total memory usage: (4*N+1)*5 bytes or so
  • "struct of arrays" style, i.e., there is no "node" structure so that key, left and right pointers are stored in arrays
  • the free list (data structure for custom memory allocation) is implemented through the nextInFreeList array, whose entries are -1 if the node is allocated and nonnegative otherwise, and freeListHead that points to the free list head

About

stack-based Binary Search Tree (BST) implemented in the "struct of arrays" style

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages