AVL树 ゝ一纸荒年。 2022-06-18 12:27 156阅读 0赞 **1. 概述** AVL树是最早提出的自平衡二叉树，在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis。AVL树种查找、插入和删除在平均和最坏情况下都是O（log n），增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。本文介绍了AVL树的设计思想和基本操作。 2. 基本术语 有四种种情况可能导致二叉查找树不平衡，分别为： （1）LL：插入一个新节点到根节点的左子树（Left）的左子树（Left），导致根节点的平衡因子由1变为2 （2）RR：插入一个新节点到根节点的右子树（Right）的右子树（Right），导致根节点的平衡因子由-1变为-2 （3）LR：插入一个新节点到根节点的左子树（Left）的右子树（Right），导致根节点的平衡因子由1变为2 （4）RL：插入一个新节点到根节点的右子树（Right）的左子树（Left），导致根节点的平衡因子由-1变为-2 针对四种种情况可能导致的不平衡，可以通过旋转使之变平衡。有两种基本的旋转： （1）左旋转：将根节点旋转到（根节点的）右孩子的左孩子位置 （2）右旋转：将根节点旋转到（根节点的）左孩子的右孩子位置 3. AVL树的旋转操作 AVL树的基本操作是旋转，有四种旋转方式，分别为：左旋转，右旋转，左右旋转（先左后右），右左旋转（先右后左），实际上，这四种旋转操作两两对称，因而也可以说成两类旋转操作。 基本的数据结构： <table style="width:660px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <tbody style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <tr style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <td style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; color:rgb(175,175,175)!important"> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">1</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">2</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">3</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">4</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">5</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">6</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">7</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">8</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">9</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">10</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">11</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">12</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">13</span> </div> </td> <td style="width:626.364px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">typedef</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important"> struct</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> Node* Tree;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">typedef</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important"> struct</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> Node* Node_t;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">typedef</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> Type </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:gray!important">int</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"> </span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">struct</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> Node{ </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">Node_t left;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">Node_t right;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:gray!important">int</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> height;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">Type data;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">};</span></code> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:gray!important">int</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> Height(Node_t node) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">return</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> node->height;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">}</span></code> </div> </div> </td> </tr> </tbody> </table> 3.1 LL LL情况需要右旋解决，如下图所示： ![LL][] 代码为： <table style="width:660px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <tbody style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <tr style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <td style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; color:rgb(175,175,175)!important"> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">1</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">2</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">3</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">4</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">5</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">6</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">7</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">8</span> </div> </td> <td style="width:632.727px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">Node_t RightRotate(Node_t a) { </span></code> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">b = a->left;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">a->left = b->right;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">b->right = a;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">a->height = Max(Height(a->left), Height(a->right));</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">b->height = Max(Height(b->left), Height(b->right));</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">return</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> b;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">}</span></code> </div> </div> </td> </tr> </tbody> </table> 3.2 RR RR情况需要左旋解决，如下图所示： ![RR][] 代码为： <table style="width:660px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <tbody style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <tr style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <td style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; color:rgb(175,175,175)!important"> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">1</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">2</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">3</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">4</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">5</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">6</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">7</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">8</span> </div> </td> <td style="width:632.727px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">Node_t LeftRotate(Node_t a) { </span></code> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">b = a->right;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">a->right = b->left;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">b->left = a;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">a->height = Max(Height(a->left), Height(a->right));</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">b->height = Max(Height(b->left), Height(b->right));</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">return</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> b;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">}</span></code> </div> </div> </td> </tr> </tbody> </table> 3.3 LR LR情况需要左右（先B左旋转，后A右旋转）旋解决，如下图所示： ![LR][] 代码为： <table style="width:660px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <tbody style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <tr style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <td style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; color:rgb(175,175,175)!important"> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">1</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">2</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">3</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">4</span> </div> </td> <td style="width:632.727px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">Node_t LeftRightRotate(Node_t a) { </span></code> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">a->left = LeftRotate(a->left);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">return</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> RightRotate(a);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">}</span></code> </div> </div> </td> </tr> </tbody> </table> 3.4 RL RL情况需要右左旋解决（先B右旋转，后A左旋转），如下图所示： ![RL][] 代码为： <table style="width:660px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <tbody style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <tr style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <td style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; color:rgb(175,175,175)!important"> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">1</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">2</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">3</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">4</span> </div> </td> <td style="width:632.727px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">Node_t RightLeftRotate(Node_t a) { </span></code> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">a->right = RightRotate(a->right);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">return</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> LeftRotate(a);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">}</span></code> </div> </div> </td> </tr> </tbody> </table> 4. AVL数的插入和删除操作 (1) 插入操作：实际上就是在不同情况下采用不同的旋转方式调整整棵树，具体代码如下： <table style="width:660px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <tbody style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <tr style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <td style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; color:rgb(175,175,175)!important"> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">1</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">2</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">3</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">4</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">5</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">6</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">7</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">8</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">9</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">10</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">11</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">12</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">13</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">14</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">15</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">16</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">17</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">18</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">19</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">20</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">21</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">22</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">23</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">24</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">25</span> </div> </td> <td style="width:626.364px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">Node_t Insert(Type x, Tree t) { </span></code> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(t == NULL) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t = NewNode(x);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">} </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">else</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important"> if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(x < t->data) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t->left = Insert(t->left);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(Height(t->left) - Height(t->right) == 2) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(x < t->left->data) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t = RightRotate(t);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">} </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">else</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t = LeftRightRotate(t);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">}</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">}</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">} </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">else</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t->right = Insert(t->right);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(Height(t->right) - Height(t->left) == 2) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(x > t->right->data) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t = LeftRotate(t);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">} </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">else</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t = RightLeftRotate(t);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">}</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">}</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">}</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t->height = Max(Height(t->left), Height(t->right)) + 1;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">return</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> t;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">}</span></code> </div> </div> </td> </tr> </tbody> </table> (2) 删除操作：首先定位要删除的节点，然后用该节点的右孩子的最左孩子替换该节点，并重新调整以该节点为根的子树为AVL树，具体调整方法跟插入数据类似，代码如下： <table style="width:660px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <tbody style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <tr style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <td style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; color:rgb(175,175,175)!important"> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">1</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">2</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">3</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">4</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">5</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">6</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">7</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">8</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">9</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">10</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">11</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">12</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">13</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">14</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">15</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">16</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">17</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">18</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">19</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">20</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">21</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">22</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">23</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">24</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">25</span> </div> <div style="margin:0px!important; padding:0px 0.5em 0px 1em!important; border-width:0px 3px 0px 0px!important; border-top-style:initial!important; border-right-style:solid!important; border-bottom-style:initial!important; border-left-style:initial!important; border-top-color:initial!important; border-right-color:rgb(108,226,108)!important; border-bottom-color:initial!important; border-left-color:initial!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px">26</span> </div> </td> <td style="width:626.364px; margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important"> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">Node_t Delete(Type x, Tree t) { </span></code> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(t == NULL) </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">return</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> NULL;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(t->data == x) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(t->right == NULL) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">Node_t temp = t;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t = t->left;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(255,20,147)!important">free</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(temp);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">} </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">else</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">Node_t head = t->right;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">while</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(head->left) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">head = head->left;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">}</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t->data = head->data; </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important; color:rgb(0,130,0)!important">//just copy data</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t->right = Delete(t->data, t->right);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">t->height = Max(Height(t->left), Height(t->right)) + 1;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">}</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">return</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> t;</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">} </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">else</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important"> if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(t->data < x) { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">Delete(x, t->right);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(t->right) Rotate(x, t->right);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">} </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">else</code> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> { </code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">Delete(x, t->left);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(t->left) Rotate(x, t->left);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">}</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <span style="font-size:18px"><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"> </code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; font-weight:bold!important; direction:ltr!important; display:inline!important; color:rgb(0,102,153)!important">if</code><code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important">(t) Rotate(x, t);</code></span> </div> <div style="margin:0px!important; padding:0px 1em!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; direction:ltr!important; white-space:pre!important"> <code style="margin:0px!important; padding:0px!important; background:none!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,"Bitstream Vera Sans Mono","Courier New",Courier,monospace!important; direction:ltr!important; display:inline!important"><span style="font-size:18px">}</span></code> </div> </div> </td> </tr> </tbody> </table> **5. 总结** AVL树是最早的自平衡二叉树，相比于后来出现的平衡二叉树（红黑树，treap，splay树）而言，它现在应用较少，但研究AVL树对于了解后面出现的常用平衡二叉树具有重要意义。 [LL]: http://dongxicheng.org/wp-content/uploads/2011/05/LL.jpg [RR]: http://dongxicheng.org/wp-content/uploads/2011/05/RR.jpg [LR]: http://dongxicheng.org/wp-content/uploads/2011/05/LR.jpg [RL]: http://dongxicheng.org/wp-content/uploads/2011/05/RL.jpg
相关 AVL树 以后在有面试官问你AVL树，你就把这篇文章扔给他。 作者：帅地 来源 |网络整理，版权归原作者所有，侵删。 背景 西天取经的路上，一样上演着编程... 川长思鸟来/ 2024年04月18日 22:41/ 0 赞/ 56 阅读
相关 AVL树 AVL树> 在之前我实现了二叉搜索树，但是二叉搜索树存在问题，就是当输入单调增或者单调减的结点数据后，二叉树就退化成类似链表的结构了，为了解决二叉搜索树的这种弊端就引入 朱雀/ 2022年07月14日 23:38/ 0 赞/ 148 阅读
相关 AVL树 1. 概述 AVL树是最早提出的自平衡二叉树，在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。AVL树得名于它的发明者G.M. Adelson-V ゝ一纸荒年。/ 2022年06月18日 12:27/ 0 赞/ 157 阅读
相关 AVL树 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和 た 入场券/ 2022年06月15日 09:08/ 0 赞/ 172 阅读
相关 AVL树详解 下面讲解AVL树的C语言代码实现： 1.首先是定义： define LH 1 define EH 0 define LH -1 define 红太狼/ 2022年06月13日 11:21/ 0 赞/ 188 阅读
相关 AVL树详解 AVL树是最先发明的自平衡二叉查树，二叉查找树的性质如果不知道可以百度一下。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。其实性质还是比较简单的， 桃扇骨/ 2022年06月01日 00:51/ 0 赞/ 177 阅读
相关 AVL树 一、AVL树继承自BinarySearchTree, 1，它是一棵平衡二叉树，他要求每个节点的左右子树的深度之差不能超过1。 2，每个节点都有一个平衡因子bf，取值为 今天药忘吃喽~/ 2022年05月27日 00:19/ 0 赞/ 161 阅读
相关 AVL树 [2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 平衡二叉树，是一个方便查找的树，树的左子树深度与右子树的 谁借莪１个温暖的怀抱￠/ 2022年01月15日 01:39/ 0 赞/ 188 阅读
Love The Way You Lie
朱雀
红太狼
亦凉
今天药忘吃喽~
还没有评论，来说两句吧...