📄 page350.html
字号:
<HTML><HEAD><TITLE>Projects</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5216" HREF="page351.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5214" HREF="page298.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5210" HREF="page349.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5218" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION00101000000000000000000">Projects</A></H1><P><OL><LI> <A NAME="projectsrchtreebst"> </A> Complete the implementation of the <tt>BinarySearchTree</tt> class introduced in Program <A HREF="page311.html#progbinarySearchTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by providing suitable definitions for the following operations: <tt>__contains__</tt> and <tt>getMax</tt>. You must also have a complete implementation of the base class <tt>BinaryTree</tt>. (See Project <A HREF="page297.html#projecttreesbintree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>). Write a test program and test your implementation.<LI> Complete the implementation of the <tt>AVLTree</tt> class introduced in Program <A HREF="page320.html#progavlTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by providing suitable definitions for the following operations: <tt>doRRRotation</tt>, and <tt>doRLRotation</tt>. You must also have a complete implementation of the base class <tt>BinarySearchTree</tt>. (See Project <A HREF="page350.html#projectsrchtreebst"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>). Write a test program and test your implementation.<LI> <A NAME="projectsrchtreemwaytree"> </A> Complete the implementation of the <tt>MWayTree</tt> class introduced in Program <A HREF="page332.html#progmWayTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by providing suitable definitions for the following operations: <tt>purge</tt>, <tt>getCount</tt>, <tt>getIsEmpty</tt>, <tt>getIsLeaf</tt>, <tt>getDegree</tt>, <tt>getKey</tt>, <tt>getSubtree</tt>, <tt>__contains__</tt>, <tt>getMin</tt>, <tt>getMax</tt>, <tt>breadthFirstTraversal</tt>, and <tt>__iter__</tt>. Write a test program and test your implementation.<LI> Complete the implementation of the <tt>BTree</tt> class introduced in Program <A HREF="page341.html#progbTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by providing suitable definitions for the following methods: <tt>insertKey</tt>, <tt>insertSubtree</tt>, <tt>attachLeftHalfOf</tt>, <tt>attachRightHalfOf</tt>, and <tt>withdraw</tt>. You must also have a complete implementation of the base class <tt>MWayTree</tt>. (See Project <A HREF="page350.html#projectsrchtreemwaytree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>). Write a test program and test your implementation.<LI> The binary search tree <tt>withdraw</tt> method shown in Program <A HREF="page318.html#progbinarySearchTreed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is biased in the following way: If the key to be deleted is in a non-leaf node with two non-empty subtrees, the key is swapped with the maximum key in the left subtree and then recursively deleted from the left subtree. Following a long series of insertions and deletions, the search tree will tend to have more nodes in the right subtrees and fewer nodes in the left subtrees. Devise and conduct an experiment that demonstrates this phenomenon.<LI> Consider the implementation of AVL trees. In order to check the AVL balance condition in constant time, we record in each node the height of that node. An alternative to keeping track of the height information explicitly is to record in each node the <em>difference</em> in the heights of its two subtrees. In an AVL balanced tree, this difference is either -1, 0 or +1. Replace the <tt>_height</tt> instance attribute of the AVL class defined in Program <A HREF="page320.html#progavlTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> with one called <tt>_diff</tt> and rewrite the various methods accordingly.<LI> The <I>M</I>-way tree implementation given in Section <A HREF="page331.html#secsrchtreemwayimpl"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is an <em>internal</em> data structure--it is assumed that all the nodes reside in the main memory. However, the motivation for using an <I>M</I>-way tree is that it is an efficient way to organize an <em>external</em> data structure--one that is stored on disk. Design, implement and test an external <I>M</I>-way tree implementation.</OL><P><HR><A NAME="tex2html5216" HREF="page351.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5214" HREF="page298.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5210" HREF="page349.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5218" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -