Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Tree (data structure)

Index 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), ..., Referential transparency, Ron Rivest, S-expression, Search algorithm, Sorting algorithm, Subset, Superior (hierarchy), The Art of Computer Programming, Thomas H. Cormen, Threaded binary tree, Tree (data structure), Tree (graph theory), Tree (set theory), Tree structure, Tree traversal, Trie, Type theory, Vertex (graph theory), Visual effects. 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.

New!!: Tree (data structure) and Abstract data type · See more »

Adjacency list

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

New!!: Tree (data structure) and Adjacency list · See more »

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.

New!!: Tree (data structure) and Ambient isotopy · See more »

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.

New!!: Tree (data structure) and Arborescence (graph theory) · See more »

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.

New!!: Tree (data structure) and Array data structure · See more »

AVL tree

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

New!!: Tree (data structure) and AVL tree · See more »

Binary heap

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

New!!: Tree (data structure) and Binary heap · See more »

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.

New!!: Tree (data structure) and Binary search tree · See more »

Binary space partitioning

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

New!!: Tree (data structure) and Binary space partitioning · See more »

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.

New!!: Tree (data structure) and Binary tree · See more »

Branching factor

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

New!!: Tree (data structure) and Branching factor · See more »

Breadth-first search

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

New!!: Tree (data structure) and Breadth-first search · See more »

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.

New!!: Tree (data structure) and Cardinal Tree · See more »

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.

New!!: Tree (data structure) and Charles E. Leiserson · See more »

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.

New!!: Tree (data structure) and Clifford Stein · See more »

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.

New!!: Tree (data structure) and Computer science · See more »


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

New!!: Tree (data structure) and Corecursion · See more »

Data structure

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

New!!: Tree (data structure) and Data structure · See more »

Day–Stout–Warren algorithm

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

New!!: Tree (data structure) and Day–Stout–Warren algorithm · See more »

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.

New!!: Tree (data structure) and Dialogue tree · See more »

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.

New!!: Tree (data structure) and Dictionary of Algorithms and Data Structures · See more »

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.

New!!: Tree (data structure) and Digital compositing · See more »

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.

New!!: Tree (data structure) and Directed graph · See more »

Donald Knuth

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

New!!: Tree (data structure) and Donald Knuth · See more »

Enfilade (Xanadu)

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

New!!: Tree (data structure) and Enfilade (Xanadu) · See more »

Family tree

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

New!!: Tree (data structure) and Family tree · See more »

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.

New!!: Tree (data structure) and Functional programming · See more »

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.

New!!: Tree (data structure) and Generative grammar · See more »

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.

New!!: Tree (data structure) and Graph (abstract data type) · See more »

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".

New!!: Tree (data structure) and Graph (discrete mathematics) · See more »

Graph theory

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

New!!: Tree (data structure) and Graph theory · See more »

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.

New!!: Tree (data structure) and Heap (data structure) · See more »

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.

New!!: Tree (data structure) and Hierarchical clustering · See more »

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.

New!!: Tree (data structure) and Hierarchical temporal memory · See more »


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.

New!!: Tree (data structure) and Hierarchy · See more »

Hierarchy (mathematics)

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

New!!: Tree (data structure) and Hierarchy (mathematics) · See more »

Introduction to Algorithms

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

New!!: Tree (data structure) and Introduction to Algorithms · See more »

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.

New!!: Tree (data structure) and Left-child right-sibling binary tree · See more »

Linked list

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

New!!: Tree (data structure) and Linked list · See more »

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.

New!!: Tree (data structure) and List (abstract data type) · See more »

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).

New!!: Tree (data structure) and Lowest common ancestor · See more »

Memory management

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

New!!: Tree (data structure) and Memory management · See more »

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.

New!!: Tree (data structure) and Multiple inheritance · See more »

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.

New!!: Tree (data structure) and Mutual recursion · See more »

Node (computer science)

A node is a basic unit used in computer science.

New!!: Tree (data structure) and Node (computer science) · See more »

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.

New!!: Tree (data structure) and Ordinal Tree · See more »

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.

New!!: Tree (data structure) and Pruning (decision trees) · See more »


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

New!!: Tree (data structure) and Recursion · See more »

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.

New!!: Tree (data structure) and Recursive data type · See more »

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.

New!!: Tree (data structure) and Reference (computer science) · See more »

Referential transparency

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

New!!: Tree (data structure) and Referential transparency · See more »

Ron Rivest

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

New!!: Tree (data structure) and Ron Rivest · See more »


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.

New!!: Tree (data structure) and S-expression · See more »

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.

New!!: Tree (data structure) and Search algorithm · See more »

Sorting algorithm

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

New!!: Tree (data structure) and Sorting algorithm · See more »


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.

New!!: Tree (data structure) and Subset · See more »

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.

New!!: Tree (data structure) and Superior (hierarchy) · See more »

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.

New!!: Tree (data structure) and The Art of Computer Programming · See more »

Thomas H. Cormen

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

New!!: Tree (data structure) and Thomas H. Cormen · See more »

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).

New!!: Tree (data structure) and Threaded binary tree · See more »

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.

New!!: Tree (data structure) and Tree (data structure) · See more »

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.

New!!: Tree (data structure) and Tree (graph theory) · See more »

Tree (set theory)

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

New!!: Tree (data structure) and Tree (set theory) · See more »

Tree structure

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

New!!: Tree (data structure) and Tree structure · See more »

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.

New!!: Tree (data structure) and Tree traversal · See more »


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.

New!!: Tree (data structure) and Trie · See more »

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.

New!!: Tree (data structure) and Type theory · See more »

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).

New!!: Tree (data structure) and Vertex (graph theory) · See more »

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.

New!!: Tree (data structure) and Visual effects · See more »

Redirects here:

Ancestor node, Child node, Child nodes, External node, Inner node, Interior node, Internal node, Internal vertices, Leaf node, Leaf nodes, Leaf object, Non-leaf node, Ordered tree data structure, Parent node, Parent node (in a tree), Root Node, Root node, Sibling node, Subtree, Subtrees, Tree (computer science), Tree (computing), Tree data structure, Tree height, Tree leaf, Tree path.


[1] https://en.wikipedia.org/wiki/Tree_(data_structure)

Hey! We are on Facebook now! »