1、AVL树:

    1)其左子树(TL)与右子树(TR)是AVL树;

    2)|HL-HR|<=1,其中HL和HR是TL和TR的高度;

    3)高度为h的AVL树,结点数2*h-1。

    AVL树查找,插入,删除在平均和最坏情况下都是O(logn),插入和删除可能需要一次或多次旋转重新达到平衡。AVL树的旋转平衡思路:以不平衡点为根的子树高度应保持不变,新结点插入后,向根回溯到第一个原平衡因  子不为0的结点。旋转方法如下:

  1)LL型:左旋转

      aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAVkAAACBCAIAAADlil56AAAgAElEQVR4nO2de2xUV57nS2qPB2FaSpSWcLQxibZ7s1GLPxrUMxvtJDP/dLRJeLmHtJRJIpGJMp1RtkNjNN1NHoSM0jvQaha6YaUkDQndISQ0PUkqEBOIbWxXUU+DHQjBD3CV7Xq/q+7znHte+8cplwu7ngZc5fL56Pzhgou5dc+933t+j/P7mZhAIBAwZqr1CQgEgrpAaIFAIGBMaIFAIOAILRAIBIwJLRAIBByhBQKBgDGhBQKBgCO0QCAQMCa0QCAQcIQWCAQCxoQWCAQCjtACgUDAmNACgUDAaVgt8Hg8d955p8lkMplM7e3ttNbnIxDUOY2pBZqmf//73w9HopjQ6+Pjd955587XX6eUCUUQCIrRmFpAKcWUGZgARHSD/Hxbx8ZN7ZgwShkVeiAQFKIBtYBSRihFhAJEVYBlgF/6eceGjZsgophQetNikE5n0pmZIcRF0Bg0thYQFeIrI9fuvPPOI+8f0wyC8PylIJlKfTV6xeZ2fOjozB92l+Pi8OVkMik0QbCoaUAtYNxGINTAVNXhuvUb1m/cJOlYhdjAdB4rA0mW7ZcG/ug4ue7szm+ffNJkbs8fzebNj5x5+R37J9ZBZyqVEoogWKQ0qhZk5WBbx/Y1a9bGUpKkYxUSA5OqhIBSFoyGT7jOrD29dZYEzB33d75wxP7ZuG+C3gJDRCBYaBpTCxhjlLGO7dtbWlp8gbACsAKwbhBUzaqAUubxTx60nWg2by4rBLmxy/qe++pXImYhWHQ0phZQyjo6tre0tPiDYRUSBWAVYIhp5csCviI4aDtRuQrkxou9v790fZiIxYFgUdGYWjA+PpNoxGlubrbZnRU+n5SyTCbzgbOzqhVB/jjkMAdjUSEHgkVEA2oBZQwTChFVIc5oKKNhBWAeRCCVLd0pZdZB5/2dL8xPCEzm9rtOPt3ntkGEhRgIFgsNqwUAEVnHaQ2nNSTrWIMEIkIoK/uqpozFE8m3bR+XeNTNIRdlzJ4cLXHMq5bDHp/vlmQ0CAQLQGNqAaEMIqJCIulY0hF3HFaSa8RzEy5cvfzImZdLPOcxKI0qQcpYiWNWd75oGXRCRIlIdhQsBhpVC7K5RrpBdIMARCCiiJS3EShjBsLn3Y4SnoKtlw9Rxh62vkIZ23r5UAk56HL1pxUNYbE0ECwCGlALGGOUMUoZJjR/EErLRv4pZYlU6kNHZ4kn3J4cHVWCJnP7qBIsbSb8znrcH4pCRIShIKh/GlMLGE83YrNH2X+CCQ1HY/utx0sbCAc8nTmvQYkjf9X3jmcyoBsEi3SD2wxCaMOGDTxm1NLSEolGa31Gi4+G1YJ5wJ2OvkDoDcuRsgaCydzOzQSuCwXH8917R8cnVEgwEVpwe9m+ffvatWtlRcWEbuvoWLNmraKo4ppXhdCCGSiliFB/MLLHerSsgZDvRCx28EvnDox5fTLAhnAZ3E7GPZ7W1laHw2VgChEZGbu+cmWrw+ES+R1VIbRgBkqpgWk4njpmL/qqn2t35JYJc8cey9Frk0EZYOE+vH1QyiwWK88x1QyiQpKUtLa2tqPHPkSEiooVlSO0YAZKKcI0rYAep7Xgs33A0znryS9tJpgd3f5oRtIREm+o2wZl7NDhwy0tLZO+EN94kpLBY4+vf+W1nQCRKjejLWmEFszA1wUywJYhd8GNiaNKcK5FUPAPTeb2u09t6XPbI5Ih1gW3FUrZHw69u3z5cq8vpACsQpxR4WPr1r/86uvV7kZb4ggtmIEyhghVIRmfDLzR/15BA8Eccs1++YdcBc2E57p/OzgyFpWg8BfcPihlhLJzff3Ll7d4/WEVEt0gKUlta1v1x6PHVHhT1WuWGkILZuBxBA3ihAx7Xba7Tj5dIl5YejSbN3c5LZMxJa4gEUe4ffApGxm7vnLlyl6LXYUE4uzHPqtDBdnqNbU+zcWB0IIZ+EsGGCStoaueqTctf5q3Fmw9d9A5PBxKw7SGdENYrbcLrgWqbjy+bsP6jZtUSCCiP+/YvmHjJhngnBaIq18JQgtugFKGMJUBjsmG7crlp7p3m95/vFohePiLX/QOuqcSICoZ0wZCrb9Yg5Lbh5aQtLa2VTzXaM2atfG0LIP5VLJayggtuAF+b+kGSWsokNRf/LcOk8lkeuuRyoVg7emtZy/YvFE1mIZJFWkQi7vx9sH3khmYqhBLOua+QxViGWBZz1WyqvVZLhKEFtwAD0cjQhWA3zr8R5PJ9JNnntrZ/+7ckqcFfQQ/7dnXd9HtiSj+FIzJhqxjsRnhdsPnSzeIrGNJx7KOFYD5ogAI66wahBbMhi8NPjp+oqmp6SdPPuVPwcGx6z2u8z/t2Xf3qS0FVeCuk08/07W7y2lxXh32xnR/EkQyMKMhgKqoqiaYH9Ola4hmEL4cUADmAQXhLKgKoQUFOHHiRFNT04//cXNC0qMS9KeAJ6q4hkf63Xazs/v57r3548/2M/0uu/Pq8LWQNBHXfUkQkbIuQxHQWhh4zWs4vUVdNwgwiFFNeUsBE1owF6vVumLFiieeeEIHhm4QSccx2QikwGQCeGP6WCB1acRzacRzacR7acR7acQz4ot7Yro3rk/G9UAKxGQjk2epiptxAciVwMeEIkJRbot6rU9scSG04Aa4EDz00EOSJPOYAkBUBjiponAGBlJgKgEmE8Ab1yfi+kRc5z9MJYA/CcIZmFCQJISgRlDGeH0KbhaIi18tQgtmGBoa4kIgyzKb9iNiQiGmvFxaUkVRyQhnYDCdHaE0DGdgVIIJxchoSAU4mwMvhECw2BBakGV4eLi1tfUHP/gBF4IcvHoir5imQSIDnNFxWkPTIxvK0oxsGTVMyldPEgjqEKEFjE0LwQMPPBAKheb+LV98EsowoQhTiChEFKBsGUWIKMJZY1W0S6oJiqL6fD6fzzc1NTU1NeXz+SRZFnJcLUILWCgUuu+++4oJQY5s0TTKyLQuYEIJZTxqJQzUhQchfNUzZh1wnHT1zAru/KfzrNVtv+oZg4Yh5qVClroWhEKhBx54oLW11ev1Vv6vZoopivusRoz7J3rd5ZI+uvf0uK3feMaE1VYJS1oLYrEYF4Lh4eFan4ugUihjg2NXdlnfqzwZ1Hll0EBIqEFplq4WyLL80EMPfec73xFCsIigjLm/GXqq+z+q2i32o7OvnBu0GwgLOSjBEtUCLgQrVqywWq21PhdBpVDGLo+P/PO5385jF/nDZ35huzwgMhFLsBS1ACH0ox/9SAjB4oIyNhX0/9o6/6ISP+/9f1c8Y0IOirHktAAh9MQTTzQ1NXV1ddX6XARVgDHpcxcuNmVPjuaXpZ5bhy7nO+h2WXQIxYalgtRSC7Zv397S0hKJLFyLm5wQ/OUvf1mw/1Rw81BKg6HQG5YCRShNN5af5c1silWmfq5n79Xr10Qp2oLURgs0XV+1alW23VUkOu9pQQhHotFcksnU1FQkGi0RUv7Zz34mhGDRwWvP2b4aKFic2jSnFHWJPpd3n9picduh2EteiBpoAWWsY/v2NWvXfn76dEtLSzAcmcfEpDMZ59cXrS77b6xH85NMfmP9oNd13vaVO5lMzvqd27ZtM5lMBw8evGXfRLAgUEp1YJwr0rRirhbEoFSi5+1nzu5ESha10uey0FowveGHAYN091qWL2/xBcJVFaLSAbBfGvjQ0fng6Y5i87329NZ37J9YB525pno7duwwmUz79++/bd9McLsglCZS6RLNr+faCFsvHyp28G+sH0wFwhBTIvaP3ciCawFjhDIDU80gZ3r6lre0TPhCEFU6MYqinB7oK7ZWnDXu73zhY9eXoVh03759JpNp9+7dt//7CW4xvGxRIFSqyeWoEsz3HcagVOKueOncgeten24QIjaP3EittIBoBjnb07+8pcXrC1div1HKJEn6zNVdVduCb598cu/nR0wm07Zt28RLYDFSSfPruf4Cylixg5/v3js6PqlCjLC4I26gVjYCBYh82dPHtaBsjUpKma6DMwP9laSdzhrN5s17/3Iomco0cE2BoaGhVCpV67O4LfDm14Fw9HfW4xVqQekml7/qe+ea1y+aWc2lNr5DbiZ09/J1QaisFmCM+y7Yiu1CKTvuOvn0lwMWHTTslrVdu3bdcccdu3btajxFqKT5dVVasN96fNwXFk0u51KbmCIvH9bda8lqQcl+uJSxyYD/VcvhufPKZz1/FLtdnunec+X6KG5Q7/GuXbt4m5DGU4Rsw1sdWV32ZvPmm7cRvnT2+2OSDLBonTCLWqwLKOvo2G7Ko7m52el0FZwXXi/A6rYXdBPMchqPKsFifqNm8+Ze53ndQA0ZWM5pQeMpQq75tePKV4+cebng5M7KOyzhO1zd+WLfBWdEMmRdrAtmUxsbgRcRlAFOayhTsr8NpTSZyhwrEk+apQX849yWx3zssR71hyI17Gj29ddf994etmzZYppDYygCZQxhqgI8GYi+bftkfkZibrzSf+jy9YmoZCjZdYHQghlq4ztEhGoGkXScUlFaQ9M9MGfHeHjC2dfXRn589o1KtOCAp7OEFvzDmV86vh6sVS+dUCg093FdAO67776qyrTUG9y7pBskqaL+C877O1+YtxDcdfLpc67zvriWUAxNtFSaQ21iighT3cjWEc3oSIUEFnIZ8BXE+a/cxRIK5toI+XbjrHH3qS2WAYcKSa0WhwMDA2JdUC3Z5teIZDQ0EYy/7/i8mNeg7HjH9umViWAoA9MaKu2iWprULO8QYqobRDOIBjGvIDzXSuC2onXAUSyCwLUgfxTzHpvM7c3mzXaXU9YbsPFxA/sL2PRtoEISl42h657/UzzpqMT450//w/7NN74kiMmGcBwWpDb+AkoZpgzhMl1uCKUQEYursONw7rqAfyy2ZdVkbnc6nZlsv9OGyjVo4DgCy2usntbQeDCx8Yknmpr/qvn4psqF4F8+3f2tb33rfz2+0f31GG9vJxYFc6lZTHG6y022LOXcieGLQ4iI5YLj3lPPVaIFJnO7PTlazI387ZNP2tyOlNqAt0ID5xdwKGUGpg73xf92/39vamr6t1dfO+74opJU9Ps7X3jX9pnj6vA7759oW3XvXy9btnPXv8uq1sCJZ/OmfmuZ5NITrUOV+gtKa8G9p57rH3AkVdR4uegNnHfIoYzt27d/2bJl//W73+uzDQTS8Fog0XfR9a7ts3Vnd87NRm02b37kzMtv2T7uu+Acnoh447o/Cfwx6Zc7Xl22bNn3vve90198UevvVHfUsRZMrwxHPN4XevbdvI2w7uxO55XLScVoPC1obGKx2Pr1600m05Znn02kJElHcd7tNq4PT0TsX18+73J8YO/MHzanw/rV0NWJ8HhUm8jreQsQHRkde/TRR00mU3t7+6KOsNxy6lgLuAPZINGUctrZW/Dxnpt3WMJ3+J79s+u+KF8XYKEFi4Surq577rlnxYoVH330EW+mDAwi6zihoFAa+pNgIq57YvrwZHR4KpYb41HNE9O9Md2XBKF0tuctQNneVoyxTz/99L777lu2bNmbb76p63qtv2VdUOdaQCGmGe1mA8smc/tdJ5/udduCST2tzbQ/FdQzCKEdO3Y0NTX98Ic/zL3AeTM73u02raGYbATT0J+CU0kwmQC8+fVkAkwmAFeBmGykVKQADOf0vNV1/bXXXuMmwxfCZKhnLWAsm5Uk69gbiL51/uOb0QKecBbOQCkbRxBKUNd4vd4HH3zQZDLt2LEDIZT/V9x4zKWopFQUl42oBMOZ7IhkYFQyEgpKa0jWsW4QA5NiW1GuXbsmTAZOfWsBY5gwHljuG3I//MUv5icEqztf7L7gmIprcdlQIRHJp3XORx99dMcdd7S2tharVU2nXcsGJgARFWIZYEnHGR1ldCTpWAZYhUQ3iIGLRqzzESYDWwxakA0sB1P62QFr27Gn5mEdnHL1jocyoTTMxpaFs6BekWX5+eefN5lMjz76aCwWK31wThEwoQaePTBhuc7XlSi/MBnqWgvYdGBZhSSuoL0H3jaZTPcfqqKu0b2nnjM7u68FkrmEs8ZLOmwYhoaGHnjggaampqrKUmbdxjTrC5gehZNWyrKUTYa61wK+qRHRMz39TU1N//iTf+q+4Hix5/dlCxw1mzc/07X7jNs6FkhNJfRwJrsoENHE+mT//v38nTw0NFTrc1miJkO9awFjjFJ6fdy7srX1b/72f0xGMpNx7cLIWI/r/EvnDhQMLtx76rkXevZ1OS3Oq8PjEWUqAcIZmFKRVnxntKCG5NIHnn32WVmWa306WZagybAItECS5NWrV/+Xe+7xTgXSGopIhi8JvFHl67GJ3gvOs46+/CSTs47+vgHH4Mj4tZDEw8tcCLjLUEhBvZGfPlDrcynAkjIZ6l0LEELr169fsWLFxcFBA1MNkrSGohIMpOFkAnhj+vVQZnhyJsnkWjDDk0wm43ogBSIZmNaQComBhXVQXxRMH6hPlojJUO9awHucfPrpp5QxQikiVDeIpOOEYkQkI5CCviSYjOsTcX0iDibi+mRc9yVBIAUiGSMuG9miSYUKpQhqSIn0gfpkKZgMda0FR44cMZlMb775Jv+YiyHxtLOMjpIqislGRDLCGRjOGOEMjEhGTDaSiiHpWAUYIi4EwjSoI8qmD9QtjW0y1K8WWK3WpqamZ555Jv8PebiIUIYI5dVQVEhkneeZYJ5kogCsGwQgwisjUJFYVDdUlT5QtzSqyVCnWuD1eltbWx988MGC15pm89IpJhQRijA1MIWIGDcUR2FCBOqK+aUP1CcNaTLUoxbIsrx69ep77rknFAqVOCyvIAorkGciZKCeqKv0gVtFg5kMdacFucBBI900jUQ6nUlnZkZZza3P9IFbSLUmAwAg/wLqANTJe6vutCAXOKj1iQhuIJlKfTV6xeZ2fOjozB92l+Pi8OVkMlnwfq7z9IFbRSUmA0LYHwicH3J1ufrzL2CXq9960emZnIBGjXv81ZcWzAocCOoBSZbtlwb+6DhZoprYO/ZPrIPOVCqVu5kXUfrAraKYyYAxGZsY73Wf33ruYLFM2X/t2d/jtn4zPoYQqpUi1JEWFAwcCGoIpSwYDZ9wnamwyugR+2fjvglKqcezyNIHbiGzTAaEsfWS+2fnKttB072nZ9Cm6XpN1KBetKB04ECw8FDKPP7Jg7YTVfUm2WV979d79yzS9IFbRc5k+O53v7vn4P+tREnzJfULd5+sKAsfBKsLLagwcCBYMPiK4KDtRNWVYz7e9K3mv/q7v384Eo3Wh0esZoyMjPzt/3zQZDKZ3n+82oobne5eTdcXWA5qrwUicFBvUMoymcwHzs55dis7vv6QwxyMRZdyuidlzHZ54O/P/tJ05NF5XMPVnS/2DzkNtKDFNmqvBSJwUG9QyqyDN9vFtM9tgwgvTTGgjCUSybdtN1Wh81XLYa/ft5BNfWqsBSJwsGAghDZs2MBbrbW0tEQi0YKHUcbi5e5je3I0V4Tenhwtdit7fL5iFUcbGJ7wVlZM+dUr1hM8p6fAqPQSVji/JSilBXN+e6SSWa08F0UEDhYMSllHR8eaNWskWcGUbevoWLt2raKqcw8jlF64evmRMy8Xu0djUMrvTGVPjhZsTrO680XLoBMi2mCtK8tCGVNU9bSrcEcPPg54OvllLNH702RuP2L/LBJLVtIWvML5LU1RLZj+7WslWTEw3dbRsWbtWllRi51WtbkoInCwYFDKxsc9ra2tNocTIAIRGR0bX7my1eF0zppNypiB8Hm3o5inwBxyUcYqXOV2ufrTilarDve1glB6fWLihe7Cnb74GFWC5pDLnhwdVYIlDlt3dufF4SsQl9HTyue3NEW1YHx8vLW11eZwAUR1gwyPja9sbbU5XJiyWf/BPHJRROBgIaGU9vdbWlpapvxhFWIF4KSktrW1fXDso1nmKKUskUp96Cjae6rsqyx//M563B+K8m4US0QNKGOEsvNfFe0Aappu9rX18iHe8q+EmcA7gGqwTCvgyue3NIW1gDJmsVpbWlp8gbACsAJwIqO2ta3609FjRl5dkPnlohiGIQIHCwZvRfeHQ4eXL2/x+kKyjmUdJ2X98XUbXn3t9fwCkLw2RDga2289XuImLtGlbtb4Vd87nsnAkipCTylFhFovOot1Bs8ZCPznEu0/Teb2b5988rzbIQNcIp5Q+fyWpYgWUPqHQ4eXL18+4Q/LOpYBTivgsXXrX35153RTOjrvXJQt//KcyWT6RAQOFgReSPrtPxxevrzF6w8rAKuQpGTw2Lr1r7y2EyKSW3/yI32B0BuWI6VfaBXO9fPde0fHJ1RIMFk6WsAMTC0u+10ni1buH1WCOYdribbgfDidzoyGIKbFXvCVz29ZCmgBdyBllcYfViDRIJY0+Pi6DS+/9rpmEANTQuabi3LkUZPJ9L87ti7l4PNCQilFmPb09vP3hm4Q3SBJSWtrW3Xk/WOQK3vuSEL9wcge69Fbsi546dyBMa9vuidF4882f0VDRCxu+92ntlSipwc8nSXktdm82e5ypjVUogNo5fNblkJawBgm9Fy/ZfnyFo8vpEICEU3LalvbqiPvf8A/ptLp+eeivPWIyEVZMPib6urY9ZUrW/ttToAoQCT78bwDoJkFPKXUwDQcTx2zF33aS69pZ409lqPXJoPTS9zGn2puZAFErENF/QXc+TprFIvL3n1qS7/bnlSRVtzOqnx+y1JUC0bGrq9cubLXYlchhoiOXhtf2draZ3Xwj5ZB5/2f/+t8hMDcblryuSgLCb9XJA0+tm79ho3tABGI6dZtHes3bpIBnqUFCNO0Anqc1mITV3ZNe8N97+j2RzOSjpZIW4pcy7+h0eEfn32j4DWJQWnWk1/ikv7DmV/aLg8mFaNEj5/K57csRbVA1eHj6zas37hJhQQgsq1j+4aNm2SAFUjCseRbIhdlkcB7VWsGiaWVtrZVPFvkB2vWRlOSAkm2E3n2SGpgKgNsKf5a40uD/EiYOeQquFK4+9SWPrc9IhlLcF0QiCSPFYrF8MDBLIug4B/mFlZjk8Gy64IK57csxfwFDCLKYwfTv31NLCVJGlYgdl25/MiZooEQkYtSV1BKMWG8PbmkYxVizSAKJDLI1onO9x0iQlVIxicDb/S/V0LrY1Aqq/XPdf92cGQsKsGl5i8AiGQ0XNB9WCw7o+BlbDZv7nWe9yfUsv6CCue3LMXiCAxhqhlE0rGkIx5WlHUsASxphsXl/GuRi7JIoIxhyiCiCpipE81jQ7OayvH1oAZxQoa9LlsJT3jZ0Wze3OW0TMaUuIKWYBxB0tGwd/JVy+F5X0CTuf2Zrt0Dw8PhDJR0XCaOUNn8lqVoTJGvdhSAJR3J079dATgcT35g7zSZf1zsjSFyUeoKnh5vYKrz14WOubJrEBv4Bidz9rVmkLSGrnqm3rT8ad738dZzB53DwzNN7hdwg01t4bEYFeJYBpwbsBWLJpQdd518+oyrfyKqRCVDgaR0fkGF81uWousCQqmBKUBUhUSFRIVYBViFOBCO7rf8ueAXELko9Ql/4SNMASI85gQQMTCdm0LK14MywDHZsF25/FT37nncxw9/8YveQfdUAkSlJdfknr+ldYOkNTQVyZid3WXLGc0dzebNf7J/PjoVC6RAUi0vppXPb2mK70dgjFDGWw9w5yTvQTDlD+3qF7koiwzK2Ew7ibz+EXMPw4TyWzmQ1HuGXE90/bqq+3jt6a1nL9i8UTWYhkkVaRAvnUUBh7+luZ5enQwed3xRlRw0mzf/3nri4jWPLwmikiHpqJKFc4XzW5pS+xTp9LoRE4oJxYQYmPgCIhdlUZLXToJyt1/hYyhDhCoAJxTkT2iWS4M7+9+t5G5uNm/+ac++votuT0Txp2BMNmQdL0EDMF9PIxnjeiB52tVXYZmz+ztf+Njx5WWPfzKuhzIwlVsUVHAFK5nf0pSvX5DzGBMiclEaH34rQ0QlHcdkw5+Cg2PXe1znf9qzr5j1e9fJp5/p2t3ltDivDntjuj8JIhmY0RCoJumtkeBLAxXipIpCGegJS70XXR/YOx883VFiPfWW7ePeC86xQGoyAYJpmFCM6f7gC/RwVFHLROSiLBG451g3SEZDUQn6U8ATVVzDI/1uu9nZ/Xz33vzxZ/uZfpfdeXX4WkiaiOu+JIhIWZfhwlboqiO4fW1gqkKSVFAoA6cSYGQq2j90weqy7+4/mn8Bd/cfPee09l10X50Ie2L6VAIEUyAuGzLAsErn301SnRaIXJSlQNZSwNn29jHZCKTAZAJ4Y/pYIHVpxHNpxHNpxHtpxHtpxDPii3tiujeuT8b1QArEcn3uSba33dJkenlFVEiSKopkDF8STMT18Yjyzbg/7wJ6r4z7r4Xk8ajmjem+JAhnjKSKqk0ZvCVUowUiF2XJkJMDgKgMcFJF4QwMpMBUAkwmgDeuT8T1ibjOf5hKAH8ShDMwoSBJCME0XA746iCtoZhshNLQlwRTCZC9ejF+GcFkXPcnQTAFopKR1hBP8682CnDzVKcFIhdl6cAfZkwoxFSFRNJxUkVRyQhnYDCdHaE0DGdgVIIJxchoSOVvMyEE0+SMBZ4XmNZQXDYikhFKw2AKBNMwmAKhDIxIRlw2UiqSdawZBC2saZCjKhtB5KIsObKhZUIBIhokMsAZHac1ND2wpGMFYM0gEGWjWVQs8vLIBeO4IqgQywBnNJTWUEpFaQ1ldJ47THSDZLODapRuU10dZJGLsgThkSoeWkaYQkQhogARgAj/mb/HangT1z90eucSItmEHYAI318METEwRYQSyrgPvVaPQ5VaIHJRlirT4WtGpnUB527f6b8SlGY6/p/NC8IzSUGsHtZSVa8LRC6KIPvwi+d/vvDniE7/UCdU3StF5KIIBA3JfPomiVwUgaDxmJ8WiFwUgaDRmGc/RZGLIhA0GPPvrSpyUQSCRuJm+yyLXBSBoDG4BT3XRS6KQNAA3AIt4GPASmkAAAANSURBVIhcFIFgUfP/ATBAL8GhFBWVAAAAAElFTkSuQmCC" alt="" />

  2)RR型:右旋转

  3)LR型:在不平衡的儿结点先进行右旋转,然后进行左旋转。

  4)RL型:在不平衡的儿结点先进行左旋转,然后里德右旋转

  注意在旋转过程中涉及的最小树应该保持搜索二叉树的性质。

  AVL树的C++实现核心部分是平衡旋转:

 #include "stdafx.h"
