Computer Science
Tree data structure
A tree data structure is a hierarchical way of organizing data using nodes and edges. It consists of a root node, which has child nodes connected by edges, forming a branching structure. Each node can have multiple children, and the structure is commonly used in computer science for organizing and representing data in a way that allows for efficient searching and retrieval.
Written by Perlego with AI-assistance
Related key terms
1 of 5
10 Key excerpts on "Tree data structure"
eBook - ePubEssential Algorithms
A Practical Approach to Computer Algorithms Using Python and C#
- Rod Stephens(Author)
- 2019(Publication Date)
- Wiley(Publisher)
CHAPTER 10 TreesThis chapter explains trees, which are highly recursive data structures that you can use to store hierarchical data and model decision processes. For example, a tree can store a company organizational chart or the parts that make up a complex machine such as a car.This chapter explains how to build relatively simple trees and provides the background that you need to understand the more complicated trees described in Chapter 11 and Chapter 12 .Tree Terminology
Tree terminology includes a hodgepodge of terms taken from genealogy, horticulture, and computer science. Trees use a lot of terms, but many of them are intuitive because you probably already understand what they mean in another context.A tree consists of nodes connected by branches. Usually, the nodes contain some sort of data, and the branches do not.NOTE
Trees are a special type of network or graph, so sometimes network and graph terms leak into discussions of trees. For example, branches are sometimes called links or edges, although those terms are more appropriate for networks and graphs. Chapter 13 and Chapter 14 have more to say about networks.The branches in a tree are usually directed so that they define a parent-child relationship between the nodes that they connect. Normally, branches are drawn as arrows pointing from the parent node to the child node. Two nodes that have the same parent are sometimes called siblings.Each node in the tree has exactly one parent node, except for a single, unique root node, which has no parent.The children, the children's children, and so on, for a node are that node's descendants. A node's parent, its parent's parent, and so on, up to the root are that node's ancestors.All of these relationship-oriented terms make sense if you think of the tree as a family tree. You can even define terms such as cousin, nephew, and grandparent without confusing anyone, although those terms are uncommon.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
________________________ WORLD TECHNOLOGIES ________________________ Chapter 5 Tree (Data Structure) and Closure Tree (data structure) A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. A Tree structure is a way of representing the hierarchical nature of a structure in a gra-phical form. In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes. Mathematically, it is a tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at most one parent node. Furthermore, the children of each node have a specific order. Terminology A node is a structure which may contain a value, a condition, or represent a separate data structure (which could be a tree of its own). Each node in a tree has zero or more child nodes , which are below it in the tree (by convention, trees are drawn growing down- ________________________ WORLD TECHNOLOGIES ________________________ wards). A node that has a child is called the child's parent node (or ancestor node , or superior). A node has at most one parent. Nodes that do not have any children are called leaf nodes . They are also referred to as terminal nodes. A free tree is a tree that is not rooted. The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path ). This is commonly needed in the manipulation of the various self balancing trees, AVL Trees in particular. Conventionally, the value -1 corres-ponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node. The topmost node in a tree is called the root node . Being the topmost node, the root node will not have parents.
581 C H A P T E R 17 TREE STRUCTURES C H A P T E R G O A L S To study trees and binary trees To understand how binary search trees can implement sets To learn how red-black trees provide performance guarantees for set operations To choose appropriate methods for tree traversal To become familiar with the heap data structure To use heaps for implementing priority queues and for sorting C H A P T E R C O N T E N T S © DNY59/iStockphoto. 17.1 BASIC TREE CONCEPTS 582 17.2 BINARY TREES 586 WE1 Building a Huffman Tree 590 17.3 BINARY SEARCH TREES 590 17.4 TREE TRAVERSAL 599 17.5 RED-BLACK TREES 605 WE2 Implementing a Red-Black Tree 611 17.6 HEAPS 612 17.7 THE HEAPSORT ALGORITHM 622 582 © DNY59/iStockphoto. In this chapter, we study data structures that organize elements hierarchically, creating arrangements that resemble trees. These data structures offer better performance for adding, removing, and finding elements than the linear structures you have seen so far. You will learn about commonly used tree-shaped structures and study their implementation and performance. 17.1 Basic Tree Concepts In computer science, a tree is a hierar- chical data structure composed of nodes. Each node has a sequence of child nodes, and one of the nodes is the root node. Like a linked list, a tree is composed of nodes, but with a key difference. In a linked list, a node can have only one child node, so the data structure is a linear chain of nodes. In a tree, a node can have more than one child. The resulting shape resembles an actual tree with branches. However, in computer science, it is customary to draw trees upside-down, with the root on top (see Figure 1). Austrian Archives/Imagno/GettyImages, Inc. A family tree shows the descendants of a common ancestor. A tree is composed of nodes, each of which can have child nodes. The root is the node with no parent. A leaf is a node with no children.
No longer available |Learn moreData Structures and Program Design Using C
A Self-Teaching Introduction
- D. Malhotra, N. Malhotra(Authors)
- 2018(Publication Date)
- Mercury Learning and Information(Publisher)
C H A P T E R 8 TREES 8.1 Introduction In earlier chapters, we have already learned about various data struc- tures such as arrays, linked lists, stacks, and queues. All these data struc- tures are linear data structures. Although linear data structures are flexible, it is quite difficult to use them to organize data into a hierarchical represen- tation. Hence, to overcome this problem or limitation, we create a new data structure which is called a tree. A tree is a data structure that is defined as a set of one or more nodes which allows us to associate a parent-child rela- tionship. In trees, one node is designated as the root node or parent node, and all the remaining nodes can be partitioned into non-empty sets, each of which is a subtree of the root. Unlike natural trees, a Tree data structure is upside down, having a root at the top and leaves at the bottom. Also, there is no parent of the root node. A root node can only have child nodes. On the In This Chapter ● ● Introduction ● ● Definitions ● ● Binary tree ● ● Binary search tree ● ● AVL trees ● ● Summary ● ● Exercises 344 • DATA STRUCTURES AND PROGRAM DESIGN USING C contrary, leaf nodes or leaves are those that have no children. When there are no nodes in the tree, then the tree is known as a null tree or empty tree. Trees are widely used in various day to day applications. Also, the recur- sive programming of trees makes the programs optimized and easily under- standable. Trees are also used to represent the structure of mathematical formulas. Figure 8.1 represents a tree. In the following tree, A is the root node of the tree. X, Y, and Z are the child nodes of the root node A. They also form the subtrees of the tree. Also, B, C, Y, D, and E are the leaf nodes of the tree as they have no children. FIGURE 8.1. A tree. Practical Application: 1. The members of a family can be visualized as a tree in which the root node can be visualized as a grandfather. His two children can be visualized as the child nodes.
17 C H A P T E R 779 TREE STRUCTURES To study trees and binary trees To understand how binary search trees can implement sets To learn how red-black trees provide performance guarantees for set operations To choose appropriate methods for tree traversal To become familiar with the heap data structure To use heaps for implementing priority queues and for sorting CHAPTER GOALS CHAPTER CONTENTS 17.1 BASIC TREE CONCEPTS 780 17.2 BINARY TREES 784 WE 1 Building a Huffman Tree 17.3 BINARY SEARCH TREES 789 17.4 TREE TRAVERSAL 798 17.5 RED-BLACK TREES 804 WE 2 Implementing a Red-Black Tree 17.6 HEAPS 811 17.7 THE HEAPSORT ALGORITHM 822 DNY59/iStockphoto. © DNY59/iStockphoto. 780 © DNY59/iStockphoto. In this chapter, we study data structures that organize elements hierarchically, creating arrangements that resemble trees. These data structures offer better performance for adding, removing, and finding elements than the linear structures you have seen so far. You will learn about commonly used tree-shaped structures and study their implementation and performance. 17.1 Basic Tree Concepts In computer science, a tree is a hierar-chical data structure composed of nodes . Each node has a sequence of child nodes , and one of the nodes is the root node . Like a linked list, a tree is composed of nodes, but with a key difference. In a linked list, a node can have only one child node, so the data structure is a linear chain of nodes. In a tree, a node can have more than one child. The resulting shape resembles an actual tree with branches. However, in computer science, it is customary to draw trees upside-down, with the root on top (see Figure 1). A family tree shows the descendants of a common ancestor. A tree is composed of nodes, each of which can have child nodes. The root is the node with no parent. A leaf is a node with no children.
eBook - PDF- Elliot B. Koffman, Paul A. T. Wolfgang(Authors)
- 2012(Publication Date)
- Wiley(Publisher)
C h a p t e r O b j e c t i v e s ◆ To learn how to use a tree to represent a hierarchical organization of information ◆ To learn how to use recursion to process trees ◆ To understand the different ways of traversing a tree ◆ To understand the difference between binary trees, binary search trees, and heaps ◆ To learn how to implement binary trees, binary search trees, and heaps using linked data structures and arrays ◆ To learn how to use a binary search tree to store information so that it can be retrieved in an efficient manner ◆ To learn how to use a Huffman tree to encode characters using fewer bits than ASCII or Unicode, resulting in smaller files and reduced storage requirements 445 Trees C h a p t e r 8 T he data organizations you studied so far are linear, in that each element has only one predecessor or successor. Accessing all the elements in sequence is an O(n) process. In this chapter we begin our discussion of a data organization that is nonlinear or hierarchical: the tree. Instead of having just one successor, a node in a tree can have multiple successors; but it has just one predecessor. A tree in computer science is like a natural tree, which has a single trunk that may split off into two or more main branches. The predecessor of each main branch is the trunk. Each main branch may spawn several secondary branches (successors of the main branches). The predecessor of each secondary branch is a main branch. In computer science, we draw a tree from the top down, so the root of the tree is at the top of the diagram instead of the bottom. Because trees have a hierarchical structure, we use them to represent hierarchi- cal organizations of information, such as a class hierarchy, a disk directory and its subdirectories (see Figure 8.1), or a family tree. You will see that trees are recursive data structures, because they can be defined recursively. For this reason, many of the functions used to process trees are written as recursive functions.
519 C H A P T E R 16 TREE STRUCTURES C H A P T E R G O A L S To study trees and binary trees To understand how binary search trees can implement sets To learn how red-black trees provide performance guarantees for set operations To choose appropriate functions for tree traversal C H A P T E R C O N T E N T S © DNY59/iStockphoto. 16.1 BASIC TREE CONCEPTS 520 16.2 BINARY TREES 524 WE1 Building a Huffman Tree 528 16.3 BINARY SEARCH TREES 528 16.4 TREE TRAVERSAL 538 16.5 RED-BLACK TREES 544 WE2 Implementing a Red-Black Tree 551 520 In this chapter, we study data structures that organize elements hierarchically, creating arrangements that resemble trees. These data structures offer better performance for adding, removing, and finding elements than the linear structures you have seen so far. You will learn about commonly used tree-shaped structures and study their implementation and performance. 16.1 Basic Tree Concepts In computer science, a tree is a hierarchi- cal data structure composed of nodes. Each node has a sequence of child nodes, and one of the nodes is the root node. Like a linked list, a tree is composed of nodes, but with a key difference. In a linked list, a node can have only one child node, so the data structure is a linear chain of nodes. In a tree, a node can have more than one child. The resulting shape resembles an actual tree with branches. However, in computer science, it is cus- tomary to draw trees upside-down, with the root on top (see Figure 1). Austrian Archives/Imagno/GettyImages, Inc. A family tree shows the descendants of a common ancestor. A tree is composed of nodes, each of which can have child nodes. The root is the node with no parent. A leaf is a node with no children. Figure 1 A Family Tree George V Edward VIII George VI Mary Henry George John Elizabeth II Margaret Richard Edward Michael Alexandra Charles Anne Andrew Edward Harry Peter Zara Beatrice Eugenie Louise Severn William Savannah
eBook - PDFFundamentals of Python
Data Structures
- Kenneth Lambert(Author)
- 2018(Publication Date)
- Cengage Learning EMEA(Publisher)
Trees can also be used for implementing other collections, such as sorted sets and sorted dictionaries, that require efficient searching, or that, like prior- ity queues, must impose some priority order on their elements. This chapter examines the properties of trees that make them useful data structures and explores their role in imple- menting several types of collections. An Overview of Trees In the linear data structures you have studied thus far, all items except for the first have a distinct predecessor, and all items except the last have a distinct successor. In a tree, the ideas of predecessor and successor are replaced with those of parent and child. Trees have two main characteristics: • Each item can have multiple children. • All items, except a privileged item called the root, have exactly one parent. The root has no parent. Tree Terminology Tree terminology is a peculiar mix of biological, genealogical, and geometric terms. Table 10-1 provides a quick summary of these terms. Figure 10-1 shows a tree and some of its properties. Term Definition Node An item stored in a tree. Root The topmost node in a tree. It is the only node without a parent. Child A node immediately below and directly connected to a given node. A node can have more than one child, and its children are viewed as organized in left-to-right order. The leftmost child is called the first child, and the rightmost is called the last child. Parent A node immediately above and directly connected to a given node. A node can have only one parent. Siblings The children of a common parent. Leaf A node that has no children. Interior node A node that has at least one child. (continued) Copyright 2019 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
eBook - PDFData Structure Practice
for Collegiate Programming Contests and Education
- Yonghui Wu, Jiande Wang(Authors)
- 2016(Publication Date)
- CRC Press(Publisher)
231 Chapter 8 Programming by Tree Structure A tree can be defined recursively. A tree is a collection of n vertices. The collection can be empty ( n == 0); otherwise, a tree constitutes a distinguished vertex r , called the root, and zero or more nonempty subtrees that the root of each subtree is a child of r , and r is the parent of each subtree root. In Chapter 8, there are two parts of the experiments: 1. Solving hierarchical problems by tree traversal 2. Union–find sets supported by tree structure 8.1 Solving Hierarchical Problems by Tree Traversal A hierarchical structure can be modeled mathematically as a rooted tree: the root of the tree forms the top level, and the children of the root are at the same level, under their common par-ent. Vertices in a rooted tree constitute a partially ordered set, and the relations between vertices constitute relations of partial orders. Hierarchical problems can be represented as tree structures and can be solved by tree traversal. Tree traversal (also known as tree search) refers to the process of visiting (examining or updating) each vertex in a tree exactly once, in a systematic way. There are two ways to traverse a tree: Preorder traversal Visit the root Preorder traversal for subtrees from left to right Postorder traversal Postorder traversal for subtrees from left to right Visit the root
eBook - PDF- Michael T. Goodrich, Roberto Tamassia(Authors)
- 2014(Publication Date)
- Wiley(Publisher)
/user/rt/courses/ cs016/ cs252/ programs/ homeworks/ projects/ papers/ demos/ hw1 hw2 hw3 pr1 pr2 pr3 grades market buylow sellhigh grades Figure 2.16: A tree representing a portion of a file system. A tree T is a set of nodes storing elements in a parent-child relationship with the following properties: • T has a special node r, called the root of T , with no parent node. • Each node v of T different from r has a unique parent node u. Note that according to the above definition, a tree cannot be empty, since it must have at least one node, the root. One could also allow the definition to include empty trees, but we adopt the convention that a tree always has a root so as to keep our presentation simple and to avoid having to always deal with the special case of an empty tree in our algorithms. If node u is the parent of node v, then we say that v is a child of u. Two nodes that are children of the same parent are siblings. A node is external if it has no children, and it is internal if it has one or more children. External nodes are also known as leaves. The subtree of T rooted at a node v is the tree consisting of all the descendants of v in T (including v itself). An ancestor of a node is either the node itself, its parent, or an ancestor of its parent. Conversely, we say that a node v is a descendant of a node u if u is an ancestor of v. 2.3. Trees 69 Example 2.2: In most operating systems, files are organized hierarchically into nested directories (also called folders), which are presented to the user in the form of a tree. (See Figure 2.16.) More specifically, the internal nodes of the tree are associated with directories and the external nodes are associated with regular files. In Unix-like operating systems, the root of the tree is appropriately called the “root directory,” and is represented by the symbol “/.” It is the ancestor of all directories and files in such a file system.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
