www.delorie.com/gnu/docs/avl/libavl_fot.html | search |
Buy GNU books! | |
[Top] | [Contents] | [Index] | [ ? ] |
External names are identifiers visible outside a single source file. These are, mainly, non-static functions and variables declared outside a function.
This sort of notation means very different things in C and mathematics. In mathematics, writing a < b < c asserts both of the relations a < b and b < c, whereas in C, it expresses the evaluation of a < b, then the comparison of the 0 or 1 result to the value of c. In mathematics this notation is invaluable, but in C it is rarely meaningful. As a result, this book uses this notation only in the mathematical sense.
These uses of the words "static" and "dynamic" are different from their meanings in the phrases "static allocation" and "dynamic allocation." See section C. Glossary, for more details.
Some of these terms are not generic BST vocabulary. Rather, they have been adopted for these particular uses in this text. You can consider the above to be our working definitions of these terms.
This is possible in some other languages, such as Scheme, that support "coroutines" as well as subroutines.
These colors are for the purpose of illustration only. They are not stored in the nodes and are not related to those used in a red-black tree (see red-black tree).
The ** notation in the diagram emphasizes that this is a counterexample.
Some might scoff at this amount of detail, calling it wasted effort, but this thorough testing in fact revealed a number of subtle bugs during development of libavl that had otherwise gone unnoticed.
This seems true intuitively, but there are some difficult mathematics in this area. For details, refer to [ Knuth 1998b] theorem 6.2.2H, [ Knuth 1977], and [ Knuth 1978].
Here log2 is the standard C base-2 logarithm function, pow is the exponentiation function, and ceil is the "ceiling" or "round up" function. For more information, consult a C reference guide, such as [ Kernighan 1988].
We could make a list of the nodes as we move down the tree and reuse it on the way back up. We'll do that for deletion, but there's a simpler way for insertion, so keep reading.
A "prime" (') is traditional, but primes are easy to overlook.
This usage of "thread" has nothing to do with the idea of a program with multiple "threads of excecution", a form of multitasking within a single program.
It can be efficient if we use a stack to do it, but that kills the advantage of threading the tree. It would be possible to implement two sets of traversers for right-threaded trees, one with a stack, one without, but in that case it's probably better to just use a threaded tree.
This abbreviation might be thought of as
expanding to "parented BST" or "parental BST", but those are not
proper terms.
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |