📄 unbalanced.html

📁 Data Structure Ebook

💻 HTML

字号:

<HTML><HEAD>
<TITLE>Data Structures and Algorithms: Unbalanced Trees</TITLE>

<META name="description" content="Data Structures and Algorithms Course Notes,
PLDS210 University of Western Australia">
<META name="keywords" content="data structures,algorithms,abstract data types,
trees">
</HEAD>
<BODY BGCOLOR="#ffffff">
<TABLE BGCOLOR="#00c0f0" WIDTH="100%" CELLSPACING=0 CELLPADDING=0>
<TR BGCOLOR="#00f0f0"><TD ALIGN=right>
<FONT FACE=helvetica SIZE=+1><I>Data Structures and Algorithms</I></FONT>
</TD></TR>

<TR><TD><FONT FACE=helvetica SIZE=+2><B>Unbalanced Trees</B></FONT>
</TD></TR>
</TABLE>
<P>

If items are added to a binary tree <I>in order</I>
then the following <FONT COLOR="#fa0000"><B>unbalanced tree</B></FONT>
results:
<CENTER>
<IMG SRC="unbal_tree.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/unbal_tree.gif">
</CENTER>.
The <B>worst case</B> search of this tree may require up to 
<B><I>n</I></B> comparisons.
Thus a binary tree's worst case searching time is 
<B><I>O(n)</I></B>.
Later, we will look at <A HREF="red_black.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/red_black.html">red-black trees</A>,
which provide us with a strategy for avoiding this 
pathological behaviour.

<P>
<TABLE WIDTH="100%" BGCOLOR="#00c0f0">
<TR><TD><H3>Key terms</H3></TD></TR></TABLE>
<DL>
<DT><FONT COLOR="#fa0000"><B>Balanced Binary Tree</B></FONT>
   <DD>Binary tree in which each leaf is the same distance from the
root.
</DL>

<P>

<TABLE CELLPADDING=5 WIDTH="100%" BGCOLOR="#00f0f0" CELLSPACING=0>
<TR><TD>
Back to <A HREF="trees.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/trees.html">Trees</A><BR>
Back to the <A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
</TD></TR></TABLE>
<SMALL>
&copy; <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1998
</SMALL>
</BODY>
</HTML>

⌨️ 快捷键说明

复制代码 Ctrl + C

搜索代码 Ctrl + F

全屏模式 F11

切换主题 Ctrl + Shift + D

显示快捷键 ?

增大字号 Ctrl + =

减小字号 Ctrl + -