Definition

quad tree

A quad tree is a method of placing and locating files (called records or keys) in a database. The algorithm finds data by repeatedly dividing the number of ultimately accessible records in four parts until only one remains.

In a tree, records are stored in locations called leaves. This name derives from the fact that records always exist at end points; there is nothing beyond them. Branch points are called nodes. The order of a tree is the number of branches (called children) per node. In a quad tree, there are always four children per node, so the order is 4. The number of leaves in a quad tree is always a power of 4. The number of access operations required to reach the desired record is called the depth of the tree. The image below shows a quad tree of depth 3.

quad_tree.gif

In a practical tree, there can be thousands, millions, or billions of records. Not all leaves necessarily contain a record, but more than half do. A leaf that does not contain a record is called a null. In the example shown here, the eighth, twelfth, and sixteenth leaves are nulls, indicated by open circles.

The quad tree is uniquely suited as an algorithm to locate pixels in a two-dimensional image. The reason for this is that, in two dimensions (the usual way in which graphics are depicted), square pixels can be divided into four square parts repeatedly. The depth of such a tree depends on the image resolution, the computer memory, and the complexity of the image.

Also see binary tree, B-tree, splay tree, and tree structure.

This was last updated in September 2005
Posted by: Margaret Rouse

Email Alerts

Register now to receive SearchOracle.com-related news, tips and more, delivered to your inbox.
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy

More News and Tutorials

Do you have something to add to this definition? Let us know.

Send your comments to techterms@whatis.com

There are Comments. Add yours.

 
TIP: Want to include a code block in your comment? Use <pre> or <code> tags around the desired text. Ex: <code>insert code</code>

REGISTER or login:

Forgot Password?
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy
Sort by: OldestNewest

Forgot Password?

No problem! Submit your e-mail address below. We'll send you an email containing your password.

Your password has been sent to: