Chapter 10 BINARY TREES
1,General Binary Trees
2,Binary Search Trees
3,Building a Binary Search
Tree4,Height Balance,AVL Trees
5,Splay Trees
6,Pointers and Pitfalls
10.1 Binary Trees
DEFINITION A binary tree is either empty,or it
consists of a node called the root together with two
binary trees called the left subtree and the right
subtree of the root.
1,Definitions
2,Traversal of Binary Trees
At a given node there are three tasks to do in some
order,Visit the node itself (V); traverse its left subtree
(L); traverse its right subtree (R),There are six ways to
arrange these tasks:
VLR LVR LRV VRL RVL RLV
By standard convention,these are reduced to three
by considering only the ways in which the left subtree
is traversed before the right,
preorderinorderpostorder
These three names are chosen according to the
step at which the given node is visited.
◆ With preorder traversal we first visit a node,then
traverse its left subtree,and then traverse its right
subtree.
◆ With inorder traversal we first traverse the left
subtree,then visit the node,and then traverse its
right subtree.
◆ With postorder traversal we first traverse the left
subtree,then traverse the right subtree,and nally
visit the node.
See pg.432-434
Expression tree
x = (-b+(b↑2-4× a× c)↑0.5) / (2× a)
3,Linked implementation of Binary Trees
Node structure of Binary Trees
example
Linked Binary Trees Specifications
template <class Entry>
class Binary_tree
{ public:
// Add methods here.
protected:
// Add auxiliary function prototypes here.
Binary_node<Entry> *root;
};
Binary trees class 二叉树根 结点 指针
template <class Entry>
struct Binary_node
{ Entry data;
Binary_node<Entry> *left;
Binary_node<Entry> *right;
Binary_node( );
Binary_node(const Entry & x);
};
Binary node class 数据域指向左孩子的指针指向右孩子的指针
template <class Entry>
void Binary_tree<Entry>::inorder(void (*visit)(Entry &))
{ recursive_inorder(root,visit); }
template <class Entry> void Binary_tree<Entry>::
recursive_inorder(Binary_node<Entry> *sub_root,
void (*visit)(Entry &))
/* Pre,sub_root is either NULL or points to a subtree of the inary_tree.
Post,The subtree has been traversed in inorder sequence,*/
{ if (sub_root != NULL)
{ recursive_inorder(sub_root->left,visit);
(*visit)(sub_root->data);
recursive_inorder(sub_root->right,visit);
}
}
Inorder traversal,method函数参数
(访问数据 )
调用递归中序
遍历函数递归中序遍历函数
多一个参数
◆ 树形结构是一类重要的非线性结构。树能够很好地描述结
构的分支关系和层次特性，它非常类似于自然界中的树。树
结构在客观世界中是大量存在的，例如家谱以及行政组织机
构都可用树形象地表示。树在计算机领域中也有着广泛的应
用，如在编译程序中，用树来表示源程序语法结构；在数据
库系统中，可以用树来组织信息。本章重点讨论二叉树的存
储表示及其各种运算，要求大家要学会编写实现二叉树的各
种运算的算法。
◆ 二叉树是递归定义 的，因此 递归是它的固有特性，本小节
的练习中就要求大家完成许多 操作二叉树的算法，且是 递归
算法 。
◆ 下面 我们给出一个以先序方式创建任意二叉树的算法，请
认真学习。
template<class Entry>
void Binary_tree<Entry>::CreatBinary_tree()
{ CreatBinary_tree(root); }
template<class Entry> void Binary_tree<Entry>::
CreatBinary_tree(Binary_node<Entry>* &r)
{ cin>>x;
if ( x==endmark ) r = NULL;
else{ r = new Binary_Node<Entry>(x);
CreatBinary_tree(r->left);
CreatBinary_tree(r->right);
}
}
建立二叉链表
表示的二叉树
递归建立以 r为
根结点指针的二叉链表
表示的二叉树
建立 ? 空 ? 二叉树建立根结点建立根结点
的左子树建立根结点 的右子树
Entry
data member
表示‘空’的
数据
我们再给出一个应用例。
在以二叉链表存储的二叉树中查找值为 x的结点，请编
写一非递归算法：打印值为 x的结点的所有的祖先结点
的值。设值为 x的结点不多于 1个。
template <class T> printAncestors(Binary_tree<T> tree,
T& x)
{ typedef struct
{ Binary_node<T>* ptr; int tag; } StackNode;
StackNode ST[100]; int i,top = -1,find=0;
Binary_node<T>* t = tree.GetRoot();
if(t->data==x) { cout<<x<<" is Root\n"; return; }
while( t && t->data!=x || top!=-1 )
{ while(t && t->data != x)
{ ST[++ top].ptr=t; ST[top].tag = 0; t=t->left; }
在二叉树 tree中搜索
结点 x，找到则打印
所有祖先结点及 x
否则输出 x不存在
要求非递归
因此自行定义
‘栈结点’类型
指针域 (保留从根到
搜索结点路径上
所以结点指针 )
标记域
(tag==0左子树
否则是右子树 )置空栈
栈数组栈结点类型名
取得二叉树 tree
的根结点指针
做为 t的初始值
指针不‘空’而且
其所指结点的
数据域不是 x栈不‘空’搜索左子树
寻找值为 x的结点进栈
二叉树 tree
的根结点是 x
if (t && t->data==x)
{ for(i=0; i<=top; i++) cout<<ST[i].ptr->data<<endl;
cout<<x<<endl; find=1;
break;
}
else
{ while( top!=-1 && ST[top].tag==1) top--;
if (top!=-1) { ST[top].tag=1; t=ST[top].ptr->right; }
} // end_(if-else)block
} // end_while
if (!find) cout<<" search "<<x<<" not exists\n";
}
找到值为 x的结点
输出所有祖先结点
(栈 )
跳出 while循环如果栈顶是右指针
弹出
如果栈不空
栈顶是左指针
转向右子树
重新回到 while
没找到值为 x的结点
在 C++环境下演示创建二叉树及在建立的二叉树上完
成各项操作的 bt_main.cpp。
10.2 Binary Search Trees
Can we find an implementation for ordered lists in
which we can search quickly (as with binary search on
a contiguous list) and in which we can make insertions
and deletions quickly (as with a linked list)?
A binary search tree is a binary trees that is either
empty or in which the data entry of every node has a
key and satisfies the conditions:
1,The key of the root (if it exists) is greater than the
key in any node in the left subtree of the root.
2,The key of the root (if it exists) is less than the
key in any node in the right subtree of the root.
3,The left and right subtrees of the root are again
binary search trees.
binary search tree Definitions pg.445
binary searchtree not binary searchtree
DEFINITION A binary search tree is a binary tree that is
either empty or in which the data entry of every node has a
key and satises the conditions:
1,The key of the left child of a node (if it exists) is less than
the key of its parent node.
2,The key of the right child of a node (if it exists) is greater
than the key of its parent node.
3,The left and right subtrees of the root are again binary
search trees.
errorerror
We always require:
No two entries in a binary search tree may have equal keys.
? We can regard binary search trees as a new ADT.
? We may regard binary search trees as a
specialization of binary trees.
? We may study binary search trees as a new
implementation of the ADT ordered list.
? The binary search tree class will be derived from the
binary tree class; hence all binary tree methods are
inherited.
1,Ordered Lists and Implementations pg.446
The Binary Search Tree Class pg.446
template <class Record>
class Search_tree:public Binary_tree <Record>
{ public:
Error_code insert(const Record &new_data);
Error_code remove(const Record &old_data);
Error_code tree_search(Record &target) const;
protected:
// Add auxiliary function prototypes here.
};
?The inherited methods include the constructors,
the destructor,clear,empty,size,height,and the
traversals preorder,inorder,and postorder.
?A binary search tree also admits specialized methods
called insert,remove,and tree search.
?The class Record has the behavior outlined in
Chapter 7,Each Record is associated with a Key,
The keys can be compared with the usual
comparison operators,By casting records to their
corresponding keys,the comparison operators apply
to records as well as to keys.
2,Tree Search pg.447
Error_code Search_tree<Record>::
tree_search(Record &target) const;
Post,If there is an entry in the tree whose key
matches that
in target,the parameter target is replaced by the
corresponding record from the tree and a code
of
success is returned,
?This method will often be called with a parameter
target that contains only a key value,The method will
fill target with the complete data belonging to any
corresponding Record in the tree.
?To search for the target,we first compare it with the
entry at the root of the tree,If their keys match,then we
are finished,Otherwise,we go to the left subtree or
right subtree as appropriate and repeat the search in
that subtree.
?We program this process by calling an auxiliary
recursive function.
?The process terminates when it either finds the target
or hits an empty subtree.
? The auxiliary search function returns a pointer to the
node that contains the target back to the calling
program,Since it is private in the class,this pointer
manipulation will not compromise tree encapsulation.
Binary_node<Record>* Search_tree<Record>::
search_for_node(Binary_node<Record> *sub_root,
const Record &target) const
Pre,sub root is NULL or points to a subtree of a
Search tree
Post,If the key of target is not in the subtree,a result
of
NULL is returned,
Otherwise a pointer to the subtree node
containing the
Recursive auxiliary function,pg.448
Non-recursive version:
template <class Record> Binary_node<Record>*
Search_tree<Record>::search_for_node(Binary_node<Record>
*sub_root,const Record &target) const
{ while(sub_root!=NULL && sub_root->data!=target)
if(sub_root->data<target) sub_root = sub_root->right;
else sub_root = sub_root->left;
return sub_root;
}
Public method for tree search:
template <class Record> Error_code Search_tree<Record>:,
tree_search(Record &target) const
{ Error_code result = success;
Binary_node<Record> *found;
found = search_for_node(root,target) ;
if(found==NULL) result = not_present;
else target = found->data;
return result;
}
Binary Search Trees with the Same Keys
The same keys
may be built into
binary search trees of
many different shapes
Analysis of Tree Search
? Draw the comparison tree for a binary search (on an
ordered list),Binary search on the list does exactly the
same comparisons as tree search will do if it is applied
to the comparison tree,By Section 7.4,binary search
performs O(㏒ n)comparisons for a list of length n,This
performance is excellent in comparison to other
methods,since ㏒ n grows very slowly as n increases.
?The same keys may be built into binary search trees
of many different shapes.
?If a binary search tree is nearly completely balanced
(“bushy”),then tree search on a tree with n vertices will
also do O (㏒ n) comparisons of keys.
? If the tree degenerates into a long chain,then tree
search becomes the same as sequential search,doing
?(n)comparisons on n vertices,This is the worst case
for tree search.
?The number of vertices between the root and the
target,inclusive,is the number of comparisons that
must be done to find the target,The bushier the tree,
the smaller the number of comparisons that will usually
need to be done.
?It is often not possible to predict (in advance of
building it) what shape of binary search tree will occur.
?In practice,if the keys are built into a binary search
tree in random order,then it is extremely unlikely that a
binary search tree degenerates badly; tree_search
usually performs almost as well as binary search.
3.Insertion into a Binary Search Tree pg.451
Error_code Search tree<Record>::
insert(const Record &new data);
Post,If a Record with a key matching that of new
data already belongs to the Search tree a code of
duplicate_error is returned,Otherwise,the Record
new data is inserted into the tree in such a way that
the properties of a binary search tree are preserved,
and a code of success is returned.
Method for Insertion
template <class Record>Error_code
Search_tree<Record>::insert(const Record &new_data)
{ if(root==NULL)
{ root=new Binary_node<Record>(new_data);
return success;
}
Binary_node<Record> *sub_root=root,*parent;
do{ parent=sub_root;
if(new_data<sub_root->data) sub_root=sub_root->left;
else if(new_data>sub_root->data)
sub_root=sub_root->right;
else return duplicate_error;
}while(sub_root!=NULL);
“空 ? BST
直接插入 (根结点 )
寻找
插入位置
插入数据小于
当前 (子树根 )结点数据
继续在左子树中
搜寻插入位置
在右子树中
搜寻插入位置
直至到达一个 ‘ 空 ’ BST
子树，脱离循环；这时
插入结点应是 parent
的孩子
sub_root=new Binary_node<Record>(new_data);
if(new_data<parent->data) parent->left=sub_root;
else parent->right = sub_root;
return success;
}
根据 插入结点值
确定应是 parent
的左孩子还是右孩子？
The method insert can usually insert a new node
into a random binary search tree with n nodes in
O(㏒ n) steps,It is possible,but extremely unlikely,
that a random tree may degenerate so that
insertions require as many as n steps,If the keys
are inserted in sorted order into an empty tree,
however,this degenerate case will occur.
See pg.453 Theorem 10.1 and Corollary 10.2
?When a binary search tree is traversed in inorder,the
keys will come out in sorted order.
?This is the basis for a sorting method,called treesort,
Take the entries to be sorted,use the method insert to
build them into a binary search tree,and then use
inorder traversal to put them out in order.
Theorem 10.1 Treesort makes exactly the same
comparisons of keys as does quicksort when the
pivot for each sublist is chosen to be the first key
in the sublist.
4,Treesort pg.453
Corollary 10.2 In the average case,on a randomly
ordered list of length n,treesort performs
comparisons of keys,O ( n)n1, 3 9 nlO ( n)n2 nl gn ???
?First advantage of treesort over quicksort,The nodes
need not all be available at the start of the process,but
are built into the tree one by one as they become
available.
?Second advantage,The search tree remains available
for later insertions and removals.
?Drawback,If the keys are already sorted,then treesort
will be a disaster-- the search tree it builds will reduce
to a chain,Treesort should never be used if the keys
are already sorted,or are nearly so.
5.Removal from a Binary Search Tree pg.455
从二叉查找 (搜索 /排序 )树中删除一个结点, 不能把以该结点
为根的子树都删除, 只能删掉该结点, 并且还应该保证删除
后得到的二叉树仍然满足二叉查找树的性质, 即在二叉查找
树中 删除一个结点相当于删去有序序列中的一个结点 。 那么,
如何在二叉查找树上删去一个结点呢? 如上页图所示：当被
删结点是叶子或仅有一棵子树时, 情况较简单, 只是修改其
双亲结点的指针就可以了；若被删结点既有左子树也有右子
树时, 应当如何处理呢？ 假设在二叉查找树上被删结点为
P(指向结点的指针为 p),其双亲结点为 F(结点指针为 f),且
不失一般性, 可设 p是 f的左指针, 即被删结点 P是 F的左孩子 。
一种处理方法如下页图所示：以被删结点的左子树中最大结
点 S(必然是叶子 )的数据代替 被删结点 P的数据, 然后删除叶
子 S。
Auxiliary Function to Remove One Node,
template <class Record>Error_code Search_tree<Record>::
remove_root(Binary_node<Record>* &sub_root)
{ if(sub_root==NULL) return not_present;
Binary_node<Record> *to_delete=sub_root->left;
if(sub_root->right==NULL) sub_root=sub_root->left;
else if(sub_root->left==NULL) sub_root=sub_root->right;
else // else(2)
{ to_delete=sub_root->left;
Binary_node<Record> *parent=sub_root;
while(to_delete->right!=NULL)
{ parent=to_delete;
to_delete=to_delete->right;
}
sub_root->data=to_delete->data;
注意,sub_root
一定是引用参数
sub_root只有左
子树,以左孩子做为
删除后子树的新根
sub_root只有右
子树,以右孩子做为
删除后子树的新根
sub_root既有左
子树,也有右子树,
搜寻它的左子树
中最大结点
令 to_delete移动到
sub_root的左孩子
指针 parent
保持跟踪 to_delete
是 它 的双亲结点
在 sub_root所指
结点的 左子树中
搜寻最大结点
(此结点是它的前驱 )
脱离循环 to_delete
指向找到的结点
将 to_delete所指结点
的 数据域转移到
sub_root所指结点If sub_root is NULL
a code of not_present
is returned,Otherwise,
the root of the subtree
is removed in such a way that
the properties of a binary search tree
are preserved,The parameter sub_root
is reset as the root of the
modified subtree,and
success is returned.
if(parent==sub_root) sub_root ->left=to_delete->left;
else parent->right=to_delete->left;
} // end else(2)
delete to_delete;
return success;
} to_delete是 sub_root
的左孩子它没有右子树,
因此,将 to_delete所指结点
的左 子树做为 sub_root
(parent)的左子树
将 to_delete所指结点
的左 子树做为 parent的右子树Remove to_delete from treeRemoval Method:
template <class Record>Error_code
Search_tree<Record>::remove(const Record &target)
{ return search_and_destroy(root,target); }
Recursive function,search_and_destroy
template <class Record>Error_code Search_tree<Record>::
search_and_destroy(Binary_node<Record>* &sub_root,
const Record &target)
{ if(sub_root==NULL || sub_root->data==target)
return remove_root(sub_root);
else if (target<sub_root->data)
return search_and_destroy(sub_root->left,target);
else
return search_and_destroy(sub_root->right,target);
}
按 target值向左 (右 )子树递归
调用搜寻被删结点,sub_root的
左 (右 )孩子域做为 递归调用参数,
这样当到达边界调用 remove_root时
sub_root的地址就可以由引用参数
带回到其双亲结点的左 (右 )孩子域
10.3 Building a Balanced Binary Search Tree
Problem,Start with an ordered list and build its entries
into a binary search tree that is nearly balanced (?bushy?).
If the nodes of a complete binary tree are labeled in
inorder sequence,starting with 1,then each node is
exactly as many levels above the leaves as the
highest power of 2 that divides its label.
由于课时不够, 本节删略 。 感兴趣的同学可以自学 。
See Pg 463-472
10.4 Height Balance,AVL Trees
1.Denition:
An AVL tree is a binary search tree in which the
heights of the left and right subtrees of the root differ
by at most 1 and in which the left and right subtrees
are again AVL trees.
With each node of an AVL tree is associated a
balance factor that is left higher,equal,or right
higher according,respectively,as the left subtree
has height greater than,equal to,or less than that of
the right subtree.
平衡因子
中文教材中，平衡因子＝左子树高度－右子树高度；因此
AVL定义为 BST中任一结点平衡因子的绝对值 ≤ 1。
平衡左高 1左高 2
右高 2enum Balance_factor {
left_higher,equal_height,right_higher };
本教材中，将平衡因子定义为?枚举?类型。
AVL_node,pg.475
template <class Record>
struct AVL_node,public Binary_node<Record>
{ Balance_factor balance;
AVL_node()
{ balance = equal_height; left = right = NULL; }
AVL_node(const Record &x);
{ balance = equal_height; data = x; left = right = NULL; }
void set_balance(Balance_factor b)
{ balance = b; }
Balance_factor get_balance() const
{ return balance; }
};
inherit
data memberconstructorconstructor
? In a Binary_node,left and right have type Binary_node*,
so the inherited pointer members of an AVL node have
this type too,not the more restricted AVL node *,
In the insertion method,we must make sure to insert
only genuine AVL nodes.
? The benefit of implementing AVL nodes with a derived
structure is the reuse of all of our functions for
processing nodes of binary trees and search trees.
? We often invoke these methods through pointers to
nodes,such as left->get_balance( ),But left could (for
the compiler) point to any Binary_node,not just to an
AVL_node,and these methods are declared only for
AVL_node.
? A C++ compiler must reject a call such as left->get
balance( ),since left might point to a Binary node that is
not an AVL_node.
? To enable calls such as left->get_balance( ),
we include dummy versions of get_balance( ) and
set_balance( ) in the underlying Binary_node
structure,These do nothing:
template <class Entry>
void Binary_node<Record>::set_balance(Balance_factor b)
{ }
template <class Entry> Balance_factor
Binary_node<Record>::get_balance(Balance_factor b)
{ return equal_height; }
Class Declaration for AVL Trees
template <class Record>
class AVL_tree,public Search_tree<Record>
{ public:
Error_code insert(const Record &new_data);
Error_code remove(const Record &old_data);
private:
void prenode(void (*f)(Binary_node<Record> *&));
Error_code avl_insert(Binary_node<Record> *&,
const Record &,bool &);
void right_balance(Binary_node<Record> *&);
void left_balance(Binary_node<Record> *&);
void rotate_left(Binary_node<Record> *&);
void rotate_right(Binary_node<Record> *&);
Error_code remove_avl(Binary_node<Record> *&,
const Record &,bool &);
Error_code remove_avl_right(Binary_node<Record> *&,
const Record &,bool &);
Error_code remove_avl_left(Binary_node<Record> *&,
const Record &,bool &);
// Add auxiliary function prototypes here.
};
2.Insertions of a Node
See pg.478 Fig,10.18
Simple insertions of nodes into an AVL tree
AVL insertions requiring rotations
(pg.483 Fig.10.21)
Public Insertion Method
template <class Record>Error_code AVL_tree<Record>::
insert(const Record &new_data)
{ bool taller;
return avl_insert(root,new_data,taller);
}
Post,If the key of new_data is already in the AVL_tree,a
code of duplicate_error is returned.
Otherwise,a code of success is returned and the
Record new_data is inserted into the tree in such a
way that the properties of an AVL tree are preserved.
Uses,avl_insert,
Has the tree
grown in height?
Recursive Function Specifications
template <class Record>Error_code AVL_tree<Record>::
avl_insert ( Binary_node<Record> *&sub_root,
const Record &new_data,bool &taller )
{ Error_code result = success;
if (sub_root == NULL)
{ sub_root = new AVL_node<Record>(new_data);
taller = true;
}
else if (new_data == sub_root->data)
{ result = duplicate_error; taller = false; }
else if(new_data < sub_root->data)
{ result=avl_insert(sub_root->left,new_data,taller);
if (taller == true)
Insert into
empty subtreeduplicate_errorInsert in
left subtreeRecursive call selfleft subtree
is taller
switch (sub_root->get_balance())
{ case left_higher:
left_balance(sub_root);
taller = false; break;
case equal_height:
sub_root->set_balance(left_higher);
break;
case right_higher:
sub_root->set_balance(equal_height);
taller = false;
break;
} // end switch
} // end insert to left subtree (if block)
else
Change
balance factorsLeft subtreealready Is taller
Re balancing
always shortens
the tree
Old left subtree
Is equal heightleft subtreeIs taller
Insert in
right subtree
{ result = avl_insert(sub_root->right,new_data,taller);
if( taller == true )
switch(sub_root->get_balance())
{ case left_higher,
sub_root->set_balance(equal_height);
taller = false; break;
case equal_height,
sub_root->set_balance(right_higher);
break;
case right_higher:
right_balance(sub_root);
taller = false; break;
} // end switch
} // end insert to right subtree (else block)
return result;
}
Old left subtree
Is taller,ok!Old left subtreeIs equal height
right subtree
already Is taller
Rotations of an AVL Tree
(pg.480 Fig.10.19)
Rotations of an AVL Tree
template <class Record>void AVL_tree<Record>::
rotate_left(Binary_node<Record> *&sub_root)
{ if( sub_root == NULL || sub_root->right == NULL)
cout << "WARNING,program error detected in rotate_left\n";
else
{ Binary_node<Record> *right_tree = sub_root->right;
sub_root->right = right_tree->left;
right_tree->left = sub_root;
sub_root = right_tree;
}
}
sub_root points to
a subtree of
the AVL_tree
This subtree has a
non empty right subtreeimpossible cases
The new balance factors for root and right tree
depend on the previous balance factor for sub tree:
Double Rotation
balance of an AVL Tree
template <class Record>void AVL_tree<Record>::
right_balance(Binary_node<Record> *&sub_root)
{Binary_node<Record> *&right_tree = sub_root->right;
switch( right_tree->get_balance() )
{ case right_higher,
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
rotate_left(sub_root);
break;
case equal_height:
cout<<"WARNING,program error detected in right_balance\n";
return;
sub_root points to a
subtree of an AVL_tree
that is doubly unbalanced
on the rightsingle rotation leftimpossible cases
case left_higher:
Binary_node<Record> *sub_tree = right_tree->left;
switch (sub_tree->get_balance()) // switch(2)
{ case equal_height:
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
break;
case left_higher:
sub_root->set_balance(equal_height);
right_tree->set_balance(right_higher);
break;
case right_higher:
sub_root->set_balance(left_higher);
right_tree->set_balance(equal_height);
break;
}// end switch(2)
double rotation left
sub_tree->set_balance(equal_height);
rotate_right(right_tree);
rotate_left(sub_root);
}// end switch
}
3.Removal of a Node
1,Reduce the problem to the case when the node x
to be removed has at most one child.
2,Delete x,We use a bool variable shorter to show if
the height of a subtree has been shortened.
3,While shorter is true do the following steps for
each node p on the path from the parent of x to the
root of the tree,When shorter becomes false,the
algorithm terminates.
4,Case 1,Node p has balance factor equal,The
balance factor of p is changed according as its left or
right subtree has been shortened,and shorter
becomes false.
5,Case 2,The balance factor of p is not equal,and the
taller subtree was shortened,Change the balance
factor of p to equal,and leave shorter as true.
6,Case 3,The balance factor of p is not equal,and the
shorter subtree was shortened,Apply a rotation as
follows to restore balance,Let q be the root of the taller
subtree of p.
7,Case 3a,The balance factor of q is equal,A single
rotation restores balance,and shorter becomes false.
8,Case 3b,The balance factor of q is the same as that
of p,Apply a single rotation,set the balance factors of
p and q to equal,and leave shorter as true.
9,Case 3c,The balance factors of p and q are opposite,
Apply a double rotation (rst around q,then around p),
set the balance factor of the new root to equal and the
other balance factors as appropriate,and leave shorter
as true.
See pg.486 Fig,10.22
See pg.487 Fig,10.23
4,The height of an AVL Tree pg.485
? The number of recursive calls to insert a new node
can be as large as the height of the tree.
? At most one (single or double) rotation will be done
per insertion.
? A rotation improves the balance of the tree,so later
insertions are less likely to require rotations.
? It is very difcult to nd the height of the average AVL
tree,but the worst case is much easier,The worst-case
behavior of AVL trees is essentially no worse than the
behavior of random search trees.
? Empirical evidence suggests that the average
behavior of AVL trees is much better than that of
random trees,almost as good as that which could be
obtained from a perfectly balanced tree.
Worst-Case AVL Trees
? To find the maximum height of an AVL tree with n
nodes,we instead find the minimum number of nodes
that an AVL tree of height h can have.
? Let Fh be such a tree,with left and right subtrees Fl
and Fr, Then one of Fl and Fr,say Fl,has height h - 1
and the minimum number of nodes in such a tree,and
Fr has height h - 2 with the minimum number of nodes.
? These trees,as sparse as possible for AVL trees,are
called Fibonacci trees.
Analysis of Fibonacci trees Trees
? If we write |T| for the number of nodes in a tree T,we
then have the recurrence relation for Fibonacci trees:
|Fh| = |Fh-1| + |Fh-2| + 1.
where |F0| = 1 and |F1| = 2.
? By the evaluation of Fibonacci numbers in Section
A.4,
2h
2
51
5
11Fh ?
??
?
??
? ???
? Take the logarithms of both sides,keeping only
the largest terms:
Fh1,4 4 lgh ?
? The sparsest possible AVL tree with n nodes has
height about 1:44 lg n compared to:
?A perfectly balanced binary search tree with n
nodes has height about lg n.
?A random binary search tree,on average,has
height about 1.39 lgn.
?A degenerate binary search tree has height as
large as n.
?Hence the algorithms for manipulating AVL trees are
guaranteed to take no more than about 44 percent
more time than the optimum,In practice,AVL trees do
much better than this on average,perhaps as small as
lgn + 0.25.
10.5 Splay Trees,A Self-Adjusting Data
Structure?In some applications,we wish to keep records that are
newly inserted or frequently accessed very close to the
root,while records that are inactive may be placed far
off,near or in the leaves.
?We make a binary search tree into a self-adjusting
data structure that automatically changes its shape to
bring records closer to the root as they are more
frequently accessed,allowing inactive records to drift
slowly out toward the leaves,
?In a splay tree,every time we access a node,whether
for insertion or retrieval,we lift the newly-accessed
node all the way up to become the root of the modied
tree.
?We use rotations like those of AVL trees,but now with
many rotations done for every insertion or retrieval in
the tree.
?We move the target node two levels up the tree at
each step.Consider the path going from the root down
to the accessed node,If we move left,we say that we
zig,and if we move right we say that we zag,A move of
two steps left (going down) is then called zig-zig,two
steps right zag-zag,left then right zig-zag,and right
then left zag-zig,If the length of the path is odd,either
a single zig move or a zag move occurs at the end.
Splay Rotations
Splay Rotations
? The zig-zag case is identical to that of an AVL double
rotation,and the zig case is identical to a single rotation.
? The zig-zig case is not the same as would be obtained
by lifting the target node twice with single rotations.
? Always think of lifting the target two levels at a time
(except for a single zig or zag step at the end).
? It is only the nodes on the path from the target to the
root whose relative positions are changed,and that
only in the ways shown by colored dashed curves in
the figures.
? None of the subtrees off the path (T1,T2,T3,and T4 )
changes its shape at all,and these subtrees are
attached to the path in the only places they can go to
maintain the search-tree ordering of all the keys.
Zig-Zig and Single Rotations
? A zig-zig movement is not the same as would be
obtained by lifting the target node twice with single
rotations.
Top-Down and Bottom-Up Splaying
? By hand,we perform bottom-up splaying,
beginning at the target node and moving up the path
to the root two steps at a time,A single zig or zag
move may occur at the top of the tree,Bottom-up
splaying is essentially a two-pass method,
first searching down the tree and then splaying the
target up to the root.
? In a computer algorithm,we splay from the top down
while we are searching for the target node,When we nd
the target,it is immediately moved to the root of the
tree,or,if the search is unsuccessful,a new root is
created that holds the target,In top-down splaying,a
single zig or zag move occurs at the bottom of the
splaying process.
?If you run the splaying function we develop on the
example trees,you will obtain the same results as
doing bottom-up splaying by hand when the target is
moved an even number of levels,but the results will be
different when it moves an odd number of levels.
Algorithm Development
? Given a target key,we develop a function that
searches down the tree for the key,splaying as it goes,
If it finds the key,then it retrieves it; if not,then the
function inserts it in a new node,In either case,the
node with the target key becomes the root of the tree.
? We implement splay trees as a derived class of class
Search tree.
这部分源代码可以复制给大家,splay tree比较灵活，有一
定的应用价值，由于时间关系，这部分不再细讲。
Pointers and Pitfalls
? Consider binary search trees as an alternative to
ordered lists,At the cost of an extra pointer eld in
each node,binary search trees allow random access
(with O(log n)key comparisons) to all nodes while
maintaining the flexibility of linked lists for insertions,
deletions,and rearrangement.
?Consider binary search trees as an alternative to
tables,At the cost of access time that is O(logn)
instead of O(1),binary search trees allow traversal of
the data structure in the order specified by the keys
while maintaining the advantage of random access
provided by tables.
? In choosing your data structures,always carefully
consider what operations will be required,Binary
trees are especially appropriate when the
requirements include random access,traversal in a
predetermined order,and flexibility in making
insertions and deletions.
? While choosing data structures and algorithms,
remain alert to the possibility of highly unbalanced
binary search trees,AVL trees provide nearly perfect
balance at a slight cost in computer time and space,
but with considerable programming cost,If it is
necessary for the tree to adapt dynamically to
changes in the frequency of the data,then a splay
tree may be the best choice.
? Binary trees are dened recursively; algorithms for
manipulating binary trees are usually,but not always,
best written recursively.
? Although binary trees are most commonly
implemented as linked structures,remain aware of
the possibility of other implementations.
1,General Binary Trees
2,Binary Search Trees
3,Building a Binary Search
Tree4,Height Balance,AVL Trees
5,Splay Trees
6,Pointers and Pitfalls
10.1 Binary Trees
DEFINITION A binary tree is either empty,or it
consists of a node called the root together with two
binary trees called the left subtree and the right
subtree of the root.
1,Definitions
2,Traversal of Binary Trees
At a given node there are three tasks to do in some
order,Visit the node itself (V); traverse its left subtree
(L); traverse its right subtree (R),There are six ways to
arrange these tasks:
VLR LVR LRV VRL RVL RLV
By standard convention,these are reduced to three
by considering only the ways in which the left subtree
is traversed before the right,
preorderinorderpostorder
These three names are chosen according to the
step at which the given node is visited.
◆ With preorder traversal we first visit a node,then
traverse its left subtree,and then traverse its right
subtree.
◆ With inorder traversal we first traverse the left
subtree,then visit the node,and then traverse its
right subtree.
◆ With postorder traversal we first traverse the left
subtree,then traverse the right subtree,and nally
visit the node.
See pg.432-434
Expression tree
x = (-b+(b↑2-4× a× c)↑0.5) / (2× a)
3,Linked implementation of Binary Trees
Node structure of Binary Trees
example
Linked Binary Trees Specifications
template <class Entry>
class Binary_tree
{ public:
// Add methods here.
protected:
// Add auxiliary function prototypes here.
Binary_node<Entry> *root;
};
Binary trees class 二叉树根 结点 指针
template <class Entry>
struct Binary_node
{ Entry data;
Binary_node<Entry> *left;
Binary_node<Entry> *right;
Binary_node( );
Binary_node(const Entry & x);
};
Binary node class 数据域指向左孩子的指针指向右孩子的指针
template <class Entry>
void Binary_tree<Entry>::inorder(void (*visit)(Entry &))
{ recursive_inorder(root,visit); }
template <class Entry> void Binary_tree<Entry>::
recursive_inorder(Binary_node<Entry> *sub_root,
void (*visit)(Entry &))
/* Pre,sub_root is either NULL or points to a subtree of the inary_tree.
Post,The subtree has been traversed in inorder sequence,*/
{ if (sub_root != NULL)
{ recursive_inorder(sub_root->left,visit);
(*visit)(sub_root->data);
recursive_inorder(sub_root->right,visit);
}
}
Inorder traversal,method函数参数
(访问数据 )
调用递归中序
遍历函数递归中序遍历函数
多一个参数
◆ 树形结构是一类重要的非线性结构。树能够很好地描述结
构的分支关系和层次特性，它非常类似于自然界中的树。树
结构在客观世界中是大量存在的，例如家谱以及行政组织机
构都可用树形象地表示。树在计算机领域中也有着广泛的应
用，如在编译程序中，用树来表示源程序语法结构；在数据
库系统中，可以用树来组织信息。本章重点讨论二叉树的存
储表示及其各种运算，要求大家要学会编写实现二叉树的各
种运算的算法。
◆ 二叉树是递归定义 的，因此 递归是它的固有特性，本小节
的练习中就要求大家完成许多 操作二叉树的算法，且是 递归
算法 。
◆ 下面 我们给出一个以先序方式创建任意二叉树的算法，请
认真学习。
template<class Entry>
void Binary_tree<Entry>::CreatBinary_tree()
{ CreatBinary_tree(root); }
template<class Entry> void Binary_tree<Entry>::
CreatBinary_tree(Binary_node<Entry>* &r)
{ cin>>x;
if ( x==endmark ) r = NULL;
else{ r = new Binary_Node<Entry>(x);
CreatBinary_tree(r->left);
CreatBinary_tree(r->right);
}
}
建立二叉链表
表示的二叉树
递归建立以 r为
根结点指针的二叉链表
表示的二叉树
建立 ? 空 ? 二叉树建立根结点建立根结点
的左子树建立根结点 的右子树
Entry
data member
表示‘空’的
数据
我们再给出一个应用例。
在以二叉链表存储的二叉树中查找值为 x的结点，请编
写一非递归算法：打印值为 x的结点的所有的祖先结点
的值。设值为 x的结点不多于 1个。
template <class T> printAncestors(Binary_tree<T> tree,
T& x)
{ typedef struct
{ Binary_node<T>* ptr; int tag; } StackNode;
StackNode ST[100]; int i,top = -1,find=0;
Binary_node<T>* t = tree.GetRoot();
if(t->data==x) { cout<<x<<" is Root\n"; return; }
while( t && t->data!=x || top!=-1 )
{ while(t && t->data != x)
{ ST[++ top].ptr=t; ST[top].tag = 0; t=t->left; }
在二叉树 tree中搜索
结点 x，找到则打印
所有祖先结点及 x
否则输出 x不存在
要求非递归
因此自行定义
‘栈结点’类型
指针域 (保留从根到
搜索结点路径上
所以结点指针 )
标记域
(tag==0左子树
否则是右子树 )置空栈
栈数组栈结点类型名
取得二叉树 tree
的根结点指针
做为 t的初始值
指针不‘空’而且
其所指结点的
数据域不是 x栈不‘空’搜索左子树
寻找值为 x的结点进栈
二叉树 tree
的根结点是 x
if (t && t->data==x)
{ for(i=0; i<=top; i++) cout<<ST[i].ptr->data<<endl;
cout<<x<<endl; find=1;
break;
}
else
{ while( top!=-1 && ST[top].tag==1) top--;
if (top!=-1) { ST[top].tag=1; t=ST[top].ptr->right; }
} // end_(if-else)block
} // end_while
if (!find) cout<<" search "<<x<<" not exists\n";
}
找到值为 x的结点
输出所有祖先结点
(栈 )
跳出 while循环如果栈顶是右指针
弹出
如果栈不空
栈顶是左指针
转向右子树
重新回到 while
没找到值为 x的结点
在 C++环境下演示创建二叉树及在建立的二叉树上完
成各项操作的 bt_main.cpp。
10.2 Binary Search Trees
Can we find an implementation for ordered lists in
which we can search quickly (as with binary search on
a contiguous list) and in which we can make insertions
and deletions quickly (as with a linked list)?
A binary search tree is a binary trees that is either
empty or in which the data entry of every node has a
key and satisfies the conditions:
1,The key of the root (if it exists) is greater than the
key in any node in the left subtree of the root.
2,The key of the root (if it exists) is less than the
key in any node in the right subtree of the root.
3,The left and right subtrees of the root are again
binary search trees.
binary search tree Definitions pg.445
binary searchtree not binary searchtree
DEFINITION A binary search tree is a binary tree that is
either empty or in which the data entry of every node has a
key and satises the conditions:
1,The key of the left child of a node (if it exists) is less than
the key of its parent node.
2,The key of the right child of a node (if it exists) is greater
than the key of its parent node.
3,The left and right subtrees of the root are again binary
search trees.
errorerror
We always require:
No two entries in a binary search tree may have equal keys.
? We can regard binary search trees as a new ADT.
? We may regard binary search trees as a
specialization of binary trees.
? We may study binary search trees as a new
implementation of the ADT ordered list.
? The binary search tree class will be derived from the
binary tree class; hence all binary tree methods are
inherited.
1,Ordered Lists and Implementations pg.446
The Binary Search Tree Class pg.446
template <class Record>
class Search_tree:public Binary_tree <Record>
{ public:
Error_code insert(const Record &new_data);
Error_code remove(const Record &old_data);
Error_code tree_search(Record &target) const;
protected:
// Add auxiliary function prototypes here.
};
?The inherited methods include the constructors,
the destructor,clear,empty,size,height,and the
traversals preorder,inorder,and postorder.
?A binary search tree also admits specialized methods
called insert,remove,and tree search.
?The class Record has the behavior outlined in
Chapter 7,Each Record is associated with a Key,
The keys can be compared with the usual
comparison operators,By casting records to their
corresponding keys,the comparison operators apply
to records as well as to keys.
2,Tree Search pg.447
Error_code Search_tree<Record>::
tree_search(Record &target) const;
Post,If there is an entry in the tree whose key
matches that
in target,the parameter target is replaced by the
corresponding record from the tree and a code
of
success is returned,
?This method will often be called with a parameter
target that contains only a key value,The method will
fill target with the complete data belonging to any
corresponding Record in the tree.
?To search for the target,we first compare it with the
entry at the root of the tree,If their keys match,then we
are finished,Otherwise,we go to the left subtree or
right subtree as appropriate and repeat the search in
that subtree.
?We program this process by calling an auxiliary
recursive function.
?The process terminates when it either finds the target
or hits an empty subtree.
? The auxiliary search function returns a pointer to the
node that contains the target back to the calling
program,Since it is private in the class,this pointer
manipulation will not compromise tree encapsulation.
Binary_node<Record>* Search_tree<Record>::
search_for_node(Binary_node<Record> *sub_root,
const Record &target) const
Pre,sub root is NULL or points to a subtree of a
Search tree
Post,If the key of target is not in the subtree,a result
of
NULL is returned,
Otherwise a pointer to the subtree node
containing the
Recursive auxiliary function,pg.448
Non-recursive version:
template <class Record> Binary_node<Record>*
Search_tree<Record>::search_for_node(Binary_node<Record>
*sub_root,const Record &target) const
{ while(sub_root!=NULL && sub_root->data!=target)
if(sub_root->data<target) sub_root = sub_root->right;
else sub_root = sub_root->left;
return sub_root;
}
Public method for tree search:
template <class Record> Error_code Search_tree<Record>:,
tree_search(Record &target) const
{ Error_code result = success;
Binary_node<Record> *found;
found = search_for_node(root,target) ;
if(found==NULL) result = not_present;
else target = found->data;
return result;
}
Binary Search Trees with the Same Keys
The same keys
may be built into
binary search trees of
many different shapes
Analysis of Tree Search
? Draw the comparison tree for a binary search (on an
ordered list),Binary search on the list does exactly the
same comparisons as tree search will do if it is applied
to the comparison tree,By Section 7.4,binary search
performs O(㏒ n)comparisons for a list of length n,This
performance is excellent in comparison to other
methods,since ㏒ n grows very slowly as n increases.
?The same keys may be built into binary search trees
of many different shapes.
?If a binary search tree is nearly completely balanced
(“bushy”),then tree search on a tree with n vertices will
also do O (㏒ n) comparisons of keys.
? If the tree degenerates into a long chain,then tree
search becomes the same as sequential search,doing
?(n)comparisons on n vertices,This is the worst case
for tree search.
?The number of vertices between the root and the
target,inclusive,is the number of comparisons that
must be done to find the target,The bushier the tree,
the smaller the number of comparisons that will usually
need to be done.
?It is often not possible to predict (in advance of
building it) what shape of binary search tree will occur.
?In practice,if the keys are built into a binary search
tree in random order,then it is extremely unlikely that a
binary search tree degenerates badly; tree_search
usually performs almost as well as binary search.
3.Insertion into a Binary Search Tree pg.451
Error_code Search tree<Record>::
insert(const Record &new data);
Post,If a Record with a key matching that of new
data already belongs to the Search tree a code of
duplicate_error is returned,Otherwise,the Record
new data is inserted into the tree in such a way that
the properties of a binary search tree are preserved,
and a code of success is returned.
Method for Insertion
template <class Record>Error_code
Search_tree<Record>::insert(const Record &new_data)
{ if(root==NULL)
{ root=new Binary_node<Record>(new_data);
return success;
}
Binary_node<Record> *sub_root=root,*parent;
do{ parent=sub_root;
if(new_data<sub_root->data) sub_root=sub_root->left;
else if(new_data>sub_root->data)
sub_root=sub_root->right;
else return duplicate_error;
}while(sub_root!=NULL);
“空 ? BST
直接插入 (根结点 )
寻找
插入位置
插入数据小于
当前 (子树根 )结点数据
继续在左子树中
搜寻插入位置
在右子树中
搜寻插入位置
直至到达一个 ‘ 空 ’ BST
子树，脱离循环；这时
插入结点应是 parent
的孩子
sub_root=new Binary_node<Record>(new_data);
if(new_data<parent->data) parent->left=sub_root;
else parent->right = sub_root;
return success;
}
根据 插入结点值
确定应是 parent
的左孩子还是右孩子？
The method insert can usually insert a new node
into a random binary search tree with n nodes in
O(㏒ n) steps,It is possible,but extremely unlikely,
that a random tree may degenerate so that
insertions require as many as n steps,If the keys
are inserted in sorted order into an empty tree,
however,this degenerate case will occur.
See pg.453 Theorem 10.1 and Corollary 10.2
?When a binary search tree is traversed in inorder,the
keys will come out in sorted order.
?This is the basis for a sorting method,called treesort,
Take the entries to be sorted,use the method insert to
build them into a binary search tree,and then use
inorder traversal to put them out in order.
Theorem 10.1 Treesort makes exactly the same
comparisons of keys as does quicksort when the
pivot for each sublist is chosen to be the first key
in the sublist.
4,Treesort pg.453
Corollary 10.2 In the average case,on a randomly
ordered list of length n,treesort performs
comparisons of keys,O ( n)n1, 3 9 nlO ( n)n2 nl gn ???
?First advantage of treesort over quicksort,The nodes
need not all be available at the start of the process,but
are built into the tree one by one as they become
available.
?Second advantage,The search tree remains available
for later insertions and removals.
?Drawback,If the keys are already sorted,then treesort
will be a disaster-- the search tree it builds will reduce
to a chain,Treesort should never be used if the keys
are already sorted,or are nearly so.
5.Removal from a Binary Search Tree pg.455
从二叉查找 (搜索 /排序 )树中删除一个结点, 不能把以该结点
为根的子树都删除, 只能删掉该结点, 并且还应该保证删除
后得到的二叉树仍然满足二叉查找树的性质, 即在二叉查找
树中 删除一个结点相当于删去有序序列中的一个结点 。 那么,
如何在二叉查找树上删去一个结点呢? 如上页图所示：当被
删结点是叶子或仅有一棵子树时, 情况较简单, 只是修改其
双亲结点的指针就可以了；若被删结点既有左子树也有右子
树时, 应当如何处理呢？ 假设在二叉查找树上被删结点为
P(指向结点的指针为 p),其双亲结点为 F(结点指针为 f),且
不失一般性, 可设 p是 f的左指针, 即被删结点 P是 F的左孩子 。
一种处理方法如下页图所示：以被删结点的左子树中最大结
点 S(必然是叶子 )的数据代替 被删结点 P的数据, 然后删除叶
子 S。
Auxiliary Function to Remove One Node,
template <class Record>Error_code Search_tree<Record>::
remove_root(Binary_node<Record>* &sub_root)
{ if(sub_root==NULL) return not_present;
Binary_node<Record> *to_delete=sub_root->left;
if(sub_root->right==NULL) sub_root=sub_root->left;
else if(sub_root->left==NULL) sub_root=sub_root->right;
else // else(2)
{ to_delete=sub_root->left;
Binary_node<Record> *parent=sub_root;
while(to_delete->right!=NULL)
{ parent=to_delete;
to_delete=to_delete->right;
}
sub_root->data=to_delete->data;
注意,sub_root
一定是引用参数
sub_root只有左
子树,以左孩子做为
删除后子树的新根
sub_root只有右
子树,以右孩子做为
删除后子树的新根
sub_root既有左
子树,也有右子树,
搜寻它的左子树
中最大结点
令 to_delete移动到
sub_root的左孩子
指针 parent
保持跟踪 to_delete
是 它 的双亲结点
在 sub_root所指
结点的 左子树中
搜寻最大结点
(此结点是它的前驱 )
脱离循环 to_delete
指向找到的结点
将 to_delete所指结点
的 数据域转移到
sub_root所指结点If sub_root is NULL
a code of not_present
is returned,Otherwise,
the root of the subtree
is removed in such a way that
the properties of a binary search tree
are preserved,The parameter sub_root
is reset as the root of the
modified subtree,and
success is returned.
if(parent==sub_root) sub_root ->left=to_delete->left;
else parent->right=to_delete->left;
} // end else(2)
delete to_delete;
return success;
} to_delete是 sub_root
的左孩子它没有右子树,
因此,将 to_delete所指结点
的左 子树做为 sub_root
(parent)的左子树
将 to_delete所指结点
的左 子树做为 parent的右子树Remove to_delete from treeRemoval Method:
template <class Record>Error_code
Search_tree<Record>::remove(const Record &target)
{ return search_and_destroy(root,target); }
Recursive function,search_and_destroy
template <class Record>Error_code Search_tree<Record>::
search_and_destroy(Binary_node<Record>* &sub_root,
const Record &target)
{ if(sub_root==NULL || sub_root->data==target)
return remove_root(sub_root);
else if (target<sub_root->data)
return search_and_destroy(sub_root->left,target);
else
return search_and_destroy(sub_root->right,target);
}
按 target值向左 (右 )子树递归
调用搜寻被删结点,sub_root的
左 (右 )孩子域做为 递归调用参数,
这样当到达边界调用 remove_root时
sub_root的地址就可以由引用参数
带回到其双亲结点的左 (右 )孩子域
10.3 Building a Balanced Binary Search Tree
Problem,Start with an ordered list and build its entries
into a binary search tree that is nearly balanced (?bushy?).
If the nodes of a complete binary tree are labeled in
inorder sequence,starting with 1,then each node is
exactly as many levels above the leaves as the
highest power of 2 that divides its label.
由于课时不够, 本节删略 。 感兴趣的同学可以自学 。
See Pg 463-472
10.4 Height Balance,AVL Trees
1.Denition:
An AVL tree is a binary search tree in which the
heights of the left and right subtrees of the root differ
by at most 1 and in which the left and right subtrees
are again AVL trees.
With each node of an AVL tree is associated a
balance factor that is left higher,equal,or right
higher according,respectively,as the left subtree
has height greater than,equal to,or less than that of
the right subtree.
平衡因子
中文教材中，平衡因子＝左子树高度－右子树高度；因此
AVL定义为 BST中任一结点平衡因子的绝对值 ≤ 1。
平衡左高 1左高 2
右高 2enum Balance_factor {
left_higher,equal_height,right_higher };
本教材中，将平衡因子定义为?枚举?类型。
AVL_node,pg.475
template <class Record>
struct AVL_node,public Binary_node<Record>
{ Balance_factor balance;
AVL_node()
{ balance = equal_height; left = right = NULL; }
AVL_node(const Record &x);
{ balance = equal_height; data = x; left = right = NULL; }
void set_balance(Balance_factor b)
{ balance = b; }
Balance_factor get_balance() const
{ return balance; }
};
inherit
data memberconstructorconstructor
? In a Binary_node,left and right have type Binary_node*,
so the inherited pointer members of an AVL node have
this type too,not the more restricted AVL node *,
In the insertion method,we must make sure to insert
only genuine AVL nodes.
? The benefit of implementing AVL nodes with a derived
structure is the reuse of all of our functions for
processing nodes of binary trees and search trees.
? We often invoke these methods through pointers to
nodes,such as left->get_balance( ),But left could (for
the compiler) point to any Binary_node,not just to an
AVL_node,and these methods are declared only for
AVL_node.
? A C++ compiler must reject a call such as left->get
balance( ),since left might point to a Binary node that is
not an AVL_node.
? To enable calls such as left->get_balance( ),
we include dummy versions of get_balance( ) and
set_balance( ) in the underlying Binary_node
structure,These do nothing:
template <class Entry>
void Binary_node<Record>::set_balance(Balance_factor b)
{ }
template <class Entry> Balance_factor
Binary_node<Record>::get_balance(Balance_factor b)
{ return equal_height; }
Class Declaration for AVL Trees
template <class Record>
class AVL_tree,public Search_tree<Record>
{ public:
Error_code insert(const Record &new_data);
Error_code remove(const Record &old_data);
private:
void prenode(void (*f)(Binary_node<Record> *&));
Error_code avl_insert(Binary_node<Record> *&,
const Record &,bool &);
void right_balance(Binary_node<Record> *&);
void left_balance(Binary_node<Record> *&);
void rotate_left(Binary_node<Record> *&);
void rotate_right(Binary_node<Record> *&);
Error_code remove_avl(Binary_node<Record> *&,
const Record &,bool &);
Error_code remove_avl_right(Binary_node<Record> *&,
const Record &,bool &);
Error_code remove_avl_left(Binary_node<Record> *&,
const Record &,bool &);
// Add auxiliary function prototypes here.
};
2.Insertions of a Node
See pg.478 Fig,10.18
Simple insertions of nodes into an AVL tree
AVL insertions requiring rotations
(pg.483 Fig.10.21)
Public Insertion Method
template <class Record>Error_code AVL_tree<Record>::
insert(const Record &new_data)
{ bool taller;
return avl_insert(root,new_data,taller);
}
Post,If the key of new_data is already in the AVL_tree,a
code of duplicate_error is returned.
Otherwise,a code of success is returned and the
Record new_data is inserted into the tree in such a
way that the properties of an AVL tree are preserved.
Uses,avl_insert,
Has the tree
grown in height?
Recursive Function Specifications
template <class Record>Error_code AVL_tree<Record>::
avl_insert ( Binary_node<Record> *&sub_root,
const Record &new_data,bool &taller )
{ Error_code result = success;
if (sub_root == NULL)
{ sub_root = new AVL_node<Record>(new_data);
taller = true;
}
else if (new_data == sub_root->data)
{ result = duplicate_error; taller = false; }
else if(new_data < sub_root->data)
{ result=avl_insert(sub_root->left,new_data,taller);
if (taller == true)
Insert into
empty subtreeduplicate_errorInsert in
left subtreeRecursive call selfleft subtree
is taller
switch (sub_root->get_balance())
{ case left_higher:
left_balance(sub_root);
taller = false; break;
case equal_height:
sub_root->set_balance(left_higher);
break;
case right_higher:
sub_root->set_balance(equal_height);
taller = false;
break;
} // end switch
} // end insert to left subtree (if block)
else
Change
balance factorsLeft subtreealready Is taller
Re balancing
always shortens
the tree
Old left subtree
Is equal heightleft subtreeIs taller
Insert in
right subtree
{ result = avl_insert(sub_root->right,new_data,taller);
if( taller == true )
switch(sub_root->get_balance())
{ case left_higher,
sub_root->set_balance(equal_height);
taller = false; break;
case equal_height,
sub_root->set_balance(right_higher);
break;
case right_higher:
right_balance(sub_root);
taller = false; break;
} // end switch
} // end insert to right subtree (else block)
return result;
}
Old left subtree
Is taller,ok!Old left subtreeIs equal height
right subtree
already Is taller
Rotations of an AVL Tree
(pg.480 Fig.10.19)
Rotations of an AVL Tree
template <class Record>void AVL_tree<Record>::
rotate_left(Binary_node<Record> *&sub_root)
{ if( sub_root == NULL || sub_root->right == NULL)
cout << "WARNING,program error detected in rotate_left\n";
else
{ Binary_node<Record> *right_tree = sub_root->right;
sub_root->right = right_tree->left;
right_tree->left = sub_root;
sub_root = right_tree;
}
}
sub_root points to
a subtree of
the AVL_tree
This subtree has a
non empty right subtreeimpossible cases
The new balance factors for root and right tree
depend on the previous balance factor for sub tree:
Double Rotation
balance of an AVL Tree
template <class Record>void AVL_tree<Record>::
right_balance(Binary_node<Record> *&sub_root)
{Binary_node<Record> *&right_tree = sub_root->right;
switch( right_tree->get_balance() )
{ case right_higher,
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
rotate_left(sub_root);
break;
case equal_height:
cout<<"WARNING,program error detected in right_balance\n";
return;
sub_root points to a
subtree of an AVL_tree
that is doubly unbalanced
on the rightsingle rotation leftimpossible cases
case left_higher:
Binary_node<Record> *sub_tree = right_tree->left;
switch (sub_tree->get_balance()) // switch(2)
{ case equal_height:
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
break;
case left_higher:
sub_root->set_balance(equal_height);
right_tree->set_balance(right_higher);
break;
case right_higher:
sub_root->set_balance(left_higher);
right_tree->set_balance(equal_height);
break;
}// end switch(2)
double rotation left
sub_tree->set_balance(equal_height);
rotate_right(right_tree);
rotate_left(sub_root);
}// end switch
}
3.Removal of a Node
1,Reduce the problem to the case when the node x
to be removed has at most one child.
2,Delete x,We use a bool variable shorter to show if
the height of a subtree has been shortened.
3,While shorter is true do the following steps for
each node p on the path from the parent of x to the
root of the tree,When shorter becomes false,the
algorithm terminates.
4,Case 1,Node p has balance factor equal,The
balance factor of p is changed according as its left or
right subtree has been shortened,and shorter
becomes false.
5,Case 2,The balance factor of p is not equal,and the
taller subtree was shortened,Change the balance
factor of p to equal,and leave shorter as true.
6,Case 3,The balance factor of p is not equal,and the
shorter subtree was shortened,Apply a rotation as
follows to restore balance,Let q be the root of the taller
subtree of p.
7,Case 3a,The balance factor of q is equal,A single
rotation restores balance,and shorter becomes false.
8,Case 3b,The balance factor of q is the same as that
of p,Apply a single rotation,set the balance factors of
p and q to equal,and leave shorter as true.
9,Case 3c,The balance factors of p and q are opposite,
Apply a double rotation (rst around q,then around p),
set the balance factor of the new root to equal and the
other balance factors as appropriate,and leave shorter
as true.
See pg.486 Fig,10.22
See pg.487 Fig,10.23
4,The height of an AVL Tree pg.485
? The number of recursive calls to insert a new node
can be as large as the height of the tree.
? At most one (single or double) rotation will be done
per insertion.
? A rotation improves the balance of the tree,so later
insertions are less likely to require rotations.
? It is very difcult to nd the height of the average AVL
tree,but the worst case is much easier,The worst-case
behavior of AVL trees is essentially no worse than the
behavior of random search trees.
? Empirical evidence suggests that the average
behavior of AVL trees is much better than that of
random trees,almost as good as that which could be
obtained from a perfectly balanced tree.
Worst-Case AVL Trees
? To find the maximum height of an AVL tree with n
nodes,we instead find the minimum number of nodes
that an AVL tree of height h can have.
? Let Fh be such a tree,with left and right subtrees Fl
and Fr, Then one of Fl and Fr,say Fl,has height h - 1
and the minimum number of nodes in such a tree,and
Fr has height h - 2 with the minimum number of nodes.
? These trees,as sparse as possible for AVL trees,are
called Fibonacci trees.
Analysis of Fibonacci trees Trees
? If we write |T| for the number of nodes in a tree T,we
then have the recurrence relation for Fibonacci trees:
|Fh| = |Fh-1| + |Fh-2| + 1.
where |F0| = 1 and |F1| = 2.
? By the evaluation of Fibonacci numbers in Section
A.4,
2h
2
51
5
11Fh ?
??
?
??
? ???
? Take the logarithms of both sides,keeping only
the largest terms:
Fh1,4 4 lgh ?
? The sparsest possible AVL tree with n nodes has
height about 1:44 lg n compared to:
?A perfectly balanced binary search tree with n
nodes has height about lg n.
?A random binary search tree,on average,has
height about 1.39 lgn.
?A degenerate binary search tree has height as
large as n.
?Hence the algorithms for manipulating AVL trees are
guaranteed to take no more than about 44 percent
more time than the optimum,In practice,AVL trees do
much better than this on average,perhaps as small as
lgn + 0.25.
10.5 Splay Trees,A Self-Adjusting Data
Structure?In some applications,we wish to keep records that are
newly inserted or frequently accessed very close to the
root,while records that are inactive may be placed far
off,near or in the leaves.
?We make a binary search tree into a self-adjusting
data structure that automatically changes its shape to
bring records closer to the root as they are more
frequently accessed,allowing inactive records to drift
slowly out toward the leaves,
?In a splay tree,every time we access a node,whether
for insertion or retrieval,we lift the newly-accessed
node all the way up to become the root of the modied
tree.
?We use rotations like those of AVL trees,but now with
many rotations done for every insertion or retrieval in
the tree.
?We move the target node two levels up the tree at
each step.Consider the path going from the root down
to the accessed node,If we move left,we say that we
zig,and if we move right we say that we zag,A move of
two steps left (going down) is then called zig-zig,two
steps right zag-zag,left then right zig-zag,and right
then left zag-zig,If the length of the path is odd,either
a single zig move or a zag move occurs at the end.
Splay Rotations
Splay Rotations
? The zig-zag case is identical to that of an AVL double
rotation,and the zig case is identical to a single rotation.
? The zig-zig case is not the same as would be obtained
by lifting the target node twice with single rotations.
? Always think of lifting the target two levels at a time
(except for a single zig or zag step at the end).
? It is only the nodes on the path from the target to the
root whose relative positions are changed,and that
only in the ways shown by colored dashed curves in
the figures.
? None of the subtrees off the path (T1,T2,T3,and T4 )
changes its shape at all,and these subtrees are
attached to the path in the only places they can go to
maintain the search-tree ordering of all the keys.
Zig-Zig and Single Rotations
? A zig-zig movement is not the same as would be
obtained by lifting the target node twice with single
rotations.
Top-Down and Bottom-Up Splaying
? By hand,we perform bottom-up splaying,
beginning at the target node and moving up the path
to the root two steps at a time,A single zig or zag
move may occur at the top of the tree,Bottom-up
splaying is essentially a two-pass method,
first searching down the tree and then splaying the
target up to the root.
? In a computer algorithm,we splay from the top down
while we are searching for the target node,When we nd
the target,it is immediately moved to the root of the
tree,or,if the search is unsuccessful,a new root is
created that holds the target,In top-down splaying,a
single zig or zag move occurs at the bottom of the
splaying process.
?If you run the splaying function we develop on the
example trees,you will obtain the same results as
doing bottom-up splaying by hand when the target is
moved an even number of levels,but the results will be
different when it moves an odd number of levels.
Algorithm Development
? Given a target key,we develop a function that
searches down the tree for the key,splaying as it goes,
If it finds the key,then it retrieves it; if not,then the
function inserts it in a new node,In either case,the
node with the target key becomes the root of the tree.
? We implement splay trees as a derived class of class
Search tree.
这部分源代码可以复制给大家,splay tree比较灵活，有一
定的应用价值，由于时间关系，这部分不再细讲。
Pointers and Pitfalls
? Consider binary search trees as an alternative to
ordered lists,At the cost of an extra pointer eld in
each node,binary search trees allow random access
(with O(log n)key comparisons) to all nodes while
maintaining the flexibility of linked lists for insertions,
deletions,and rearrangement.
?Consider binary search trees as an alternative to
tables,At the cost of access time that is O(logn)
instead of O(1),binary search trees allow traversal of
the data structure in the order specified by the keys
while maintaining the advantage of random access
provided by tables.
? In choosing your data structures,always carefully
consider what operations will be required,Binary
trees are especially appropriate when the
requirements include random access,traversal in a
predetermined order,and flexibility in making
insertions and deletions.
? While choosing data structures and algorithms,
remain alert to the possibility of highly unbalanced
binary search trees,AVL trees provide nearly perfect
balance at a slight cost in computer time and space,
but with considerable programming cost,If it is
necessary for the tree to adapt dynamically to
changes in the frequency of the data,then a splay
tree may be the best choice.
? Binary trees are dened recursively; algorithms for
manipulating binary trees are usually,but not always,
best written recursively.
? Although binary trees are most commonly
implemented as linked structures,remain aware of
the possibility of other implementations.
