4.1 二叉搜索树

4.1.1 定义与抽象数据类型的基本操作

1.$\color{red}{定义：}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@</p> <blockquote> <p>一棵二叉树，可以为<strong>空</strong>；如果不为空，满足以下性质： <br> 1. 非空 <strong>左子树</strong> 的所有 <strong>键值小于其根结点</strong> 的键值。 <br> 2. 非空 <strong>右子树</strong> 的所有 <strong>键值大于其根结点</strong> 的键值。 <br> 3. <strong>左、右子树都是二叉<a href="/tag/sousuo/" target="_blank" class="keywords">搜索</a>树 。</strong></p> </blockquote> <p>2.<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-2-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-14" style="width: 7.043em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.603em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.389em 1000em 2.723em -0.477em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-15"><span class="mstyle" id="MathJax-Span-16" style="color: red;"><span class="mrow" id="MathJax-Span-17" style="color: red;"><span class="texatom" id="MathJax-Span-18" style="color: red;"><span class="mrow" id="MathJax-Span-19" style="color: red;"><span class="mo" id="MathJax-Span-20" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">抽</span></span></span></span><span class="texatom" id="MathJax-Span-21" style="color: red;"><span class="mrow" id="MathJax-Span-22" style="color: red;"><span class="mo" id="MathJax-Span-23" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">象</span></span></span></span><span class="texatom" id="MathJax-Span-24" style="color: red;"><span class="mrow" id="MathJax-Span-25" style="color: red;"><span class="mo" id="MathJax-Span-26" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">数</span></span></span></span><span class="texatom" id="MathJax-Span-27" style="color: red;"><span class="mrow" id="MathJax-Span-28" style="color: red;"><span class="mo" id="MathJax-Span-29" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">据</span></span></span></span><span class="texatom" id="MathJax-Span-30" style="color: red;"><span class="mrow" id="MathJax-Span-31" style="color: red;"><span class="mo" id="MathJax-Span-32" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">类</span></span></span></span><span class="texatom" id="MathJax-Span-33" style="color: red;"><span class="mrow" id="MathJax-Span-34" style="color: red;"><span class="mo" id="MathJax-Span-35" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">型</span></span></span></span><span class="texatom" id="MathJax-Span-36" style="color: red;"><span class="mrow" id="MathJax-Span-37" style="color: red;"><span class="mo" id="MathJax-Span-38" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">：</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-2">\color{red}{抽象数据类型：}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@</p> <blockquote> <p><strong>查找：</strong> <br> 1.1. <code>Position Find( ElementType X,BinTree BST )</code> ：从二叉<a href="/tag/sousuo/" target="_blank" class="keywords">搜索</a>树BST中查找元素X ，返回其所在结点的地址； <br> 1.2. <code>Position FindMin( BinTree BST )</code> ：从二叉<a href="/tag/sousuo/" target="_blank" class="keywords">搜索</a>树BST 中查找并返回最小元素所在结点的地址； <br> 1.3. <code>Position FindMax( BinTree BST )</code> ：从二叉<a href="/tag/sousuo/" target="_blank" class="keywords">搜索</a>树BST 中查找并返回最大元素所在结点的地址。</p> <p><strong>注：</strong> <br> 1. <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-3-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-39" style="width: 12.003em; display: inline-block;"><span style="display: inline-block; position: relative; width: 9.603em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.389em 1000em 2.723em -0.477em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-40"><span class="mstyle" id="MathJax-Span-41" style="color: red;"><span class="mrow" id="MathJax-Span-42" style="color: red;"><span class="texatom" id="MathJax-Span-43" style="color: red;"><span class="mrow" id="MathJax-Span-44" style="color: red;"><span class="mo" id="MathJax-Span-45" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">尾</span></span></span></span><span class="texatom" id="MathJax-Span-46" style="color: red;"><span class="mrow" id="MathJax-Span-47" style="color: red;"><span class="mo" id="MathJax-Span-48" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">递</span></span></span></span><span class="texatom" id="MathJax-Span-49" style="color: red;"><span class="mrow" id="MathJax-Span-50" style="color: red;"><span class="mo" id="MathJax-Span-51" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">归</span></span></span></span><span class="texatom" id="MathJax-Span-52" style="color: red;"><span class="mrow" id="MathJax-Span-53" style="color: red;"><span class="mo" id="MathJax-Span-54" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">都</span></span></span></span><span class="texatom" id="MathJax-Span-55" style="color: red;"><span class="mrow" id="MathJax-Span-56" style="color: red;"><span class="mo" id="MathJax-Span-57" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">可</span></span></span></span><span class="texatom" id="MathJax-Span-58" style="color: red;"><span class="mrow" id="MathJax-Span-59" style="color: red;"><span class="mo" id="MathJax-Span-60" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">以</span></span></span></span><span class="texatom" id="MathJax-Span-61" style="color: red;"><span class="mrow" id="MathJax-Span-62" style="color: red;"><span class="mo" id="MathJax-Span-63" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">用</span></span></span></span><span class="texatom" id="MathJax-Span-64" style="color: red;"><span class="mrow" id="MathJax-Span-65" style="color: red;"><span class="mo" id="MathJax-Span-66" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">循</span></span></span></span><span class="texatom" id="MathJax-Span-67" style="color: red;"><span class="mrow" id="MathJax-Span-68" style="color: red;"><span class="mo" id="MathJax-Span-69" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">环</span></span></span></span><span class="texatom" id="MathJax-Span-70" style="color: red;"><span class="mrow" id="MathJax-Span-71" style="color: red;"><span class="mo" id="MathJax-Span-72" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">实</span></span></span></span><span class="texatom" id="MathJax-Span-73" style="color: red;"><span class="mrow" id="MathJax-Span-74" style="color: red;"><span class="mo" id="MathJax-Span-75" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">现</span></span></span></span><span class="texatom" id="MathJax-Span-76" style="color: red;"><span class="mrow" id="MathJax-Span-77" style="color: red;"><span class="mo" id="MathJax-Span-78" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">！</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-3">\color{red}{尾递归都可以用循环实现！}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@ <br> 2. <strong>查找效率与树的高度有关！</strong></p> </blockquote> <p> <br> </p> <blockquote> <p><strong>插入与<a href="/tag/shanchu/" target="_blank" class="keywords">删除</a></strong> <br> 1. <code>BinTree Insert( ElementType X,BinTree BST )</code> <br> 2. <code>BinTree Delete( ElementType X,BinTree BST )</code> <br> <strong>注</strong>： <br> 1. 插入和<a href="/tag/shanchu/" target="_blank" class="keywords">删除</a>有三种情况： <br> - 没有左儿子和右儿子； <br> - 只有左儿子或者右儿子； <br> - 既有左儿子又有右儿子（选取右子树中最小的那个）。 <br> <br> </p> </blockquote> <h1 id="42-平衡二叉树">4.2 平衡二叉树</h1> <hr> <h2 id="421-定义和特点">4.2.1 定义和特点</h2> <p>1.<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-452-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-6809" style="width: 10.029em; display: inline-block;"><span style="display: inline-block; position: relative; width: 8.003em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.389em 1000em 2.723em -0.477em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6810"><span class="mstyle" id="MathJax-Span-6811" style="color: red;"><span class="mrow" id="MathJax-Span-6812" style="color: red;"><span class="texatom" id="MathJax-Span-6813" style="color: red;"><span class="mrow" id="MathJax-Span-6814" style="color: red;"><span class="mo" id="MathJax-Span-6815" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">平</span></span></span></span><span class="texatom" id="MathJax-Span-6816" style="color: red;"><span class="mrow" id="MathJax-Span-6817" style="color: red;"><span class="mo" id="MathJax-Span-6818" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">衡</span></span></span></span><span class="texatom" id="MathJax-Span-6819" style="color: red;"><span class="mrow" id="MathJax-Span-6820" style="color: red;"><span class="mo" id="MathJax-Span-6821" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">因</span></span></span></span><span class="texatom" id="MathJax-Span-6822" style="color: red;"><span class="mrow" id="MathJax-Span-6823" style="color: red;"><span class="mo" id="MathJax-Span-6824" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">子</span></span></span></span><span class="texatom" id="MathJax-Span-6825" style="color: red;"><span class="mrow" id="MathJax-Span-6826" style="color: red;"><span class="mo" id="MathJax-Span-6827" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">和</span></span></span></span><span class="texatom" id="MathJax-Span-6828" style="color: red;"><span class="mrow" id="MathJax-Span-6829" style="color: red;"><span class="mo" id="MathJax-Span-6830" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">平</span></span></span></span><span class="texatom" id="MathJax-Span-6831" style="color: red;"><span class="mrow" id="MathJax-Span-6832" style="color: red;"><span class="mo" id="MathJax-Span-6833" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">衡</span></span></span></span><span class="texatom" id="MathJax-Span-6834" style="color: red;"><span class="mrow" id="MathJax-Span-6835" style="color: red;"><span class="mo" id="MathJax-Span-6836" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">二</span></span></span></span><span class="texatom" id="MathJax-Span-6837" style="color: red;">@H_343_<a href="/tag/403/" target="_blank" class="keywords">403</a>@@H_567_<a href="/tag/404/" target="_blank" class="keywords">404</a>@<span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">叉</span></span></span></span><span class="texatom" id="MathJax-Span-6840" style="color: red;"><span class="mrow" id="MathJax-Span-6841" style="color: red;"><span class="mo" id="MathJax-Span-6842" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">树</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-452">\color{red}{平衡因子和平衡二叉树}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@</p> <blockquote> <p><strong>平衡因子定义</strong>： <br> <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-453-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-6843" style="width: 4.003em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.203em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.389em 1000em 2.723em -0.477em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6844"><span class="mstyle" id="MathJax-Span-6845" style="color: red;"><span class="mrow" id="MathJax-Span-6846" style="color: red;"><span class="texatom" id="MathJax-Span-6847" style="color: red;"><span class="mrow" id="MathJax-Span-6848" style="color: red;"><span class="mo" id="MathJax-Span-6849" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">平</span></span></span></span><span class="texatom" id="MathJax-Span-6850" style="color: red;"><span class="mrow" id="MathJax-Span-6851" style="color: red;"><span class="mo" id="MathJax-Span-6852" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">衡</span></span></span></span><span class="texatom" id="MathJax-Span-6853" style="color: red;"><span class="mrow" id="MathJax-Span-6854" style="color: red;"><span class="mo" id="MathJax-Span-6855" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">因</span></span></span></span><span class="texatom" id="MathJax-Span-6856" style="color: red;"><span class="mrow" id="MathJax-Span-6857" style="color: red;"><span class="mo" id="MathJax-Span-6858" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">子</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-453">\color{red}{平衡因子}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@（Balance Factor，简称BF）: <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-454-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-6859" style="width: 9.763em; display: inline-block;"><span style="display: inline-block; position: relative; width: 7.789em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.816em 1000em 3.149em -0.424em); top: -2.717em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6860">@H_969_<a href="/tag/502/" target="_blank" class="keywords">502</a>@B</span><span class="mi" id="MathJax-Span-6862" style="font-family: MathJax_Math-italic;">F<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.109em;"></span></span><span class="mo" id="MathJax-Span-6863" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-6864" style="font-family: MathJax_Math-italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.109em;"></span></span><span class="mo" id="MathJax-Span-6865" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-6866" style="font-family: MathJax_Main; padding-left: 0.269em;">=</span><span class="msubsup" id="MathJax-Span-6867" style="padding-left: 0.269em;"><span style="display: inline-block; position: relative; width: 1.123em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-6868" style="font-family: MathJax_Math-italic;">h</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.589em;"><span class="mi" id="MathJax-Span-6869" style="font-size: 70.7%; font-family: MathJax_Math-italic;">L</span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span><span class="mo" id="MathJax-Span-6870" style="font-family: MathJax_Main; padding-left: 0.216em;">−</span><span class="msubsup" id="MathJax-Span-6871" style="padding-left: 0.216em;"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-6872" style="font-family: MathJax_Math-italic;">h</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.589em;"><span class="mi" id="MathJax-Span-6873" style="font-size: 70.7%; font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.723em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.397em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-454">BF(T) = h_L -h_R@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@其中<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-455-Frame" role="textbox" aria-readonly="true"> <nobr> @H_<a href="/tag/301/" target="_blank" class="keywords">301</a>_568@<span style="display: inline-block; position: relative; width: 1.123em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.496em 1000em 2.669em -0.424em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6875"><span class="msubsup" id="MathJax-Span-6876"><span style="display: inline-block; position: relative; width: 1.123em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-6877" style="font-family: MathJax_Math-italic;">h</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.589em;"><span class="mi" id="MathJax-Span-6878" style="font-size: 70.7%; font-family: MathJax_Math-italic;">L</span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.203em; vertical-align: -0.263em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-455">h_L@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@ 和<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-456-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-6879" style="width: 1.496em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.496em 1000em 2.669em -0.424em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6880"><span class="msubsup" id="MathJax-Span-6881"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-6882" style="font-family: MathJax_Math-italic;">h</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.589em;"><span class="mi" id="MathJax-Span-6883" style="font-size: 70.7%; font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.203em; vertical-align: -0.263em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-456">h_R@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@ 分别为<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-457-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-6884" style="width: 0.909em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.696em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.477em); top: -2.557em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6885"><span class="mi" id="MathJax-Span-6886" style="font-family: MathJax_Math-italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.109em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.003em; vertical-align: -0.063em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-457">T@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@<strong>左、右子树的高度</strong>。</p> <hr> <p><strong>平衡二叉树的定义</strong>： <br> <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-458-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-6887" style="width: 5.016em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.003em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.389em 1000em 2.723em -0.477em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6888"><span class="mstyle" id="MathJax-Span-6889" style="color: red;"><span class="mrow" id="MathJax-Span-6890" style="color: red;"><span class="texatom" id="MathJax-Span-6891" style="color: red;"><span class="mrow" id="MathJax-Span-6892" style="color: red;"><span class="mo" id="MathJax-Span-6893" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">平</span></span></span></span><span class="texatom" id="MathJax-Span-6894" style="color: red;"><span class="mrow" id="MathJax-Span-6895" style="color: red;"><span class="mo" id="MathJax-Span-6896" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">衡</span></span></span></span><span class="texatom" id="MathJax-Span-6897" style="color: red;"><span class="mrow" id="MathJax-Span-6898" style="color: red;"><span class="mo" id="MathJax-Span-6899" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">二</span></span></span></span><span class="texatom" id="MathJax-Span-6900" style="color: red;"><span class="mrow" id="MathJax-Span-6901" style="color: red;"><span class="mo" id="MathJax-Span-6902" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">叉</span></span></span></span><span class="texatom" id="MathJax-Span-6903" style="color: red;"><span class="mrow" id="MathJax-Span-6904" style="color: red;"><span class="mo" id="MathJax-Span-6905" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">树</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-458">\color{red}{平衡二叉树}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@(Balanced Binary Tree)（AVL)： <br> <strong>空树</strong>，或者<strong>任一结点</strong>左、右子树<strong>高度差的绝对值</strong>不超过1 ，即<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-459-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-6906" style="width: 6.669em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.336em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.816em 1000em 3.149em -0.371em); top: -2.717em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6907"><span class="texatom" id="MathJax-Span-6908"><span class="mrow" id="MathJax-Span-6909"><span class="mo" id="MathJax-Span-6910" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-6911" style="font-family: MathJax_Math-italic;">B</span><span class="mi" id="MathJax-Span-6912" style="font-family: MathJax_Math-italic;">F<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.109em;"></span></span><span class="mo" id="MathJax-Span-6913" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-6914" style="font-family: MathJax_Math-italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.109em;"></span></span><span class="mo" id="MathJax-Span-6915" style="font-family: MathJax_Main;">)</span><span class="texatom" id="MathJax-Span-6916"><span class="mrow" id="MathJax-Span-6917"><span class="mo" id="MathJax-Span-6918" style="font-family: MathJax_Main;">|</span></span></span><span class="mo" id="MathJax-Span-6919" style="font-family: MathJax_Main; padding-left: 0.269em;">≤</span><span class="mn" id="MathJax-Span-6920" style="font-family: MathJax_Main; padding-left: 0.269em;">1</span></span><span style="display: inline-block; width: 0px; height: 2.723em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.397em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-459">|BF(T) |≤ 1@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@。</p> </blockquote> <p>2.<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-460-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-6921" style="width: 7.043em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.603em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.389em 1000em 2.723em -0.477em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-6922"><span class="mstyle" id="MathJax-Span-6923" style="color: red;"><span class="mrow" id="MathJax-Span-6924" style="color: red;"><span class="texatom" id="MathJax-Span-6925" style="color: red;"><span class="mrow" id="MathJax-Span-6926" style="color: red;"><span class="mo" id="MathJax-Span-6927" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">平</span></span></span></span><span class="texatom" id="MathJax-Span-6928" style="color: red;"><span class="mrow" id="MathJax-Span-6929" style="color: red;"><span class="mo" id="MathJax-Span-6930" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">衡</span></span></span></span><span class="texatom" id="MathJax-Span-6931" style="color: red;"><span class="mrow" id="MathJax-Span-6932" style="color: red;"><span class="mo" id="MathJax-Span-6933" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">因</span></span></span></span><span class="texatom" id="MathJax-Span-6934" style="color: red;"><span class="mrow" id="MathJax-Span-6935" style="color: red;"><span class="mo" id="MathJax-Span-6936" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">子</span></span></span></span><span class="texatom" id="MathJax-Span-6937" style="color: red;"><span class="mrow" id="MathJax-Span-6938" style="color: red;"><span class="mo" id="MathJax-Span-6939" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">的</span></span></span></span><span class="texatom" id="MathJax-Span-6940" style="color: red;"><span class="mrow" id="MathJax-Span-6941" style="color: red;"><span class="mo" id="MathJax-Span-6942" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">高</span></span></span></span><span class="texatom" id="MathJax-Span-6943" style="color: red;"><span class="mrow" id="MathJax-Span-6944" style="color: red;"><span class="mo" id="MathJax-Span-6945" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">度</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-460">\color{red}{平衡因子的高度}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@ <br> </p> <hr> <h2 id="422-平衡二叉树的调整">4.2.2 平衡二叉树的调整</h2> <hr> <p><strong>整体思路：</strong> <br> <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-667-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-16353" style="width: 42.509em; display: inline-block;"><span style="display: inline-block; position: relative; width: 33.976em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.763em 1000em 3.096em -0.477em); top: -2.717em; left: 0.003em;"><span class="mrow" id="MathJax-Span-16354"><span class="mstyle" id="MathJax-Span-16355" style="color: red;"><span class="mrow" id="MathJax-Span-16356" style="color: red;"><span class="texatom" id="MathJax-Span-16357" style="color: red;"><span class="mrow" id="MathJax-Span-16358" style="color: red;"><span class="mo" id="MathJax-Span-16359" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">发</span></span></span></span><span class="texatom" id="MathJax-Span-16360" style="color: red;"><span class="mrow" id="MathJax-Span-16361" style="color: red;"><span class="mo" id="MathJax-Span-16362" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">现</span></span></span></span><span class="mo" id="MathJax-Span-16363" style="font-family: MathJax_Main; color: red;">“</span><span class="texatom" id="MathJax-Span-16364" style="color: red;"><span class="mrow" id="MathJax-Span-16365" style="color: red;"><span class="mo" id="MathJax-Span-16366" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">麻</span></span></span></span><span class="texatom" id="MathJax-Span-16367" style="color: red;"><span class="mrow" id="MathJax-Span-16368" style="color: red;"><span class="mo" id="MathJax-Span-16369" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">烦</span></span></span></span><span class="texatom" id="MathJax-Span-16370" style="color: red;"><span class="mrow" id="MathJax-Span-16371" style="color: red;"><span class="mo" id="MathJax-Span-16372" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">节</span></span></span></span><span class="texatom" id="MathJax-Span-16373" style="color: red;"><span class="mrow" id="MathJax-Span-16374" style="color: red;"><span class="mo" id="MathJax-Span-16375" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">点</span></span></span></span><span class="mo" id="MathJax-Span-16376" style="font-family: MathJax_Main; color: red;">”</span><span class="texatom" id="MathJax-Span-16377" style="color: red;"><span class="mrow" id="MathJax-Span-16378" style="color: red;"><span class="mo" id="MathJax-Span-16379" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">，</span></span></span></span><span class="texatom" id="MathJax-Span-16380" style="color: red;"><span class="mrow" id="MathJax-Span-16381" style="color: red;"><span class="mo" id="MathJax-Span-16382" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">寻</span></span></span></span><span class="texatom" id="MathJax-Span-16383" style="color: red;"><span class="mrow" id="MathJax-Span-16384" style="color: red;"><span class="mo" id="MathJax-Span-16385" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">找</span></span></span></span><span class="texatom" id="MathJax-Span-16386" style="color: red;"><span class="mrow" id="MathJax-Span-16387" style="color: red;"><span class="mo" id="MathJax-Span-16388" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">麻</span></span></span></span><span class="texatom" id="MathJax-Span-16389" style="color: red;"><span class="mrow" id="MathJax-Span-16390" style="color: red;"><span class="mo" id="MathJax-Span-16391" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">烦</span></span></span></span><span class="texatom" id="MathJax-Span-16392" style="color: red;"><span class="mrow" id="MathJax-Span-16393" style="color: red;"><span class="mo" id="MathJax-Span-16394" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">节</span></span></span></span><span class="texatom" id="MathJax-Span-16395" style="color: red;"><span class="mrow" id="MathJax-Span-16396" style="color: red;"><span class="mo" id="MathJax-Span-16397" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">点</span></span></span></span><span class="texatom" id="MathJax-Span-16398" style="color: red;"><span class="mrow" id="MathJax-Span-16399" style="color: red;"><span class="mo" id="MathJax-Span-16400" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">的</span></span></span></span><span class="texatom" id="MathJax-Span-16401" style="color: red;"><span class="mrow" id="MathJax-Span-16402" style="color: red;"><span class="mo" id="MathJax-Span-16403" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">的</span></span></span></span><span class="texatom" id="MathJax-Span-16404" style="color: red;"><span class="mrow" id="MathJax-Span-16405" style="color: red;"><span class="mo" id="MathJax-Span-16406" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">原</span></span></span></span><span class="texatom" id="MathJax-Span-16407" style="color: red;"><span class="mrow" id="MathJax-Span-16408" style="color: red;"><span class="mo" id="MathJax-Span-16409" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">因</span></span></span></span><span class="texatom" id="MathJax-Span-16410" style="color: red;"><span class="mrow" id="MathJax-Span-16411" style="color: red;"><span class="mo" id="MathJax-Span-16412" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">（</span></span></span></span><span class="mi" id="MathJax-Span-16413" style="font-family: MathJax_Math-italic; color: red;">R</span><span class="mi" id="MathJax-Span-16414" style="font-family: MathJax_Math-italic; color: red;">R</span><span class="texatom" id="MathJax-Span-16415" style="color: red;"><span class="mrow" id="MathJax-Span-16416" style="color: red;"><span class="mo" id="MathJax-Span-16417" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">、</span></span></span></span><span class="mi" id="MathJax-Span-16418" style="font-family: MathJax_Math-italic; color: red;">L</span><span class="mi" id="MathJax-Span-16419" style="font-family: MathJax_Math-italic; color: red;">R</span><span class="texatom" id="MathJax-Span-16420" style="color: red;"><span class="mrow" id="MathJax-Span-16421" style="color: red;"><span class="mo" id="MathJax-Span-16422" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">、</span></span></span></span><span class="mi" id="MathJax-Span-16423" style="font-family: MathJax_Math-italic; color: red;">L</span><span class="mi" id="MathJax-Span-16424" style="font-family: MathJax_Math-italic; color: red;">L</span><span class="texatom" id="MathJax-Span-16425" style="color: red;"><span class="mrow" id="MathJax-Span-16426" style="color: red;"><span class="mo" id="MathJax-Span-16427" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">、</span></span></span></span><span class="mi" id="MathJax-Span-16428" style="font-family: MathJax_Math-italic; color: red;">R</span><span class="mi" id="MathJax-Span-16429" style="font-family: MathJax_Math-italic; color: red;">L</span><span class="texatom" id="MathJax-Span-16430" style="color: red;"><span class="mrow" id="MathJax-Span-16431" style="color: red;"><span class="mo" id="MathJax-Span-16432" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">）</span></span></span></span><span class="texatom" id="MathJax-Span-16433" style="color: red;"><span class="mrow" id="MathJax-Span-16434" style="color: red;"><span class="mo" id="MathJax-Span-16435" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">，</span></span></span></span><span class="texatom" id="MathJax-Span-16436" style="color: red;"><span class="mrow" id="MathJax-Span-16437" style="color: red;"><span class="mo" id="MathJax-Span-16438" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">最</span></span></span></span><span class="texatom" id="MathJax-Span-16439" style="color: red;"><span class="mrow" id="MathJax-Span-16440" style="color: red;"><span class="mo" id="MathJax-Span-16441" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">后</span></span></span></span><span class="texatom" id="MathJax-Span-16442" style="color: red;"><span class="mrow" id="MathJax-Span-16443" style="color: red;"><span class="mo" id="MathJax-Span-16444" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">根</span></span></span></span><span class="texatom" id="MathJax-Span-16445" style="color: red;"><span class="mrow" id="MathJax-Span-16446" style="color: red;"><span class="mo" id="MathJax-Span-16447" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">据</span></span></span></span><span class="texatom" id="MathJax-Span-16448" style="color: red;"><span class="mrow" id="MathJax-Span-16449" style="color: red;"><span class="mo" id="MathJax-Span-16450" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">原</span></span></span></span><span class="texatom" id="MathJax-Span-16451" style="color: red;"><span class="mrow" id="MathJax-Span-16452" style="color: red;"><span class="mo" id="MathJax-Span-16453" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">因</span></span></span></span><span class="texatom" id="MathJax-Span-16454" style="color: red;"><span class="mrow" id="MathJax-Span-16455" style="color: red;"><span class="mo" id="MathJax-Span-16456" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">进</span></span></span></span><span class="texatom" id="MathJax-Span-16457" style="color: red;"><span class="mrow" id="MathJax-Span-16458" style="color: red;"><span class="mo" id="MathJax-Span-16459" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">行</span></span></span></span><span class="texatom" id="MathJax-Span-16460" style="color: red;"><span class="mrow" id="MathJax-Span-16461" style="color: red;"><span class="mo" id="MathJax-Span-16462" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">求</span></span></span></span><span class="texatom" id="MathJax-Span-16463" style="color: red;"><span class="mrow" id="MathJax-Span-16464" style="color: red;"><span class="mo" id="MathJax-Span-16465" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">解</span></span></span></span><span class="texatom" id="MathJax-Span-16466" style="color: red;"><span class="mrow" id="MathJax-Span-16467" style="color: red;"><span class="mo" id="MathJax-Span-16468" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">。</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.723em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-667">\color{red}{发现“麻烦节点”，寻找麻烦节点的的原因（RR、LR、LL、RL），最后根据原因进行求解。}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@</p> <ol> <li><p><span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-668-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-16469" style="width: 3.896em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.096em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.603em 1000em 2.936em -0.424em); top: -2.557em; left: 0.003em;"><span class="mrow" id="MathJax-Span-16470"><span class="mstyle" id="MathJax-Span-16471" style="color: red;"><span class="mrow" id="MathJax-Span-16472" style="color: red;"><span class="mi" id="MathJax-Span-16473" style="font-family: MathJax_Math-italic; color: red;">R</span><span class="mi" id="MathJax-Span-16474" style="font-family: MathJax_Math-italic; color: red;">R</span><span class="texatom" id="MathJax-Span-16475" style="color: red;"><span class="mrow" id="MathJax-Span-16476" style="color: red;"><span class="mo" id="MathJax-Span-16477" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">旋</span></span></span></span><span class="texatom" id="MathJax-Span-16478" style="color: red;"><span class="mrow" id="MathJax-Span-16479" style="color: red;"><span class="mo" id="MathJax-Span-16480" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">转</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-668">\color{red}{RR旋转}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@ <br> </p></li> <li><p><span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-669-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-16481" style="width: 3.736em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.989em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.603em 1000em 2.936em -0.424em); top: -2.557em; left: 0.003em;"><span class="mrow" id="MathJax-Span-16482"><span class="mstyle" id="MathJax-Span-16483" style="color: red;"><span class="mrow" id="MathJax-Span-16484" style="color: red;"><span class="mi" id="MathJax-Span-16485" style="font-family: MathJax_Math-italic; color: red;">L</span><span class="mi" id="MathJax-Span-16486" style="font-family: MathJax_Math-italic; color: red;">L</span><span class="texatom" id="MathJax-Span-16487" style="color: red;"><span class="mrow" id="MathJax-Span-16488" style="color: red;"><span class="mo" id="MathJax-Span-16489" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">旋</span></span></span></span><span class="texatom" id="MathJax-Span-16490" style="color: red;"><span class="mrow" id="MathJax-Span-16491" style="color: red;"><span class="mo" id="MathJax-Span-16492" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">转</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-669">\color{red}{LL旋转}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@ <br> </p></li> <li><p><span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-670-Frame" role="textbox" aria-readonly="true"> <nobr> <span class="math" id="MathJax-Span-16493" style="width: 3.843em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.043em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.603em 1000em 2.936em -0.424em); top: -2.557em; left: 0.003em;"><span class="mrow" id="MathJax-Span-16494"><span class="mstyle" id="MathJax-Span-16495" style="color: red;"><span class="mrow" id="MathJax-Span-16496" style="color: red;"><span class="mi" id="MathJax-Span-16497" style="font-family: MathJax_Math-italic; color: red;">L</span><span class="mi" id="MathJax-Span-16498" style="font-family: MathJax_Math-italic; color: red;">R</span><span class="texatom" id="MathJax-Span-16499" style="color: red;"><span class="mrow" id="MathJax-Span-16500" style="color: red;"><span class="mo" id="MathJax-Span-16501" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">旋</span></span></span></span><span class="texatom" id="MathJax-Span-16502" style="color: red;"><span class="mrow" id="MathJax-Span-16503" style="color: red;"><span class="mo" id="MathJax-Span-16504" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">转</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-670">\color{red}{LR旋转}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@ <br> </p></li> <li><p><span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-671-Frame" role="textbox" aria-readonly="true"> <nobr> @H_<a href="/tag/502/" target="_blank" class="keywords">502</a>_1353@<span style="display: inline-block; position: relative; width: 3.043em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.603em 1000em 2.936em -0.424em); top: -2.557em; left: 0.003em;"><span class="mrow" id="MathJax-Span-16506"><span class="mstyle" id="MathJax-Span-16507" style="color: red;"><span class="mrow" id="MathJax-Span-16508" style="color: red;"><span class="mi" id="MathJax-Span-16509" style="font-family: MathJax_Math-italic; color: red;">R</span><span class="mi" id="MathJax-Span-16510" style="font-family: MathJax_Math-italic; color: red;">L</span><span class="texatom" id="MathJax-Span-16511" style="color: red;"><span class="mrow" id="MathJax-Span-16512" style="color: red;"><span class="mo" id="MathJax-Span-16513" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">旋</span></span></span></span><span class="texatom" id="MathJax-Span-16514" style="color: red;"><span class="mrow" id="MathJax-Span-16515" style="color: red;"><span class="mo" id="MathJax-Span-16516" style="color: red;"><span style="font-family: STIXGeneral,serif; font-size: 80%; font-style: normal; font-weight: normal;">转</span></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span></span><span style="border-left: 0.003em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.403em; vertical-align: -0.33em;"></span></span> </nobr></span><script type="math/tex" id="MathJax-Element-671">\color{red}{RL旋转}@H_<a href="/tag/403/" target="_blank" class="keywords">403</a>_52@ <br> </p></li> </ol> <hr> <h1 id="43">4.3</h1></div> <div class="topcard-tags"></div> <ul class="list-group"> <li class="list-group-item"><a href="/datastructure/382272.html" title="【数据结构】线性结构——判空">上一篇：【数据结构】线性结构——判空</a><a href="/datastructure/382270.html" title="【数据结构】：AVL树" class="text-muted pull-right">下一篇：【数据结构】：AVL树</a> </li> </ul> </div> </div> </div> <!-- row end --> <div class="row row-sm"> <div class="col-sm-12 col-md-12 col-lg-12"> <div class="card"> <ins class="adsbygoogle" style="display:block" data-ad-format="autorelaxed" data-ad-client="ca-pub-4605373693034661" data-ad-slot="9144498553"></ins> <script> (adsbygoogle = window.adsbygoogle || []).push({});$