Free
Faster access than browser!

# Tree (data structure)

In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. [1]

69 relations: Abstract data type, Adjacency list, Ambient isotopy, Arborescence (graph theory), Array data structure, AVL tree, Binary heap, Binary search tree, Binary space partitioning, Binary tree, Branching factor, Breadth-first search, Cardinal Tree, Charles E. Leiserson, Clifford Stein, Computer science, Corecursion, Data structure, Day–Stout–Warren algorithm, Dialogue tree, Dictionary of Algorithms and Data Structures, Digital compositing, Directed graph, Donald Knuth, Enfilade (Xanadu), Family tree, Functional programming, Generative grammar, Graph (abstract data type), Graph (discrete mathematics), Graph theory, Heap (data structure), Hierarchical clustering, Hierarchical temporal memory, Hierarchy, Hierarchy (mathematics), Introduction to Algorithms, Left-child right-sibling binary tree, Linked list, List (abstract data type), Lowest common ancestor, Memory management, Multiple inheritance, Mutual recursion, Node (computer science), Ordinal Tree, Pruning (decision trees), Recursion, Recursive data type, Reference (computer science), ... Expand index (19 more) »

## Abstract data type

In computer science, an abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph.

## Ambient isotopy

In the mathematical subject of topology, an ambient isotopy, also called an h-isotopy, is a kind of continuous distortion of an ambient space, for example a manifold, taking a submanifold to another submanifold.

## Arborescence (graph theory)

In graph theory, an arborescence is a directed graph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph.

## Array data structure

In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.

## AVL tree

In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree.

## Binary heap

A binary heap is a heap data structure that takes the form of a binary tree.

## Binary search tree

In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store "items" (such as numbers, names etc.) in memory.

## Binary space partitioning

In computer science, binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes.

## Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the and the.

## Branching factor

In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree.

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.

## Cardinal Tree

A cardinal tree (or trie) of degree k, by analogy with cardinal numbers and by opposition with ordinal trees, is a rooted tree in which each node has k positions for an edge to a child.

## Charles E. Leiserson

Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof.

## Clifford Stein

Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science.

## Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

## Corecursion

In computer science, corecursion is a type of operation that is dual to recursion.

## Data structure

In computer science, a data structure is a data organization and storage format that enables efficient access and modification.

## Day–Stout–Warren algorithm

The Day–Stout–Warren (DSW) algorithm is a method for efficiently balancing binary search trees &mdash; that is, decreasing their height to O(log n) nodes, where n is the total number of nodes.

## Dialogue tree

A dialogue tree, or conversation tree, is a gameplay mechanic that is used throughout many adventure games (including action-adventure games) and role-playing video games.

## Dictionary of Algorithms and Data Structures

The Dictionary of Algorithms and Data Structures is a dictionary style reference for many of the algorithms, algorithmic techniques, archetypal problems, and data structures found in the field of computer science.

## Digital compositing

Digital compositing is the process of digitally assembling multiple images to make a final image, typically for print, motion pictures or screen display.

## Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.

## Donald Knuth

Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.

Enfilades are a class of tree data structures used in Project Xanadu "Green" designs of the 1970s and 1980s.

## Family tree

A family tree, or pedigree chart, is a chart representing family relationships in a conventional tree structure.

## Functional programming

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

## Generative grammar

Generative grammar is a linguistic theory that regards grammar as a system of rules that generates exactly those combinations of words that form grammatical sentences in a given language.

## Graph (abstract data type)

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics, specifically the field of graph theory.

## Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

## Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

## Heap (data structure)

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node.

## Hierarchical clustering

In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis which seeks to build a hierarchy of clusters.

## Hierarchical temporal memory

Hierarchical temporal memory (HTM) is a technology based on a realistic biologically-constrained model of the pyramidal neuron that reflects today’s most recent neocortical research originally described in the 2004 book On Intelligence by Jeff Hawkins with Sandra Blakeslee.

