Hide minor edits - Show changes to markup
October 22, 2006, at 10:42 AM
October 22, 2006, at 10:41 AM
Added lines 1-7:
Threaded AVL trees ("tavl trees") are binary search trees in which nodes with no left and/or right pointer hijack the empty pointers to refer back to their parent. This provides the following nice properties:
- Fast in-order traversal, nearly as fast as a linked list.
- In-order traversal that requires a only a reference to the current node, instead of an implicit or explicit stack, which is necessary for traditional trees. This allows tavl trees to be robust against modifications during traversal, and also stack overflow.
See Ben Pfaff's GNU libavl for a discussion of threaded AVL trees and a list of tree implementations, including his own. Ben's implementation is released under the GPL, which precludes Hex Fiend from using it; therefore Hex Fiend uses Bert Hughes's public domain implementation here. Much gratitude to Bert, wherever he is.
TavlTreeByteArray uses a tavl tree as its data representation.