Computer Science terms in Abstract data types

A description of a collection of data in terms of the values it can hold and the operations that can be performed on it, independent of how the data is stored or how the operations are coded.

A self-balancing search tree in which each node holds many sorted keys and has many children, keeping the tree shallow so that few nodes need to be read from disk during a search.

A tree in which, at every node, the heights of the left and right subtrees differ by at most a small fixed amount (at most one in the strictest definition), so that the height stays close to ${\log }_{2}n$.

A binary tree in which, for every node, every value in its left subtree is less than the node's value and every value in its right subtree is greater.

A tree in which every node has at most two children, identified as the left child and the right child.

One position in a hash table's array, identified by an index, which holds the key or keys whose hash values lead to it.

A node directly below another node and linked to it by an edge; every node except the root is the child of exactly one parent.

A linked list in which the last node's reference points back to the first node, so the nodes form a closed loop with no null reference.

A tree in which every parent node has only one child, so the tree has the shape and performance of a linked list.

The set of elements that are in the first set but not in the second; written $A-B$ or $A\setminus B$.

A linked list in which each node has two references, one to the next node and one to the previous node, so the list can be traversed in both directions.

A link between a parent node and one of its children.

The situation in which two different keys produce the same index in a hash table.

A function that converts a key into a number used to choose its position in a hash table, always producing the same number for the same key.

A data structure that stores keys (or key–value pairs) in an array of buckets, using a hash function to calculate the bucket for each key so that it can be stored and found without searching.

The number produced by applying a hash function to a key; reduced modulo the table size, it gives the index of the key's bucket.

The reference to the first node of a linked list, from which every traversal starts; it is null or None when the list is empty.

The number of edges on the longest path from the root node down to a leaf; a tree with only a root has height 0.

The node that comes immediately after a given node in an in-order traversal; for a node with a right subtree, it is the smallest value in that right subtree.

A traversal of a binary tree that visits the left subtree, then the node itself, then the right subtree, applied recursively at every node.

The set of elements that are in both of two sets; written $A\cap B$.

An item of data made of a unique key, used to look the item up, and a value associated with that key.

A node with no children.

An open addressing method that, when the calculated index is occupied, tries index + 1, index + 2 and so on (wrapping round to 0 at the end of the table) until it finds a free bucket.

A dynamic data structure that stores a sequence of items in nodes, where each node holds a data item and a reference to the next node in the sequence.

The number of entries stored in a hash table divided by the number of buckets, $\alpha =n\mathrm{/}m$.

An abstract data type that stores key–value pairs with unique keys, with operations to add or update the value for a key, get the value for a key, remove a key and test whether a key is present.

The property of an element being present in a set; a membership test returns True if the element is in the set and False if it is not.

A single element of a linked structure, made up of a data field and one or more reference fields that point to other nodes.

A collision resolution strategy in which every entry is stored in the table's array itself; when a key's bucket is occupied, other buckets are tried in a fixed sequence until a free one is found.

A node that has one or more nodes directly below it, linked to it by edges.

A value that refers to the location of another item of data in memory; in a linked structure, a reference held in one node that leads to another node.

A traversal of a binary tree that visits the left subtree, then the right subtree, then the node itself, applied recursively at every node.

A traversal of a binary tree that visits the node itself first, then its left subtree, then its right subtree, applied recursively at every node.

Creating a larger hash table, usually about twice the size, and reinserting every existing entry by recalculating its index for the new size, carried out when the load factor passes a set threshold.

The single node at the top of a tree, which has no parent; every other node is reached by following edges down from it.

A collision resolution strategy in which each bucket holds a linked list (chain) of all the entries whose keys hash to that index.

An abstract data type that stores a collection of unique elements in no particular order, with operations to add and remove elements, test membership, and combine sets by union, intersection and difference.

A linked list in which each node has a single reference, to the next node, and the last node's reference is null or None.

A set $S$ is a subset of a set $A$, written $S\subseteq A$, if every element of $S$ is also an element of $A$.

A node of a tree together with all of the nodes below it, which itself forms a tree.

A set $A$ is a superset of a set $S$, written $A\supseteq S$, if $A$ contains every element of $S$; $A$ is a superset of $S$ exactly when $S$ is a subset of $A$.

A reference to the last node of a linked list, kept so that items can be added at the end without traversing the list.

A marker left in a slot of an open-addressing hash table when its key is deleted, so that searches continue past the slot while insertions may reuse it.

A non-linear, hierarchical data structure of nodes connected by edges, with one node at the top and every other node reached from it by exactly one path.

The set of all elements that are in either of two sets, or in both, with each element included once; written $A\cup B$.