Abstract Data Type : A set of data values and associated operations that are precisely specified independent of any particular implementation. Also known as ADT
Algorithm : A computable set of steps to achieve a desired result.
Alias : An alternative name for the same object. A "nickname".
Ancestor : A parent of a node in a tree, the parent of the parent, etc.
Argument : A value passed to a called function by the calling function.
Array : In programming, a list of data values, all of the same type, any element of which can be referenced by an expression consisting of the array name followed by an indexing expression. Arrays are part of the fundamentals of data structures, which, in turn, are a major fundamental of computer programming
AVL tree : A balanced binary search tree where the height of the two subtrees (children) of a node differs by at most one.
Balanced Binary Tree : A binary tree where no leaf is more than a certain amount farther from the root than any other. After inserting or deleting a node, the tree may rebalanced with "rotations."
big-O notation : A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".
Binary Heap : A complete binary tree where every node has a key more extreme (greater or less) than or equal to the key of its parent.
Binary Search : A type of search algorithm that seeks an item, with a known name, in an ordered list by first comparing the sought item to the item at the middle of the list's order. The search then divides the list in two, determines in which half of the order the item should be, and repeats this process, until the sought item is found.
Binary Search Tree : A data structure with in which every node refers to a left subtree and a right subtree such that all values in the left subtree are smaller than the value in the node and all elements in the right subtree are greater than (or equal to) the value in the node. The top node is called the root. The nodes with no children (left and right subtrees empty) are called leaves.
Binary Tree : A specific type of tree data structure in which each node has at most two subtrees, one left and one right. Binary trees are often used for sorting information; each node of the binary search tree contains a key, with values less than that key added to left subtree and values greater than that key added to the right subtree.
Bounded Queue : A queue limited to a fixed number of items.
Bubble Sort : Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.
Build-Heap : Convert an array into a heap by executing heapify progressively closer to the root. For an array of n nodes, this takes O(n) time under the comparison model.
Child : An item of a tree referred to by a parent item. Every item, except the root, is the child of some parent.
Circular List : A linked list in which the rear item refers back to the head item
Circular Queue : An implementation of a bounded queue using an array.
Collision : When two or more items should be kept in the same location, especially in hash tables, that is, when two or more different keys hash to the same value.
Collision Resolution Scheme : A way of handling collisions, that is, when two or more items should be kept in the same location, especially in a hash table. The general ways are keeping subsequent items within the table (open addressing), keeping a list for items which collide (direct chaining hashing or separate chaining hashing), keeping a special overflow area, etc. Perfect hashes avoid collisions, but may be time-consuming to create.
Complete Binary Tree : A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d
Data Object : An object capable of storing data. A variable or a constant. (A function is allocated memory within the computer and is therefore an object; but it is not a data object because it cannot store data).
Data Structure : The term data structure refers to the way data is organized for use within a program. Correct organization of data can lead to simpler and more efficient algorithms. Common data structures are linked-lists, stacks, queues and trees.
Descendant : A child of a node in a tree, any of the children of the children, etc.
Disjoint Set : A set whose members do not overlap, are not duplicated, etc.
Doubly Linked List : A data structure in which each element contains pointers to the next and previous elements in the list, thus forming a bidirectional linear list.
Dynamic Array : An array whose size may change over time. Items are not only added or removed, but memory used changes, too.
FIFO : First in first out is a policy that items are processed in order of arrival. A queue implements this.
full binary tree : A binary tree in which each node has exactly zero or two children.
Hash Function : A function that maps keys to integers, usually to get an even distribution on a smaller set of values.
Hash Table : A dictionary in which keys are mapped to array positions by a hash function. Having more than one key map to the same position is called a collision. There are many ways to resolve collisions, but they may be divided into open addressing, in which all elements are kept within the table, and chaining, in which additional data structures are used.
head : The first item of a list.
Heap : An area of memory from which space for dynamic structures are allocated
heap property : Each node in a tree has a key which is more extreme (greater or less) than or equal to the key of its parent.
heap. : A complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap.
Heapify : Rearrange a heap to maintain the heap property, that is, the key of the root node is more extreme (greater or less) than or equal to the keys of its children. If the root node's key is not more extreme, swap it with the most extreme child key, then recursively heapify that child's subtree. The child subtrees must be heaps to start.
Height : The maximum distance of any leaf from the root of a tree. If a tree has only one node (the root), the height is zero.
Huffman encoding : A minimal variable-length character encoding based on the frequency of each character. First, each character becomes a trivial tree, with the character as the only node. The character's frequency is the tree's frequency. The two trees with the least frequencies are joined with a new root which is assigned the sum of their frequencies. This is repeated until all characters are in one tree. One code bit represents each level. Thus more frequent characters are near the root and are encoded with few bits, and rare characters are far from the root and are encoded with many bits.
In-order Traversal : Process all nodes of a tree by recursively processing the left subtree, then processing the root, and finally the right subtree.
Infix Notation : A notation in which operators appear between the operands, as in 3 + 5
Insertion Sort : Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted.
Instance : A class is a definition of a set of data and member functions. When space for the data is actually allocated, we say that a member of the class has been instantiated. The instantiation is called an instance of the class. Each instance has its own set of data (there is also a mechanism in C++ to define data that is only allocated once per class, and shared amongst all instances of the class).
Internal Node : A node of a tree that has one or more child nodes, equivalently, one that is not a leaf
Key : The part of a group of data by which it is sorted, indexed, cross referenced, etc.
Leaf : Any node (location) in a tree structure that is at the farthest distance from the root (primary node), no matter which path is followed. Thus, in any tree, a leaf is a node at the end of a branch—one that has no descendants.
left rotation : In a binary search tree, pushing a node N down and to the left to balance the tree. N's right child replaces N, and the right child's left child becomes N's right child.
Level-order Traversal : Process all nodes of a tree by depth: first the root, then the children of the root, etc.
LIFO : Last in first out is a policy that the most recently arrived item is processed first. A stack implements this.
Linear Search : A simple, though inefficient, search algorithm that operates by sequentially examining each element in a list until the target element is found or the last has been completely processed. Linear searches are primarily used only with very short lists. Also called sequential search.
Linked List : A data structure in which a list of nodes or elements of a data structure connected by pointers. A singly linked list has one pointer in each node pointing to the next node in the list; a doubly linked list has two pointers in each node pointing to the next and previous nodes. In a circular list, the first and last nodes of the list are linked together.
max-heap property : Each node in a tree has a key which is less than or equal to the key of its parent.
Merge : Combine two or more sorted sequences of data into a single sorted sequence.
merge sort : A sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence.
min-heap property : Each node in a tree has a key which is greater than or equal to the key of its parent.
Name Tag : A name tag in C++ is a set of text characters formed into a symbolic word used to refer to an object. Name tags must start with an alpha character or an underscore. The second or subsequent characters can be alpha or numeric characters or the underscore character. All other characters are not allowed. Capital alpha characters can be used and are interpreted by C++ as different to their lower case equivalents.
Node : (1) A unit of reference in a data structure. Also called a vertex in graphs and trees. (2) A collection of information which must be kept at a single memory location.
null tree : A tree which is empty.
Object : Any program entity which uses physical memory in the computer
Object Oriented Programming : A concept of programming in which elements of the program are coded as stand alone objects. Each object is completely self contained in that it incorporates methods whereby the object can manipulate its own characteristics. A "Door" object, for instance would know how to open and close itself. It would also be able to respond to interrogation and advise the enquirer whether it is currently open or closed.
Open Addressing : A general collision resolution scheme for a hash table in which all items are stored within the table. In case of collision, other positions are computed and checked (a probe sequence) until an empty position is found. Some ways of computing possible new positions are less efficient because of clustering.
Overload : A term used to refer to the use of one symbol for more than one purpose. For instance, in mathematics the "-" symbol is used both as a negation symbol and as a subtraction symbol. In C++ the "<
Parameter : A value received by a called function from a calling function.
perfect binary tree : A binary tree with all leaf nodes at the same depth. All internal nodes have degree 2.
Postorder Traversal : Process all nodes of a tree by recursively processing the left subtree, then processing the right subtree, and finally the root.
Prefix Notation : A notation in which operators appear before the operands, as in +A B
Preorder Traversal : Process all nodes of a tree by recursively processing the root, then processing the left subtree, and finally the right subtree.
Queue : A data structure with first-in first-out behavior, supporting the operations enqueue (to insert) and dequeue (to remove)
Quicksort : An in-place sort algorithm that uses the divide and conquer paradigm. It picks an element from the array (the pivot), partitions the remaining elements into those greater than and less than this pivot, and recursively sorts the partitions
recursion : An algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task.
right rotation : In a binary search tree, pushing a node N down and to the right to balance the tree. N's left child replaces N, and the left child's right child becomes N's left child.
Root : The distinguished initial or fundamental item of a tree. The only item which has no parent
Rotation : To switch children and parents among two or three adjacent nodes to restore balance to a tree.
run time : The amount of time needed to execute an algorithm.
Selection Sort : A sort algorithm that repeatedly looks through remaining items to find the least one and moving it to its final location. The run time is (n2), where n is the number of comparisons. The number of swaps is O(n).
Sibling : A node in a tree that has the same parent as another node is its sibling.
Singly Linked List : A data structure in which a list of nodes or elements of a data structure connected by pointers. A singly linked list has one pointer in each node pointing to the next node in the list
Sort : Arrange items in a predetermined order. There are dozens of algorithms, the choice of which depends on factors such as the number of items relative to working memory, knowledge of the orderliness of the items or the range of the keys, the cost of comparing keys vs. the cost of moving items, etc.
Stack : A data structure with last-in first-out behavior, supporting the operations push (to insert) and pop (to remove)
Strictly Binary Tree : A binary tree is said to be a strictly binary tree if every non-leaf node in a binary tree has non-empty left and right subtrees.
String : A list of characters, usually implemented as an array. Informally a word, phrase, sentence, etc. Since text processing is so common, a special type with substring operations is often available.
Structure : A mechanism which allows objects of different types to be grouped together as a single compound type.
tail : The last item of a list.
threaded tree : A binary search tree in which each node uses an otherwise-empty left child link to refer to the node's in-order predecessor and an empty right child link to refer to its in-order successor.
Tree : A data structure containing zero or more nodes that are linked together in a hierarchical fashion
Tree Traversal : A technique for processing the nodes of a tree in some order.
uniform hashing : A conceptual method of open addressing for a hash table. A collision is resolved by putting the item in the next empty place given by a probe sequence which is independent of sequences for all other key.
Union : The union of two sets is a set having all members in either set.
vertex : An item in a graph. Sometimes referred to as a node.
worst case : The situation or input that forces an algorithm or data structure to take the most time or resources.