Chapter 11
Search Trees
11.1 Binary Search Trees
1.Definition,A binary search tree is a binary
tree that may be empty.A nonempty binary
search tree satisfies the following properties:
1)Every element has a key and no two
elements have the same key; therefore,all
keys are distinct.
11.1 Binary Search Trees
2)The keys(if any)in the left subtree of the
root are smaller than the key in the root.
3)The keys(if any)in the right subtree of the
root are larger than the key in the root.
4)The left and right subtrees of the root are
also binary search trees.
11.1 Binary Search Trees
? Example:
45
12 53
90
78
100
6124
373
Leftchild data rightchild
Inherit the linked
representation of binary tree
11.1 Binary Search Trees
? An indexed binary search tree is derived
from an ordinary binary search tree by
adding the field LeftSize to each tree node.
? Value in Leftsize field=number of the
elements in the node’s left subtree +1
leftSize leftChild data rightChild
11.1 Binary Search Trees
? Example,4 20
2 15 1 ^ 25
1 ^ 18 ^1 ^ 12 ^ 1 ^ 30 ^
11.1 Binary Search Trees
2.ADT specification of BSTree(ADT 11.1)
AbstractDataType BSTree{
instances
binary trees,each node has an element with
a key field;all keys are distinct;keys in the
left subtree of any node are smaller than the
key in the node; those in the right subtree
are larger
11.1 Binary Search Trees
operations:
Create(),create an empty binary search tree
Search(k,e):return in e the element with key k
return false if the operation fails,
return true if it succeeds
Insert(e),insert element e into the search tree
Delete(k,e):delete the element with key k and
return it in e
Ascend():Output all elements in ascending order
of key
}
11.1 Binary Search Trees
2,ADT specification of IndexedBSTree
(ADT 11.2)
AbstractDataType IndexedBSTree{
instances
same as for BSTree except that each node has a
LeftSize field
operations
Create(),create an empty indexed binary search
tree
11.1 Binary Search Trees
Search(k,e):return in e the element with key k
return false if the operation fails,
return true if it succeeds
IndexSearch(k,e),return in e the kth element
Insert(e),insert element e into the search tree
Delete(k,e),delete the element with key k and
return it in e
IndexDelete(k,e),delete the kth element and return it
in e
Ascend(),Output all elements in ascending order of key
}
11.1 Binary Search Trees
3.class BSTree
Program 11.1 class definition for binary search trees
template<class E,class K>
class BSTree,public BinaryTree<E>
{ public:
bool Search(const K&k,E& e)const;
BSTree<E,K>& Insert(const E& e);
BSTree<E,K>& Delete(const K&k,E&e);
void Ascend(){InOutput();}
};
11.1 Binary Search Trees
BSTree is a drived class of BinaryTree
IndexedBSTree may also be defined as a
derived class of BinaryTree.
1)search a binary search tree(program 11.2)
template <class E,class K>
bool BSTree<E,K>::Search(const K&k,E& e) const
{//search for element that matches k.
pointer p starts at the root and moves through the
tree looking for an element with key k
11.1 Binary Search Trees
BinaryTreeNode<E>*p=root;
while(p)//examine p?data
if(k<p?data) p=p?LeftChild;
else if(k>p?data) p=p?RightChild;
else {//found element
e=p?data;
return true;}
return false;
}
11.1 Binary Search Trees
2)Inserting into a binary search tree
? First verify if the element is exist in the BSTree
if yes,output an error message.
? Search for insert position,and insert the element
30
5 40
802
5 40
2
30
8035
Insert 35
11.1 Binary Search Trees
Program 11.3
template<class E,class K>
BSTree<E,K>& BSTree<E,K>::Insert(const E& e)
{//Insert e if not duplicate.
BinaryTreeNode<E>*p=root,*pp=0;
//find place to insert
while(p){
pp=p;
11.1 Binary Search Trees
if(e<p?data) p=p?LeftChild;
else if(e>p?data) p=p?RightChild;
else throw BadInput();
}
//get a node for e and attach to pp
BinaryTreeNode<E> *r=new BinaryTreeNode<E>(e);
if(root){tree not empty
if(e<pp?data)pp?LeftChild=r;
else pp?RightChild=r;}
11.1 Binary Search Trees
else //insertion into empty tree
root=r;
return *this;
}
? We can construct a binary seach tree by add
a sequence of keys into a empty binary
search tree
11.1 Binary Search Trees
3)Deletion
It is necessary to adjust the binary search tree
after deleting an element,so that the tree
remained is still a binary tree.There is three
cases for deleting node p,
? P is a leaf
? P has exactly one nonempty subtree
? P has exactly two nonempty subtrees
11.1 Binary Search Trees
? Example:
15
12 24
10
8 11
18
16
17
20
29
23
21
32
30 35
33
11.1 Binary Search Trees
? In case 3,we can replace the element to be
deleted with either the largest element in the
left subtree or the smallest element in the
right subtree,Next step is to delete the
largest element in the left subtree or
smallest element in the right subtree,
11.1 Binary Search Trees
? deleting from a binary search tree (program
11.4)
template<class E,class K>
BSTree<E,K>& BSTree<E,K>::Delete(const
K& k,E&e)
{//delete element with key k and put it in e.
//set p to point to node with key k
BinaryTreeNode<E>*p=root,*pp=0;
11.1 Binary Search Trees
while(p&&p?data!=k){
pp=p;
if(k<p?data)p=p?LeftChild;
else p=p?RightChild;
}
if(!p)throw BadInput();
e=p?data;
11.1 Binary Search Trees
//handling case when p has two children
if(p?LeftChild&&p?RightChild){ //two children
//convert to zero or one child case
//find largest element in left subtree of p
BinaryTreeNode<E> *s=p?LeftChild,*ps=p;
while(s?RightChild){
ps=s;
s=s?RightChild;}
11.1 Binary Search Trees
//move largest from s to p
p?data=s?data;
p=s;
pp=ps;}
//p has at most one child
//save child pointer in c
BinaryTreeNode<E>*c;
if(p?LeftChild)c=p?LeftChild;
else c=p?RightChild;
11.1 Binary Search Trees
//delete p
if(p==root)root=c;
else {//is p left or right child of pp?
if(p==pp?LeftChild)
pp?LeftChild=c;
else pp?RightChild=c;}
delete p;
return *this;
}
11.1 Binary Search Trees
4.Height of a binary search tree
? The height of a binary search tree has influence
directly on the time complexity of operations like
searching,insertion and deletion.
? Worst case,add an ordered elements[1,2,3…n]
into an empty binary search tree.
1
2
3
n
O(n)
11.1 Binary Search Trees
? Best case and average height:
O(log2n)
Example:[53,25,76,20,48,14,60,84]
53
25
20
76
6048 84
14
11.2 AVL Tree
The concept of AVL tree was introduced by
Russian scientists G.M.Adel’son-Vel’sky
and E.M.Landis in 1962.
1.purpose,the AVL tree was introduced to
increase the efficiency of searching a binary
search tree,and to decrease the average
search length.
11.2 AVL Tree
28
38
48
42 58
68
11.2 AVL Tree
2 Definition of an AVL tree:
(1) is a binary search tree
(2) |hL-hR|<=1 where hL and hR are the
heights of TL(left subtree) and TR(right
subtree),respectively.
11.2 AVL Tree
? Height of an AVL tree:
the longest path from the root to each leaf
node
? Balance factor bf(x) of a node x,
height of right subtree of x –height of left
subtree of x
Left data Right balance Each node:
11.2 AVL Tree
? The height of an AVL tree with n elements
is O(log n),so an n-element AVL search
tree can be searched in O(log n) time.
11.2 AVL Tree
3.inserting into an AVL search tree
11.2 AVL Tree
4.Deletion from an AVL search tree
11.2 AVL Tree
? Performance analysis
11.3 B-TREES
1.Indexed sequential access method,ISAM
provide good sequential and random access
for external memory.
? ISAM,the available disk space is divided
into blocks,a block being the smallest unit
of disk space that will be input or output,A
block is one track long and elements are in
ascending order.
11.3 B-TREES
1),For sequential access,the blocks are input in
order,and the elements
in each block are retrieved in ascending order.
If each block contains m elements,the number
of disk accesses per element retrieved is 1/m
11.3 B-TREES
? Random Access,
Max-Key link
Index contais
the largest key
in each block
Stored in internal
memory
Stored in external
memory
block
11.3 B-TREES
? When perform a random access of an
element with key k,first search the index
for the block that may contain the element,
then,retrieved this block and search
internally for the desired element.
? This method is not suitable for inserts and
deletes,unless much space is leaved in each
block
11.3 B-TREES
2.m-way Search Trees
? Definition,An m-way search tree may be empty,
If it is not empty,it is a tree that satisfies the
following properties:
1) In the corresponding extended search
tree(obtained by replacing zero pointer with
external nodes),each internal node has up to m
children and between 1 and m-1 elements.
11.3 B-TREES
2) Every node with p elements has exactly
p+1children.
3) Consider any node with p elements:
k1<k2<……<k p,c0,c1,……,c p be the
p+1 children of the node
C0 k1 C1 k2 …….,k p Cp
11.3 B-TREES
? C0,The elements in the subtree with root c0
have keys smaller than k1
? Cp,Elements in the subtree with root cp
have keys larger than kp
? Ci,Elements in the subtree with root ci have
keys larger than ki but smaller than ki+1,
1<=i<=p.
11.3 B-TREES
10 80
5 20 30 40 50 60 70 82 84 86 88
2 3 4 32 36
90 92 94 96 98
A seven search tree
Example:
11.3 B-TREES
1)search for 31
11.3 B-TREES
2)insert 31 10 80
5 20 30 40 50 60 70 82 84 86 88
2 3 4 31 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
10 80
5 20 30 40 50 60 70 82 84 86 88
2 3 4 31 32 36 65
90 92 94 96 98
A seven search tree
2)insert 65
11.3 B-TREES
? Delete 20,84
10 80
5 30 40 50 60 70 82 86 88
2 3 4 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
? Delete 5,move up 4
10 80
4 20 30 40 50 60 70 82 84 86 88
2 3 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
? Delete 10,replace it with the largest element in
c0(5) 5 80
4 20 30 40 50 60 70 82 84 86 88
2 3 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
? Delete 10,replace it with the smallest element in
c1(20) 20 80
5 30 40 50 60 70 82 84 86 88
2 3 4 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
4)Height of an m-way search tree
An m-way search tree of height h may have as
few as h elements(one node per level),and
as many as mh-1 elements.
11.3 B-TREES
No of nodes
0 m0=1
1 m1=m
h-1 mh-1
Sum of nodes ? mi=(mh-1)/(m-1)i=0
h-1
11.3 B-TREES
? The number of elements in a m-way search
tree of height h is between h and mh-1
? The height of a m-way search tree with n
elements is between logm(n+1) and n
? Example,a 200-way search tree of height 5
can have 2005-1=25*1005-1=32*1010-1
elements.
11.3 B-TREES
3.B-Trees of order m
? Definition, A B-tree of order m is an m-
way search tree,If the B-tree is not empty,
the corresponding extended tree satisfies the
following properties:
1)the root has at least two children
2)all internal nodes other than the root have
at least ?m/2? children
11.3 B-TREES
3)all external nodes are at the same level
10 80
2 4 6 20 30 40 50 60 70 82 84 86 88
1
2
3
Picture 11-25 a B-tree of order 7
11.3 B-TREES
? In a B-tree of order 2,each internal node
has at least 2 children,and all external
nodes must be on the same level,so a B-tree
of order 2 is full binary trees
? In a B-tree of order 3(sometimes also called
2-3 tree),each internal node has 2 or 3
children
11.3 B-TREES
? example 30
20 40
10 15 25 35 45 50
h-1 levels
Level h
A B-tree of order 3
11.3 B-TREES
? Properties:
1)all external nodes are on the same level
2)number of external nodes=number of
keywords +1
proof,b1=k0+1,b2=k1+b1,b3=k2+b2,……
the number of external nodes
=kh-1+kh-2 +……+k 1+k0+1=n+1.
11.3 B-TREES
1)Searching a B-Tree
? A B-tree is searched using the same algorithm as
used for an m-way search tree.
? Algorithm analysis,the number of disk access is
at most h(h is the height of the B-Tree).
proof,T is a B-Tree of order m with height h,
number of elements in T is n,each time we read
a node into memory,The n+1 external nodes are
on level h.
11.3 B-TREES
? Number of nodes on the each level of the B-
Tree is,
…………….
level 0 1
Level 1 >=2
Level 2 >=2?m/2?
Level 3 >=2?m/2?2
Level h >= 2?m/2?h-1
11.3 B-TREES
n+1>= 2?m/2?h-1,(n+1)/2>= ?m/2?h-1,
h-1<=log ?m/2? (n+1)/2,
logm(n+1)<=h<=1+log?m/2? (n+1)/2
In the case that each
node has m children
Example,n=2*106,m=199
then h<=1+log100(102)3=4 search one from 200
branches
11.3 B-TREES
2) Inserting into a B-Tree
Property,always happen at one level above
the external nodes
11.3 B-TREES
Case 1:number of children in the node<m-----
---insert into the node as ordered
10 80
2 4 6 20 30 40 50 60 70 82 84 86 88
A B-Tree of order 7
11.3 B-TREES
Insert 3
10 80
2 3 4 6 20 30 40 50 60 70 82 84 86 88
11.3 B-TREES
Case 2.
? Insert into a node with m children (also called a
full node),like insert 25 into the B-Tree in the last
example,the full node is split into two nodes,
? A new pointer will be added to the parent of the
full node,
? Because k?m/2? is inserted into parent node,it may
cause new split,If the root is split,the height of the
tree will increased by 1,
11.3 B-TREES
? Example,30 80
20 50 60 90
10 25 35 40 55 70 82 85 95
11.3 B-TREES
? Insert 44
80
20 60 90
10 25 44 55 70 82 85 9535
40
30
50
11.3 B-TREES
Another example:
a B-tree of order 5,
insert k,m,j,e,s,i,r,x,c,……
a b f g
Algorithm analyses:
If the insert operation causes s node to split,
then the number of disk access is h (to read in the
nodes on the search path) +2s (to write out the two
split parts of each node that is split)+1 (to write
the new node).
11.3 B-TREES
3)deletion from a B-Tree
Two cases:
?The element to be deleted is in a node
whose children are external nodes(i.e.the
element is in a leaf)
? The element is to be deleted from a nonleaf.
11.3 B-TREES
a) the element to be deleted is in a leaf
Case1,delete it directly if it is in a node
which has more than ?m/2? children
Case2,if it is in a node which has ?m/2?
children,after deletion,the number of
children(?m/2?-1) is not suitable for a B-Tree
① borrow an element from the its nearest
sibling if can,and do some adjusting.
11.3 B-TREES
? Example:delete 379
283 353 401
307 313 331 347 367 379 389
283 347 401
307 313 331 353 367 389
11.3 B-TREES
② If nearest left or right sibling both only has
?m/2? children,then merge them
? After deletion,merge the node and its
sibling with the element between them in
the parent into a single node
? Maybe cause new merge in parent nodes
? The height of the tree will deceased by one
if root is merged.
11.3 B-TREES
? Example:a B-Tree of order 7,delete 431
283 353 401
367 379 389 419 431 439
11.3 B-TREES
b)delete a key in a node in the above level
? Delete it
? Replace it with the smallest key in the right
subtree or the largest key in the left subtree
? Because delete a key in the leaf node,do
the adjust mentioned in a)
11.3 B-TREES
? Example,30 80
20 50 60 90
10 25 35 40 55 70 82 85
?Delete 80,then replace it with 82 or 70,delete 82 or
70 at last
11.3 B-TREES
? Exercise,delete 50,40 in the following tree
50
30 60 80
20 40 55 70 95
11.3 B-TREES
4)Node structure
? S is the number of elements in the node
? ei are the elements in ascending order of key
? Ci are children pointers
s,c0,e1,c1,e2,c2……e s,cs
11.3 B-TREES
? Supplements-----B+ tree
Search Trees
11.1 Binary Search Trees
1.Definition,A binary search tree is a binary
tree that may be empty.A nonempty binary
search tree satisfies the following properties:
1)Every element has a key and no two
elements have the same key; therefore,all
keys are distinct.
11.1 Binary Search Trees
2)The keys(if any)in the left subtree of the
root are smaller than the key in the root.
3)The keys(if any)in the right subtree of the
root are larger than the key in the root.
4)The left and right subtrees of the root are
also binary search trees.
11.1 Binary Search Trees
? Example:
45
12 53
90
78
100
6124
373
Leftchild data rightchild
Inherit the linked
representation of binary tree
11.1 Binary Search Trees
? An indexed binary search tree is derived
from an ordinary binary search tree by
adding the field LeftSize to each tree node.
? Value in Leftsize field=number of the
elements in the node’s left subtree +1
leftSize leftChild data rightChild
11.1 Binary Search Trees
? Example,4 20
2 15 1 ^ 25
1 ^ 18 ^1 ^ 12 ^ 1 ^ 30 ^
11.1 Binary Search Trees
2.ADT specification of BSTree(ADT 11.1)
AbstractDataType BSTree{
instances
binary trees,each node has an element with
a key field;all keys are distinct;keys in the
left subtree of any node are smaller than the
key in the node; those in the right subtree
are larger
11.1 Binary Search Trees
operations:
Create(),create an empty binary search tree
Search(k,e):return in e the element with key k
return false if the operation fails,
return true if it succeeds
Insert(e),insert element e into the search tree
Delete(k,e):delete the element with key k and
return it in e
Ascend():Output all elements in ascending order
of key
}
11.1 Binary Search Trees
2,ADT specification of IndexedBSTree
(ADT 11.2)
AbstractDataType IndexedBSTree{
instances
same as for BSTree except that each node has a
LeftSize field
operations
Create(),create an empty indexed binary search
tree
11.1 Binary Search Trees
Search(k,e):return in e the element with key k
return false if the operation fails,
return true if it succeeds
IndexSearch(k,e),return in e the kth element
Insert(e),insert element e into the search tree
Delete(k,e),delete the element with key k and
return it in e
IndexDelete(k,e),delete the kth element and return it
in e
Ascend(),Output all elements in ascending order of key
}
11.1 Binary Search Trees
3.class BSTree
Program 11.1 class definition for binary search trees
template<class E,class K>
class BSTree,public BinaryTree<E>
{ public:
bool Search(const K&k,E& e)const;
BSTree<E,K>& Insert(const E& e);
BSTree<E,K>& Delete(const K&k,E&e);
void Ascend(){InOutput();}
};
11.1 Binary Search Trees
BSTree is a drived class of BinaryTree
IndexedBSTree may also be defined as a
derived class of BinaryTree.
1)search a binary search tree(program 11.2)
template <class E,class K>
bool BSTree<E,K>::Search(const K&k,E& e) const
{//search for element that matches k.
pointer p starts at the root and moves through the
tree looking for an element with key k
11.1 Binary Search Trees
BinaryTreeNode<E>*p=root;
while(p)//examine p?data
if(k<p?data) p=p?LeftChild;
else if(k>p?data) p=p?RightChild;
else {//found element
e=p?data;
return true;}
return false;
}
11.1 Binary Search Trees
2)Inserting into a binary search tree
? First verify if the element is exist in the BSTree
if yes,output an error message.
? Search for insert position,and insert the element
30
5 40
802
5 40
2
30
8035
Insert 35
11.1 Binary Search Trees
Program 11.3
template<class E,class K>
BSTree<E,K>& BSTree<E,K>::Insert(const E& e)
{//Insert e if not duplicate.
BinaryTreeNode<E>*p=root,*pp=0;
//find place to insert
while(p){
pp=p;
11.1 Binary Search Trees
if(e<p?data) p=p?LeftChild;
else if(e>p?data) p=p?RightChild;
else throw BadInput();
}
//get a node for e and attach to pp
BinaryTreeNode<E> *r=new BinaryTreeNode<E>(e);
if(root){tree not empty
if(e<pp?data)pp?LeftChild=r;
else pp?RightChild=r;}
11.1 Binary Search Trees
else //insertion into empty tree
root=r;
return *this;
}
? We can construct a binary seach tree by add
a sequence of keys into a empty binary
search tree
11.1 Binary Search Trees
3)Deletion
It is necessary to adjust the binary search tree
after deleting an element,so that the tree
remained is still a binary tree.There is three
cases for deleting node p,
? P is a leaf
? P has exactly one nonempty subtree
? P has exactly two nonempty subtrees
11.1 Binary Search Trees
? Example:
15
12 24
10
8 11
18
16
17
20
29
23
21
32
30 35
33
11.1 Binary Search Trees
? In case 3,we can replace the element to be
deleted with either the largest element in the
left subtree or the smallest element in the
right subtree,Next step is to delete the
largest element in the left subtree or
smallest element in the right subtree,
11.1 Binary Search Trees
? deleting from a binary search tree (program
11.4)
template<class E,class K>
BSTree<E,K>& BSTree<E,K>::Delete(const
K& k,E&e)
{//delete element with key k and put it in e.
//set p to point to node with key k
BinaryTreeNode<E>*p=root,*pp=0;
11.1 Binary Search Trees
while(p&&p?data!=k){
pp=p;
if(k<p?data)p=p?LeftChild;
else p=p?RightChild;
}
if(!p)throw BadInput();
e=p?data;
11.1 Binary Search Trees
//handling case when p has two children
if(p?LeftChild&&p?RightChild){ //two children
//convert to zero or one child case
//find largest element in left subtree of p
BinaryTreeNode<E> *s=p?LeftChild,*ps=p;
while(s?RightChild){
ps=s;
s=s?RightChild;}
11.1 Binary Search Trees
//move largest from s to p
p?data=s?data;
p=s;
pp=ps;}
//p has at most one child
//save child pointer in c
BinaryTreeNode<E>*c;
if(p?LeftChild)c=p?LeftChild;
else c=p?RightChild;
11.1 Binary Search Trees
//delete p
if(p==root)root=c;
else {//is p left or right child of pp?
if(p==pp?LeftChild)
pp?LeftChild=c;
else pp?RightChild=c;}
delete p;
return *this;
}
11.1 Binary Search Trees
4.Height of a binary search tree
? The height of a binary search tree has influence
directly on the time complexity of operations like
searching,insertion and deletion.
? Worst case,add an ordered elements[1,2,3…n]
into an empty binary search tree.
1
2
3
n
O(n)
11.1 Binary Search Trees
? Best case and average height:
O(log2n)
Example:[53,25,76,20,48,14,60,84]
53
25
20
76
6048 84
14
11.2 AVL Tree
The concept of AVL tree was introduced by
Russian scientists G.M.Adel’son-Vel’sky
and E.M.Landis in 1962.
1.purpose,the AVL tree was introduced to
increase the efficiency of searching a binary
search tree,and to decrease the average
search length.
11.2 AVL Tree
28
38
48
42 58
68
11.2 AVL Tree
2 Definition of an AVL tree:
(1) is a binary search tree
(2) |hL-hR|<=1 where hL and hR are the
heights of TL(left subtree) and TR(right
subtree),respectively.
11.2 AVL Tree
? Height of an AVL tree:
the longest path from the root to each leaf
node
? Balance factor bf(x) of a node x,
height of right subtree of x –height of left
subtree of x
Left data Right balance Each node:
11.2 AVL Tree
? The height of an AVL tree with n elements
is O(log n),so an n-element AVL search
tree can be searched in O(log n) time.
11.2 AVL Tree
3.inserting into an AVL search tree
11.2 AVL Tree
4.Deletion from an AVL search tree
11.2 AVL Tree
? Performance analysis
11.3 B-TREES
1.Indexed sequential access method,ISAM
provide good sequential and random access
for external memory.
? ISAM,the available disk space is divided
into blocks,a block being the smallest unit
of disk space that will be input or output,A
block is one track long and elements are in
ascending order.
11.3 B-TREES
1),For sequential access,the blocks are input in
order,and the elements
in each block are retrieved in ascending order.
If each block contains m elements,the number
of disk accesses per element retrieved is 1/m
11.3 B-TREES
? Random Access,
Max-Key link
Index contais
the largest key
in each block
Stored in internal
memory
Stored in external
memory
block
11.3 B-TREES
? When perform a random access of an
element with key k,first search the index
for the block that may contain the element,
then,retrieved this block and search
internally for the desired element.
? This method is not suitable for inserts and
deletes,unless much space is leaved in each
block
11.3 B-TREES
2.m-way Search Trees
? Definition,An m-way search tree may be empty,
If it is not empty,it is a tree that satisfies the
following properties:
1) In the corresponding extended search
tree(obtained by replacing zero pointer with
external nodes),each internal node has up to m
children and between 1 and m-1 elements.
11.3 B-TREES
2) Every node with p elements has exactly
p+1children.
3) Consider any node with p elements:
k1<k2<……<k p,c0,c1,……,c p be the
p+1 children of the node
C0 k1 C1 k2 …….,k p Cp
11.3 B-TREES
? C0,The elements in the subtree with root c0
have keys smaller than k1
? Cp,Elements in the subtree with root cp
have keys larger than kp
? Ci,Elements in the subtree with root ci have
keys larger than ki but smaller than ki+1,
1<=i<=p.
11.3 B-TREES
10 80
5 20 30 40 50 60 70 82 84 86 88
2 3 4 32 36
90 92 94 96 98
A seven search tree
Example:
11.3 B-TREES
1)search for 31
11.3 B-TREES
2)insert 31 10 80
5 20 30 40 50 60 70 82 84 86 88
2 3 4 31 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
10 80
5 20 30 40 50 60 70 82 84 86 88
2 3 4 31 32 36 65
90 92 94 96 98
A seven search tree
2)insert 65
11.3 B-TREES
? Delete 20,84
10 80
5 30 40 50 60 70 82 86 88
2 3 4 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
? Delete 5,move up 4
10 80
4 20 30 40 50 60 70 82 84 86 88
2 3 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
? Delete 10,replace it with the largest element in
c0(5) 5 80
4 20 30 40 50 60 70 82 84 86 88
2 3 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
? Delete 10,replace it with the smallest element in
c1(20) 20 80
5 30 40 50 60 70 82 84 86 88
2 3 4 32 36
90 92 94 96 98
A seven search tree
11.3 B-TREES
4)Height of an m-way search tree
An m-way search tree of height h may have as
few as h elements(one node per level),and
as many as mh-1 elements.
11.3 B-TREES
No of nodes
0 m0=1
1 m1=m
h-1 mh-1
Sum of nodes ? mi=(mh-1)/(m-1)i=0
h-1
11.3 B-TREES
? The number of elements in a m-way search
tree of height h is between h and mh-1
? The height of a m-way search tree with n
elements is between logm(n+1) and n
? Example,a 200-way search tree of height 5
can have 2005-1=25*1005-1=32*1010-1
elements.
11.3 B-TREES
3.B-Trees of order m
? Definition, A B-tree of order m is an m-
way search tree,If the B-tree is not empty,
the corresponding extended tree satisfies the
following properties:
1)the root has at least two children
2)all internal nodes other than the root have
at least ?m/2? children
11.3 B-TREES
3)all external nodes are at the same level
10 80
2 4 6 20 30 40 50 60 70 82 84 86 88
1
2
3
Picture 11-25 a B-tree of order 7
11.3 B-TREES
? In a B-tree of order 2,each internal node
has at least 2 children,and all external
nodes must be on the same level,so a B-tree
of order 2 is full binary trees
? In a B-tree of order 3(sometimes also called
2-3 tree),each internal node has 2 or 3
children
11.3 B-TREES
? example 30
20 40
10 15 25 35 45 50
h-1 levels
Level h
A B-tree of order 3
11.3 B-TREES
? Properties:
1)all external nodes are on the same level
2)number of external nodes=number of
keywords +1
proof,b1=k0+1,b2=k1+b1,b3=k2+b2,……
the number of external nodes
=kh-1+kh-2 +……+k 1+k0+1=n+1.
11.3 B-TREES
1)Searching a B-Tree
? A B-tree is searched using the same algorithm as
used for an m-way search tree.
? Algorithm analysis,the number of disk access is
at most h(h is the height of the B-Tree).
proof,T is a B-Tree of order m with height h,
number of elements in T is n,each time we read
a node into memory,The n+1 external nodes are
on level h.
11.3 B-TREES
? Number of nodes on the each level of the B-
Tree is,
…………….
level 0 1
Level 1 >=2
Level 2 >=2?m/2?
Level 3 >=2?m/2?2
Level h >= 2?m/2?h-1
11.3 B-TREES
n+1>= 2?m/2?h-1,(n+1)/2>= ?m/2?h-1,
h-1<=log ?m/2? (n+1)/2,
logm(n+1)<=h<=1+log?m/2? (n+1)/2
In the case that each
node has m children
Example,n=2*106,m=199
then h<=1+log100(102)3=4 search one from 200
branches
11.3 B-TREES
2) Inserting into a B-Tree
Property,always happen at one level above
the external nodes
11.3 B-TREES
Case 1:number of children in the node<m-----
---insert into the node as ordered
10 80
2 4 6 20 30 40 50 60 70 82 84 86 88
A B-Tree of order 7
11.3 B-TREES
Insert 3
10 80
2 3 4 6 20 30 40 50 60 70 82 84 86 88
11.3 B-TREES
Case 2.
? Insert into a node with m children (also called a
full node),like insert 25 into the B-Tree in the last
example,the full node is split into two nodes,
? A new pointer will be added to the parent of the
full node,
? Because k?m/2? is inserted into parent node,it may
cause new split,If the root is split,the height of the
tree will increased by 1,
11.3 B-TREES
? Example,30 80
20 50 60 90
10 25 35 40 55 70 82 85 95
11.3 B-TREES
? Insert 44
80
20 60 90
10 25 44 55 70 82 85 9535
40
30
50
11.3 B-TREES
Another example:
a B-tree of order 5,
insert k,m,j,e,s,i,r,x,c,……
a b f g
Algorithm analyses:
If the insert operation causes s node to split,
then the number of disk access is h (to read in the
nodes on the search path) +2s (to write out the two
split parts of each node that is split)+1 (to write
the new node).
11.3 B-TREES
3)deletion from a B-Tree
Two cases:
?The element to be deleted is in a node
whose children are external nodes(i.e.the
element is in a leaf)
? The element is to be deleted from a nonleaf.
11.3 B-TREES
a) the element to be deleted is in a leaf
Case1,delete it directly if it is in a node
which has more than ?m/2? children
Case2,if it is in a node which has ?m/2?
children,after deletion,the number of
children(?m/2?-1) is not suitable for a B-Tree
① borrow an element from the its nearest
sibling if can,and do some adjusting.
11.3 B-TREES
? Example:delete 379
283 353 401
307 313 331 347 367 379 389
283 347 401
307 313 331 353 367 389
11.3 B-TREES
② If nearest left or right sibling both only has
?m/2? children,then merge them
? After deletion,merge the node and its
sibling with the element between them in
the parent into a single node
? Maybe cause new merge in parent nodes
? The height of the tree will deceased by one
if root is merged.
11.3 B-TREES
? Example:a B-Tree of order 7,delete 431
283 353 401
367 379 389 419 431 439
11.3 B-TREES
b)delete a key in a node in the above level
? Delete it
? Replace it with the smallest key in the right
subtree or the largest key in the left subtree
? Because delete a key in the leaf node,do
the adjust mentioned in a)
11.3 B-TREES
? Example,30 80
20 50 60 90
10 25 35 40 55 70 82 85
?Delete 80,then replace it with 82 or 70,delete 82 or
70 at last
11.3 B-TREES
? Exercise,delete 50,40 in the following tree
50
30 60 80
20 40 55 70 95
11.3 B-TREES
4)Node structure
? S is the number of elements in the node
? ei are the elements in ascending order of key
? Ci are children pointers
s,c0,e1,c1,e2,c2……e s,cs
11.3 B-TREES
? Supplements-----B+ tree