#include<time.h>
#include<stdlib.h>
#include<iostream>
using namespace std; typedef struct AVLTree{
int ndata;
AVLTree* pLchild;
AVLTree* pRchild;
int nheight;
}AVLTree; AVLTree* LLRotate(AVLTree* pRoot);
AVLTree* RRRotate(AVLTree* pRoot);
AVLTree* LRRotate(AVLTree* pRoot);
AVLTree* RLRotate(AVLTree* pRoot); int Compare(int a,int b){
return(a > b ? a : b);
}
int Height(AVLTree* pRoot){
if (NULL==pRoot)
{
return -;
}
else
{
return(pRoot->nheight);
}
} AVLTree* Insert(AVLTree* pRoot, int nData){
if (NULL==pRoot)
{
pRoot = new AVLTree;
pRoot->ndata = nData;
pRoot->nheight = ;
pRoot->pLchild = NULL;
pRoot->pRchild = NULL;
}
else if (pRoot->ndata>nData)
{
pRoot->pLchild = Insert(pRoot->pLchild, nData);
if (Height(pRoot->pLchild) - Height(pRoot->pRchild)==)
{
if (pRoot->pLchild->ndata>nData)
{
pRoot = LLRotate(pRoot);
}
else
{
pRoot = LRRotate(pRoot);
}
}
}
else if (pRoot->ndata<nData)
{
pRoot->pRchild = Insert(pRoot->pRchild, nData);
if (Height(pRoot->pRchild) - Height(pRoot->pLchild) == )
{
if (pRoot->pRchild->ndata<nData)
{
pRoot = RRRotate(pRoot);
}
else
{
pRoot = RLRotate(pRoot);
}
}
}
pRoot->nheight = Compare(Height(pRoot->pLchild), Height(pRoot->pRchild)) + ;
return pRoot;
} //LL旋转
AVLTree* LLRotate(AVLTree* pRoot){
AVLTree* pTemp; pTemp = pRoot->pLchild;
pRoot->pLchild = pTemp->pRchild;
pTemp->pRchild = pRoot; pRoot->nheight = Compare(Height(pRoot->pLchild), Height(pRoot->pRchild)) + ;
pTemp->nheight = Compare(Height(pTemp->pLchild), pRoot->nheight) + ;
return pTemp;
} //RR旋转
AVLTree* RRRotate(AVLTree* pRoot){
AVLTree* pTemp; pTemp = pRoot->pRchild;
pRoot->pRchild = pTemp->pLchild;
pTemp->pLchild = pRoot; pRoot->nheight = Compare(Height(pRoot->pLchild), Height(pRoot->pRchild)) + ;
pTemp->nheight = Compare(Height(pTemp->pRchild), pRoot->nheight) + ;
return pTemp;
} //LR旋转
AVLTree* LRRotate(AVLTree* pRoot){
pRoot->pLchild = RRRotate(pRoot->pLchild);
return LLRotate(pRoot);
} //RL旋转
AVLTree* RLRotate(AVLTree* pRoot){
pRoot->pRchild = LLRotate(pRoot->pRchild);
return RRRotate(pRoot);
} //输出树
void PrintTree(AVLTree* pRoot){
if (NULL==pRoot)
{
return;
}
static int n = ;
PrintTree(pRoot->pLchild);
cout << ++n << "\t" << pRoot->ndata << "\t" << pRoot->nheight << "\n";
PrintTree(pRoot->pRchild);
} int main()
{
AVLTree* pRoot = NULL;
srand((unsigned int)time(NULL));
for (int i = ; i < ; i++)
{
pRoot = Insert(pRoot, rand() % );
}
PrintTree(pRoot);
return ;
}
05-12 07:45