ancestors: in a tree, the union of a node's parent and the parent's ancestors.
array: A contiguous block of memory containing elements of the same type, accessed by numeric index.
association list: a list of pairs, where each pair has a key and a value associated with the key.
backtrack: in a tree search, to move back from the node currently being examined to its parent.
base case: a simple case that can be solved easily, without recursion.
Big O: an abstracted function that describes the amount of computer time or memory space required by an algorithm, as a function of problem size. For problems larger than a certain size, the actual time or space required will be less than the Big O multiplied by some constant.
binary tree: a tree in which each node has at most two children.
binary search: search of a binary tree or other structure, in which the size of the set to be searched is cut in half at each step.
boxed number: a number that is defined as an object, so that it has a runtime type and methods that can be used, e.g. Integer in Java.
branching factor: in a search tree, the number of children of a given node. Often, the branching factors of individual nodes will vary, so an average value may be used.
child: in a tree, a node pointed to by a parent node.
circularly linked list: a linked list in which the last element points back to the first element.
circular queue: a queue implemented within an array, where the first element of the array logically follows the last element.
class: in object-oriented programming, a description of a set of similar objects.
cons: 1. in Lisp, the function that constructs a pair of pointers, or basic element of list structure. 2. to make a cons data structure. 3. a cons data structure.
constructive: describes a function that makes a new data structure but does not modify its arguments.
depth: the number of links between the root of a tree and the leaves.
depth-first search: a search in which children of a node are considered (recursively) before siblings are considered.
dereference: to convert from a pointer (address) to the data that is pointed to.
descendants: all nodes below a given node in a tree.
design pattern: a pattern that describes a set of similar programs.
destructive: describes a function that modifies its arguments.
DFS: depth-first search.
divide and conquer: a problem-solving strategy in which a problem is broken down into sub-problems, until simple subproblems are reached.
doubly linked list: a linked list in which each element has both forward and backward pointers.
fair: describes a process in which every arriving customer will eventually be served.
FIFO: first-in, first-out: describes the ordering of a queue.
filter: a process that removes unwanted elements from a collection.
first-child/next-sibling: a way of implementing trees that uses two pointers per node but can represent an arbitrary number of children of a node.
garbage: storage that is no longer pointed to by any variable and therefore can no longer be accessed.
garbage collection: the process of collecting garbage for recycling.
gedanken: describes a thought experiment or view of an entity.
goal: an item (or description of items) being sought in a search.
grammar: a formal description of a language in terms of vocabulary and rules for writing phrases and sentences.
immutable: describes a data structure that cannot be changed once it has been created, such as Integer or String in Java.
inorder: an order of processing a tree in which the parent node is processed in between its children.
interior node: a node of a tree that has children.
intersection: given two sets, the intersection is the set of elements that are members of both sets.
intractable: a problem that is so hard (typically exponential) that it cannot be solved unless the problem is small.
leaf: a tree node containing a contents value but with no children.
LIFO: last-in, first out: describes the order of a stack.
linear: O(n), a problem whose solution requires a linear amount of time or space if the problem is of size n.
link: a pointer to the next element in a linked list.
linked list: a sequence of records, where each record contains a link to the next one.
merge: to combine two ordered linear structures into one.
node: an element of a linked list, tree, or graph, often represented by a data structure.
null dereference: a runtime error that occurs when an operation such as a method call is attempted on a null pointer.
object: a data structure that can be identified at runtime as being a member of a class.
ontology: a description of the kinds of objects that exist in a computer program, e.g. a Java class hierarchy.
operator: in a search tree, a program that changes a state into a child state, e.g. a move in a game.
parent: in a tree, a node that points to a given node.
pointer: a variable containing the address of other data.
postorder: an order of processing a tree in which the parent node is processed after its children.
preorder: an order of processing a tree in which the parent node is processed before its children.
quadratic: O(n2), a problem whose solution requires a quadratic amount of time or space if the problem is of size n.
queue: a data structure representing a sequence of items, which are removed in the same order as they were inserted.
random access: describes a data structure or device in which all accesses have the same cost, O(1).
recursion: a case where a program calls itself.
recursive case: a condition of the input data where the data will be handled by call(s) to the same program.
reference: a pointer to data.
reference type: a type in which variables of that type are pointers to objects.
root: the top node of a tree, from which all other nodes can be reached.
runtime stack: a stack containing a stack frame of variable values for each active invocation of a procedure.
search: to look through a data structure until a goal object is found.
sentinel: an extra record at the start or end of a data structure such as a linked list, to simplify the processing.
set difference: given two sets, the set difference is the set of elements of the first set that are not members of the second set.
shadow: to hide similar items with the same name.
side-effect: any effect of a procedure other than returning a value, e.g. printing or modifying a data structure.
sort: to modify the order of a set of elements so that a desired ordering holds between them, e.g. alphabetic order.
stack frame: a section of the runtime stack holding the values of all variables for one invocation of a procedure.
stack space: the amount of space on the runtime stack required for execution of a program.
state: a description of the state of a process, such as a board game.
structure sharing: a case where two data structures share some elements.
successor: the next element in a linked list.
tail recursive: a function whose value either does not involve a recursive call, or is exactly the value of a recursive call.
taxonomy: a classification of objects into a tree structure that groups related objects.
union: given two sets, the union is the set of elements that are members of either set.
well-founded ordering: an ordering that can be guaranteed to terminate, e.g. starting at a positive integer and counting down to 0.
XML: Extensible Markup Language, a way of writing data in a tree-structured form by enclosing it in tags.