Data Structures Using C++ 2E

Chapter 11
Binary Trees and B-Trees
 Binary Trees

• Definition: a binary tree, T, is either empty or such

that
– T has a special node called the root node
– T has two sets of nodes, LT and RT, called the left
subtree and right subtree of T, respectively
– LT and RT are binary trees
• Can be shown pictorially
– Parent, left child, right child
• Node represented as a circle
– Circle labeled by the node
Data Structures Using C++ 2E 2
 Binary Trees (cont’d.)
• Root node drawn at the top
– Left child of the root node (if any)
• Drawn below and to the left of the root node
– Right child of the root node (if any)
• Drawn below and to the right of the root node
• Directed edge (directed branch): arrow

FIGURE 11-1 Binary tree

Data Structures Using C++ 2E 3
 Binary Trees (cont’d.)

FIGURE 11-2 Binary tree with one, two, or three nodes

FIGURE 11-3 Various binary trees with three nodes

Data Structures Using C++ 2E 4

 Binary Trees (cont’d.)
• Every node in a binary tree
– Has at most two children
• struct defining node of a binary tree
– For each node
• The data stored in info
• A pointer to the left child stored in llink
• A pointer to the right child stored in rlink

Data Structures Using C++ 2E 5

 Binary Trees (cont’d.)

• Pointer to root node is stored outside the binary tree

– In pointer variable called the root
• Of type binaryTreeNode

FIGURE 11-4 Binary tree

Data Structures Using C++ 2E 6
binaryTreeNode<char>* root;
root = new binaryTreeNode<char>;
root->info = ‘A’; FIGURE 11-4 Binary tree

root->llink = new binaryTreeNode<char>;

root->llink->info = ‘B’;
root->rlink = new binaryTreeNode<char>;
root->rlink->info = ‘C’;
root->rlink->llink = NULL;

Data Structures Using C++ 2E 7

binaryTreeNode <char> *c = root;
while(c->llink!=NULL) FIGURE 11-4 Binary tree
{
cout<<c->info;
c=c->llink;
}

Data Structures Using C++ 2E 8

 Binary Trees (cont’d.)

• Level of a node
– Number of branches on the path
• Height of a binary tree
– Number of nodes on the longest path from the root to
a leaf
template <class elemType>
int height(binaryTreeNode<elemType> *p) const
{
if (p == NULL)
return 0;
FIGURE 11-5 Binary tree
else
for an inorder traversal
return 1 + max(height(p->llink), height(p->rlink));
}

Data Structures Using C++ 2E 9

 Binary Tree Traversal

• Must start with the root, and then

– Visit the node first or
– Visit the subtrees first
• Three different traversals
– Inorder
– Preorder
– Postorder

Data Structures Using C++ 2E 10

 Binary Tree Traversal (cont’d.)

• Inorder traversal
– Traverse the left subtree
– Visit the node
– Traverse the right subtree
• Preorder traversal
– Visit the node
– Traverse the left subtree
– Traverse the right subtree

Data Structures Using C++ 2E 11

 Binary Tree Traversal (cont’d.)

• Postorder traversal
– Traverse the left subtree
– Traverse the right subtree
– Visit the node
• Each traversal algorithm: recursive
• Listing of nodes
– Inorder sequence
– Preorder sequence
– Postorder sequence

Data Structures Using C++ 2E 12

 Binary Tree Traversal (cont’d.)

FIGURE 11-5 Binary tree

for an inorder traversal

Data Structures Using C++ 2E 13

 Binary Tree Traversal (cont’d.)

• Functions to implement the preorder and postorder

traversals

Data Structures Using C++ 2E 14

 Implementing Binary Trees (cont’d.)

• class binaryTreeType
– Specifies basic operations to implement a binary tree
– See code on page 609
• Contains statement to overload the assignment
operator, copy constructor, destructor
• Contains several member functions that are private
members of the class
• Binary tree empty if root is NULL
– See isEmpty function on page 611

Data Structures Using C++ 2E 15

 Implementing Binary Trees (cont’d.)

• Default constructor
– Initializes binary tree to an empty state
– See code on page 612
• Other functions for binary trees
– See code on pages 612-613
• Functions: copyTree, destroy, destroyTree
– See code on page 614
• Copy constructor, destructor, and overloaded
assignment operator
– See code on page 615
Data Structures Using C++ 2E 16
 Code Examples
template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
inorder(root);
}

template <class elemType>

int binaryTreeType<elemType>::treeNodeCount() const
{
return nodeCount(root);
}

template <class elemType>

int binaryTreeType<elemType>::treeLeavesCount() const
{
return leavesCount(root);
}
Data Structures Using C++ 2E 17
 treeHeight()
template <class elemType>
int binaryTreeType<elemType>::
height(binaryTreeNode<elemType> *p) const
{
if (p == NULL)
return 0;
else
return 1 + max(height(p->llink), height(p->rlink));
}
template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
return height(root);
}
Data Structures Using C++ 2E 18
 destroyTree()
template <class elemType>
void binaryTreeType<elemType>::
destroy(binaryTreeNode<elemType>* &p)
{
if (p != NULL)
{
destroy(p->llink);
destroy(p->rlink);
delete p;
p = NULL;
} template <class elemType>
} void binaryTreeType<elemType>::destroyTree()
{
destroy(root);
}

Data Structures Using C++ 2E 19

 Binary Search Trees

• Data in each node

