µ±Ç°Î»ÖãºÊ×Ò³ » ·þÎñÆ÷¼¼Êõ

¿ª·¢¼¼ÊõÖ¸ÄÏ» ÎÄÕÂÕýÎÄ

    ÒýÑÔ£º An Extensive Examination of Data

 

 

Data Structures with .NET - Part 3: Binary Trees and BSTs
an extensive examination of data structures

scott mitchell ¡¾Ïà¹ØÎÄÕÂ:ÔÚRedhat LinuxÉÏ°²×° GCC¡¿

part 3: binary trees and bsts ¡¾À©Õ¹ÔĶÁ:2003ϵͳʶ±ðÍâÀ´É豸һÀý£¨Ô­´´£©¡¿

4guysfromrolla.com ¡¾À©Õ¹ÐÅÏ¢:¼¸¸öÖØÒªµÄÄÚºËÎļþ½éÉÜ¡¿

january 2004

summary: this article, the third in a six-part series on data structures in the .net framework, looks at a common data structure that is not included in the .net framework base class library: binary trees. whereas arrays arrange data linearly, binary trees can be envisioned as storing data in two dimensions. a special kind of binary tree, called a binary search tree, or bst, allows for a much more optimized search time than with arrays. (31 printed pages)

scott mitchell continues his study of data structures, focusing on binary trees and bsts, a common data structure that is not include in the .net framework class library.

download the binarytrees.msi sample file.

contents

introduction

arranging data in a tree

understanding binary trees

improving the search time with binary search trees (bsts)

binary search trees in the real-world

introduction

in part 1 of this series, we looked at what data structures are, how their performance can be evaluated, and how these performance considerations play into choosing which data structure to utilize for a particular algorithm. in addition to reviewing the basics of data structures and their analysis, we also looked at the most commonly used data structure—the array—and its relative, the arraylist. in part 2 we looked at the cousins of the arraylist—the stack and the queue, which store their data like an arraylist, but limit the means by which their contained data can be accessed. in part 2 we also looked at the hashtable, which is essentially an array that is indexed by some arbitrary object as opposed to by an ordinal value.

the arraylist, stack, queue, and hashtable all use an underlying array as the means by which their data is stored. this means that, under the covers, these four data structures are bound by the limitations imposed by an array. recall from part 1 that an array is stored linearly in memory, requires explicit resizing when the array´s capacity it reached, and suffers from linear searching time.

in this third installment of the article series, we will examine a new data structure—the binary tree. as we´ll see, binary trees store data in a non-linear fashion. after discussing the properties of binary trees, we´ll look at a more specific type of binary tree—the binary search tree (bst). a bst imposes certain rules on how the items of the tree are arranged. these rules provide bsts with a sub-linear search time, making them more efficient for searching than arrays.

arranging data in a tree

if you´ve ever looked at a genealogy table, or at the chain of command in a corporation, you´ve seen data arranged in a tree. a tree is composed of a collection of nodes, where each node has some associated data and a set of children. a node´s children are those nodes that appear immediately beneath the node itself. a node´s parent is the node immediately above it. a tree´s root is the single node that contains no parent.

figure 1 shows an example of the chain of command in a fictitious company.

figure 1. tree view of a chain of command in a fictitious company

in this example, the tree´s root is bob smith, ceo. this node is the root because it has no parent. the bob smith node has one child, tina jones, president, whose parent is bob smith. the tina jones node has three children:

·???????????????????? jisun lee, cio

·???????????????????? frank mitchell, cfo

·???????????????????? davis johnson, vp of sales

each of these nodes´ parent is the tina jones node. the jisun lee node has two children:

·???????????????????? tony yee

·???????????????????? sam maher

the frank mitchell node has one child:

·???????????????????? darren kulton

the davis johnson node has three children:

·???????????????????? todd brown

·???????????????????? jimmy wong

·???????????????????? sarah yates

all trees exhibit the following properties:

·???????????????????? there is precisely one root.

·???????????????????? all nodes except the root have precisely one parent.

·???????????????????? there are no cycles. that is, starting at any given node, there is not some path that can take you back to the starting node. the first two properties—that there exists one root and that all nodes save the root have one parent—guarantee that no cycles exist.

trees are useful for arranging data in a hierarchy. as we will discuss later on in this article, the time to search for an item can be drastically reduced by intelligently arranging the hierarchy. before we can arrive at that topic, though, we need to first discuss a special kind of tree, the binary tree.

note???throughout this article we will be looking at numerous new terms and definitions. these definitions, along with being introduced throughout the text, are listed in appendix a.

understanding binary trees

a binary tree is a special kind of tree, in which all nodes have at most two children. for a given node in a binary tree, the first child is referred to as the left child, while the second child is referred to as the right child. figure 2 depicts two binary trees.

figure 2. illustration of two binary trees

binary tree (a) has 8 nodes, with node 1 as its root. node 1´s left child is node 2; node 1´s right child is node 3. notice that a node doesn´t need to have both a left child and right child. in binary tree (a), node 4, for example, has only a right child. furthermore, a node can have no children. in binary tree (b), nodes 4, 5, 6, and 7 all have no children.

nodes that have no children are referred to as leaf nodes. nodes that have one or two children are referred to as internal nodes. using these new definitions, the leaf nodes in binary tree (a) are nodes 6 and 8, and the internal nodes are nodes 1, 2, 3, 4, 5, and 7.

unfortunately, the .net framework does not contain a binary tree class, so in order to better understand binary trees, let´s take a moment to create our own binary tree class.

the first step: creating a node class

the first step in designing our binary tree class is to create a node class. the node class abstractly represents a node in the tree. realize that each node in a binary tree contains two things:

1.????????????????? data

...   ÏÂÒ»Ò³

» ±¾ÆÚÈÈÃÅÎÄÕ£º

· ÈÈÃÅÀ¸Ä¿£º

» Ïà¹Ø¾«Ñ¡ÎÄÕÂ

» ÆäËüÏà¹Ø£º