<kbd id="daqct"></kbd>

  • <nav id="daqct"></nav>
    <wbr id="daqct"><pre id="daqct"></pre></wbr>
    <wbr id="daqct"></wbr>
    <form id="daqct"><th id="daqct"></th></form>
    更多課程 選擇中心

    C/C++培訓
    達內IT學院

    400-111-8989

    c++程序員面試 - 二叉平衡樹的插入

    • 發布:C++培訓
    • 來源:C++職場
    • 時間:2017-10-25 15:57

    平衡二叉樹(Self-balancing binary search tree)又被稱為AVL樹(有別于AVL算法),且具有以下性質:它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1,并且左右兩個子樹都是一棵平衡二叉樹。

    如下圖示一個平衡二叉樹:

    1. 左旋和右旋:

    左旋:以A為中心逆時針旋轉,實際就是:把B移到A的位置,把B的左子樹作為A的右子樹,再把A變成B的左子樹。在平衡樹種以平衡因子為-2的節點為中心做左旋操作。

    左旋前

    左旋后

    1. /左旋

    2. void RotateLeft(tNode** root)

    3. {

    4. tNode * p=*root;//相當于A

    5. tNode* lc=p->pright;//相當于B

    6. tNode* llc=lc->pleft;//相當于C

    7. p->pright=llc;

    8. lc->pleft=p;

    9. *root=lc;

    10.}

    右旋:以A為中心順時針旋轉。實際就是把B移到A的位置,把B的右子樹變為A的左子樹,在把A作為B的右子樹。在平衡二叉樹中以平衡因子為2的節點進行右旋。

    右旋前

    右旋后

    1. void RotateRight(tNode** root)

    2. {

    3. tNode* p=*root;//圖中相當于A

    4. tNode* rc=p->pleft;//相當于B

    5. tNode* rrc=rc->pright;//相當于D

    6. p->pleft=rrc;

    7. rc->pright=p;

    8. *root=rc;

    9. }

    平衡二叉樹的插入時的四種不平衡情況:

    (1)“左左”

    由于在A的左孩子B的左子樹上插入結點F,使A的平衡因子由1增至2而失去平衡。故需進行一次順時針旋轉操作。即將A的左孩子B向右上旋轉代替A作為根結點,A向右下旋轉成為B的右子樹的根結點。而原來B的右子樹則變成A的左子樹。

    (2)“左右”:

    由于在A的左孩子B的右子數上插入結點F,使A的平衡因子由1增至2而失去平衡。故需進行兩次旋轉操作(先逆時針,后順時針)。即先將A結點的左孩子B的右子樹的根結點D向左上旋轉提升到B結點的位置,然后再把該D結點向右上旋轉提升到A結點的位置。即先使之成為LL型,再按LL型處理。

    插入代碼:

    1. void LeftBalance(tNode** root)

    2. {

    3. tNode* p=*root;

    4. tNode* c=p->pleft;

    5. tNode* rc=c->pright;

    6. switch(c->bf)

    7. {

    8. //LL情況

    9. case 1:

    10. {

    11. p->bf=c->bf=0;

    12. RotateRight(root);

    13. break;

    14. }

    15. //LR情況

    16. case -1:

    17. {

    18. switch(rc->bf)

    19. {

    20. case 1:

    21. {

    22. c->bf=0;

    23. p->bf=-1;

    24. break;

    25. }

    26. case 0:

    27. {

    28. c->bf=0;

    29. p->bf=0;

    30. break;

    31. }

    32. case -1:

    33. {

    34. c->bf=1;

    35. p->bf=0;

    36. break;

    37. }

    38. }

    39. rc->bf=0;

    40. RotateLeft(&c);

    41. RotateRight(root);

    42. break;

    43. }

    44. }

    45.}

    (2)“右右”:

    由于在A的右孩子C的右子樹上插入結點F,使A的平衡因子由-1減至-2而失去平衡。故需進行一次逆時針旋轉操作。即將A的右孩子C向左上旋轉代替A作為根結點,A向左下旋轉成為C的左子樹的根結點。而原來C的左子樹則變成A的右子樹。

    “右左”:

    由于在A的右孩子C的左子樹上插入結點F,使A的平衡因子由-1減至-2而失去平衡。故需進行兩次旋轉操作(先順時針,后逆時針),即先將A結點的右孩子C的左子樹。

    1. void RightBalance(tNode** root)

    2. {

    3. tNode* p=*root;

    4. tNode* c=p->pright;

    5. tNode* lc=c->pleft;

    6. switch(c->bf)

    7. {

    8. //RR情況

    9. case -1:

    10. {

    11. p->bf=-1;

    12. c->bf=0;

    13. RotateLeft(root);

    14. break;

    15. }

    16. //RL情況

    17. case 1:

    18. {

    19. switch(lc->bf)

    20. {

    21. case 1:

    22. {

    23. p->bf=0;

    24. c->bf=-1;

    25. break;

    26. }

    27. case 0:

    28. {

    29. p->bf=0;

    30. c->bf=0;

    31. break;

    32. }

    33. case -1:

    34. {

    35. p->bf=1;

    36. c->bf=0;

    37. break;

    38. }

    39. lc->bf=0;

    40. RotateRight(&c);

    41. RotateLeft(root);

    42. break;

    43. }

    44. }

    45. }

    46.}

    本文內容轉載自網絡,本著分享與傳播的原則,版權歸原作者所有,如有侵權請聯系我們進行刪除!

    預約申請免費試聽課

    填寫下面表單即可預約申請免費試聽!怕錢不夠?可就業掙錢后再付學費! 怕學不會?助教全程陪讀,隨時解惑!擔心就業?一地學習,可全國推薦就業!

    上一篇:C++程序員面試題-Vector的自增長
    下一篇:2017年百度C++開發面試題目及答案

    幾個C語言經典基礎算法(含代碼)

    不得不知道的八個C語言面試題

    C/C++后臺開發面試難不難,京東二面

    C/C++后臺開發面試難不難,來看看京東

    • 掃碼領取資料

      回復關鍵字:視頻資料

      免費領取 達內課程視頻學習資料

    • 視頻學習QQ群

      添加QQ群:1143617948

      免費領取達內課程視頻學習資料

    Copyright ? 2021 Tedu.cn All Rights Reserved 京ICP備08000853號-56 京公網安備 11010802029508號 達內時代科技集團有限公司 版權所有

    選擇城市和中心
    黑龍江省

    吉林省

    河北省

    湖南省

    貴州省

    云南省

    廣西省

    海南省

    欧美三级片,白洁外传,第四色播日韩AV第一页,啪啪免费观看大全av 百度 好搜 搜狗
    <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>