## Hierarchy

A hierarchy (from the Greek hierarchia, "rule of a high priest", from hierarkhes, "leader of sacred rites") is an arrangement of items (objects, names, values, categories, etc.) in which the items are represented as being "above", "below", or "at the same level as" one another A hierarchy can link entities either directly or indirectly, and either vertically or diagonally.

## Hierarchy (mathematics)

In mathematics, a hierarchy is a set-theoretical object, consisting of a preorder defined on a set.

## Introduction to Algorithms

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

## Left-child right-sibling binary tree

Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial-heir chain.

In computer science, a linked list is a linear collection of data elements, whose order is not given by their physical placement in memory.

## List (abstract data type)

In computer science, a list or sequence is an abstract data type that represents a countable number of ordered values, where the same value may occur more than once.

## Lowest common ancestor

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes and in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and as descendants, where we define each node to be a descendant of itself (so if has a direct connection from, is the lowest common ancestor).

## Memory management

Memory management is a form of resource management applied to computer memory.

## Multiple inheritance

Multiple inheritance is a feature of some object-oriented computer programming languages in which an object or class can inherit characteristics and features from more than one parent object or parent class.

## Mutual recursion

In mathematics and computer science, mutual recursion is a form of recursion where two mathematical or computational objects, such as functions or data types, are defined in terms of each other.

## Node (computer science)

A node is a basic unit used in computer science.

## Ordinal Tree

An ordinal tree, by analogy with an ordinal number, is a rooted tree of arbitrary degree in which the children of each node are ordered, so that one refers to the ith child in the sequence of children of a node.

## Pruning (decision trees)

Pruning is a technique in machine learning that reduces the size of decision trees by removing sections of the tree that provide little power to classify instances.

## Recursion

Recursion occurs when a thing is defined in terms of itself or of its type.

## Recursive data type

In computer programming languages, a recursive data type (also known as a recursively-defined, inductively-defined or inductive data type) is a data type for values that may contain other values of the same type.

## Reference (computer science)

In computer science, a reference is a value that enables a program to indirectly access a particular datum, such as a variable's value or a record, in the computer's memory or in some other storage device.

## Referential transparency

Referential transparency and referential opacity are properties of parts of computer programs.

## Ron Rivest

Ronald Linn Rivest (born May 6, 1947) is a cryptographer and an Institute Professor at MIT.

## S-expression

In computing, s-expressions, sexprs or sexps (for "symbolic expression") are a notation for nested list (tree-structured) data, invented for and popularized by the programming language Lisp, which uses them for source code as well as data.

## Search algorithm

In computer science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain.

## Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order.

## Subset

In mathematics, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.

## Superior (hierarchy)

In a hierarchy or tree structure of any kind, a superior is an individual or position at a higher level in the hierarchy than another (a "subordinate" or "inferior"), and thus closer to the apex.

## The Art of Computer Programming

The Art of Computer Programming (sometimes known by its initials TAOCP) is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis.

## Thomas H. Cormen

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein.

## Threaded binary tree

In computing, a threaded binary tree is a binary tree variant that allows fast traversal: given a pointer to a node in a threaded tree, it is possible to cheaply find its in-order successor (and/or predecessor).

## Tree (data structure)

In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

## Tree (graph theory)

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.

## Tree (set theory)

In set theory, a tree is a partially ordered set (T, \omega + 1.

## Tree structure

A tree structure or tree diagram is a way of representing the hierarchical nature of a structure in a graphical form.

## Tree traversal

In computer science, tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once.

## Trie

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

## Type theory

In mathematics, logic, and computer science, a type theory is any of a class of formal systems, some of which can serve as alternatives to set theory as a foundation for all mathematics.

## Vertex (graph theory)

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).

## Visual effects

Visual Effects (abbreviated VFX) is the process by which imagery is created or manipulated outside the context of a live action shot in film making.

## References

Hey! We are on Facebook now! »