– Larger than the data in its left child
– Smaller than the data in its right child

FIGURE 11-6 Arbitrary binary tree FIGURE 11-7 Binary search tree

Data Structures Using C++ 2E 20

 Binary Search Trees (cont’d.)

• A binary search tree, T, is either empty or the

following is true:
– T has a special node called the root node
– T has two sets of nodes, LT and RT , called the left
subtree and right subtree of T, respectively
– The key in the root node is larger than every key in
the left subtree and smaller than every key in the right
subtree
– LT and RT are binary search trees

Data Structures Using C++ 2E 21

 Binary Search Trees (cont’d.)

• Operations performed on a binary search tree

– Search the binary search tree for a particular item
– Insert an item in the binary search tree
– Delete an item from the binary search tree
– Find the height of the binary search tree
– Find the number of nodes in the binary search tree
– Find the number of leaves in the binary search tree
– Traverse the binary search tree
– Copy the binary search tree

Data Structures Using C++ 2E 22

 Binary Search Trees (cont’d.)

• Every binary search tree is a binary tree

• Height of a binary search tree
– Determined the same way as the height of a binary
tree
• Operations to find number of nodes, number of
leaves, to do inorder, preorder, postorder traversals
of a binary search tree
– Same as those for a binary tree
• Can inherit functions

Data Structures Using C++ 2E 23

 Binary Search Trees (cont’d.)

• class bSearchTreeType
– Illustrates basic operations to implement a binary
search tree
– See code on page 618
• Function search
• Function insert
• Function delete

Data Structures Using C++ 2E 24

template <class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
binaryTreeNode<elemType> *current;
bool found = false;

if (root == NULL)
cerr << "Cannot search the empty tree." << endl;
else
{
current = root;

while (current != NULL && !found)

{
if (current->info == searchItem)
found = true;
else if (current->info > searchItem)
current = current->llink;
else
current = current->rlink;
}//end while
}//end else

return found;
}//end search

Data Structures Using C++ 2E 25

template <class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
binaryTreeNode<elemType> *current; //pointer to traverse the tree
binaryTreeNode<elemType> *trailCurrent; //pointer behind current
binaryTreeNode<elemType> *newNode; //pointer to create the node

newNode = new binaryTreeNode<elemType>;

assert(newNode != NULL);
newNode->info = insertItem;
newNode->llink = NULL;
newNode->rlink = NULL;

if (root == NULL)
root = newNode;
else
{
current = root;

Data Structures Using C++ 2E 26

 while (current != NULL)
{
trailCurrent = current;

if (current->info == insertItem)
{
cerr << "The insert item is already in the list-";
cerr << "duplicates are not allowed."
<< insertItem << endl;
return;
}
else if (current->info > insertItem)
current = current->llink;
else
current = current->rlink;
}//end while

if (trailCurrent->info > insertItem)

trailCurrent->llink = newNode;
else
trailCurrent->rlink = newNode;

}//end else
}//end insert

Data Structures Using C++ 2E 27

 AVL (Height-Balanced) Trees

• AVL tree (height-balanced tree)

– Resulting binary search is nearly balanced
• Perfectly balanced binary tree
– Heights of left and right subtrees of the root: equal
– Left and right subtrees of the root are perfectly
balanced binary trees

FIGURE 11-12 Perfectly balanced binary tree

Data Structures Using C++ 2E 28
 AVL (Height-Balanced) Trees (cont’d.)

• An AVL tree (or height-balanced tree) is a binary

search tree such that
– The heights of the left and right subtrees of the root
differ by at most one
– The left and right subtrees of the root are AVL trees

FIGURE 11-13 AVL and non-AVL trees

Data Structures Using C++ 2E 29
 AVL (Height-Balanced) Trees (cont’d.)

Data Structures Using C++ 2E 30

 AVL (Height-Balanced) Trees (cont’d.)

• AVL binary search tree search algorithm

– Same as for a binary search tree
– Other operations on AVL trees
• Implemented exactly the same way as binary trees
– Item insertion and deletion operations on AVL trees
• Somewhat different from binary search trees operations

Data Structures Using C++ 2E 31

 B-Trees
• Leaves on the same level
– Not too far from the root
• m-way search tree
– Tree in which each node has at most m children
• If the tree is nonempty, it has the following properties:

Data Structures Using C++ 2E 32

 B-Trees (cont’d.)
• B-tree of order m
– m-way search tree
– Either empty or has the following properties:

• Basic operations
– Search the tree, insert an item, delete an item,
traverse the tree

Data Structures Using C++ 2E 33

 B-Trees (cont’d.)

FIGURE 11-24 A 5-way search tree

FIGURE 11-25 A B-tree of order 5

Data Structures Using C++ 2E 34
 B-Trees (cont’d.)
• Constant expressions
– May be passed as parameters to templates
• Definition of a B-tree node
• Class implementing B-tree properties
– See code on pages 664-665
• Implements B-tree basic properties as an ADT

Data Structures Using C++ 2E 35

 Search

• Searches binary search tree for a given item

– If item found in the binary search tree: returns true
– Otherwise: returns false
• Search must start at root node
• More than one item in a node (usually)
– Must search array containing the data
• Two functions required
– Function search
– Function searchNode
• Searches a node sequentially

Data Structures Using C++ 2E 36

 Traversing a B-Tree
• B-tree traversal methods
– Inorder, preorder, postorder

Data Structures Using C++ 2E 37