search

exported / execap

Automatically exported from code.google.com/p/execap
GNU General Public License v3.0
0 stars 0 forks source link

The hybrid hash+AVL tree needs to be documented #9

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
To reduce the height of the binary tree, a bunch of trees are created, one for 
each bucket of a hash table.  How this works needs to be documented otherwise 
it will be hard for others to hack the data structure.

Original issue reported on code.google.com by bmenr...@ucsd.edu on 5 Jan 2011 at 12:12

GoogleCodeExporter commented 9 years ago 
I think I should change from an AVL tree to a Red-Black tree.  The AVL tree 
stays very well balanced but at high insertion and deletion cost.  Since one 
would assume most network traffic is "randomly" ordered (especially considering 
the "hash" selects which tree gets used) so the trees probably do a pretty good 
job of staying balanced on their own.  A slight out-of-balance is no big deal 
so saving the time by not aggressively re-balancing will probably be a win.

Original comment by bmenr...@ucsd.edu on 19 May 2011 at 4:36

GoogleCodeExporter commented 9 years ago

Original comment by bmenr...@ucsd.edu on 22 May 2011 at 5:35