Beginning Programming All-In-One Desk Reference for Dummies (ISBN by 0470108541)

Author:0470108541)
Language: eng
Format: mobi
Tags: &NEW
Published: 2011-07-01T01:27:23+00:00

• • •

Z

alpha-

betically by

last name.

Bally, David

Burkins, John

To save the name David Bally, the computer stores the name under the B

node. To save the name John Burkins, the computer also stores this name under the B node. To determine whether to store this new name before or after any existing data, the computer examines the data and sorts it alphabetically. In this way, the tree data structure not only stores data, but sorts and organizes it as well.

If you had a long list of names stored in an array or a collection, finding a name would require searching through the entire array or collection. However, if that same list of names is stored in a tree, a name would be much simpler to find because you’d only need to look at the first letter of a person’s last name to find where it might be stored.

So if you want to find the name John Bally, start at the B node and ignore any data stored under the other nodes. This makes searching and retrieving data much faster than other types of data structures, which is why trees are so commonly used in databases.

Binary trees

A variation of an ordered tree is a binary tree. Unlike an ordinary tree, every node in a binary tree has at the most two nodes connected underneath. To sort data, the left node contains values less than its parent node whereas the right node contains values greater than its parent node, as shown in Figure 5-8.

By limiting each node to a maximum of two connected nodes, binary trees make searching and sorting data fast and efficient.

10

Figure 5-8:

Binary trees

8

12

store and

sort data

by value.

4

9

11

19

26_108543-bk03ch05.qxp 4/30/08 8:27 PM Page 383

Creating Trees

383

For example, an ordinary tree allows each node to have multiple nodes underneath. As a result, the more data an ordinary tree stores, the more nodes that can appear directly underneath a single node, as shown in Figure 5-9.

10

10

8

12

12

9

4

Figure 5-9:

An ordinary

tree is more

4

9

11

19

8

19

11

difficult to

search than

To find the number 11 in a sorted

To find the number 11 in an unordered,

a binary

binary tree, you have to search three

non-binary tree means having to search

tree.

nodes.

every node.

To find the number 11 in an ordered binary tree is simple. Start with the root (top) node and compare the number 11 to the root node value (10). Because the number you want to find is greater than the root node, you’d branch to the right. At this next node (12), the computer repeats the process and Book III

determines that 11 is less than 12, so it branches to the left node, which is Chapter 5

where it finds the number 11.

Graphs and T

Searching through a sorted binary tree is simple, especially when compared to an unordered tree. Because an unordered tree can scatter data anywhere, searching an unordered tree means methodically searching each node, one by one, until you find the data you want. In a large unordered tree, this rees

search time can be slow and inefficient.

Ordered binary trees are one of the most common tree data structures used in many types of programs, such as databases.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.