每周算法-AVL樹

文章首發(fā)個(gè)人博客 shimeng.info

背景

之前學(xué)習(xí)過二叉搜索樹BST窝撵，順序的插入數(shù)據(jù)的時(shí)候BST被退化為鏈表，因此為了防止這種情況的發(fā)生襟铭，就需要引入一些機(jī)制碌奉，那就是平衡樹。平衡的機(jī)制就產(chǎn)生了平衡因子這個(gè)概念，它用于表示一個(gè)節(jié)點(diǎn)的平衡性，如一個(gè)節(jié)點(diǎn)的平衡因子為1淮悼，則表示該節(jié)點(diǎn)的左子樹和右子樹的高度差為1暖呕。在這里將平衡因子定義為左子樹 - 右子樹的差。通過定義能夠明白如果一個(gè)平衡因子為整數(shù)，則表明左子樹比右子樹高，也就是該節(jié)點(diǎn)下左子樹比右子樹的的節(jié)點(diǎn)數(shù)多，因?yàn)閷τ谝粋€(gè)平衡的子樹來說璃赡，它的高度是其節(jié)點(diǎn)數(shù)的logN，因此也就是說該節(jié)點(diǎn)下的子樹向左偏移了献雅。

自然而然的我們就知道的平衡樹的定義：一棵二叉樹碉考，對于任意一個(gè)節(jié)點(diǎn)，左子樹和右子樹的高度差不能超過1挺身。

下圖即為一棵平衡樹侯谁，括號內(nèi)表示該節(jié)點(diǎn)的高度值，節(jié)點(diǎn)的高度值：葉子節(jié)點(diǎn)的高度為1，非葉子節(jié)點(diǎn)的高度是其左右子樹高度的最大值 + 1


                                (4)15

                                /      \

                            (3)6    (2)18

                            /  \    /

                        (2)2  (1)8  (1)12

                          /

                      (1)1

因此先生成一個(gè)二叉樹墙贱，之后在引入平衡機(jī)制热芹，所以重新實(shí)現(xiàn)一個(gè)二叉樹

定義Node對象


class Node {

  constructor(key, value) {

    this.key = key;

    this.value = value;

    this.left = null;

    this.right = null;

  }

}

定義BST構(gòu)造函數(shù)


class BST {

  constructor() {

    this.root = null;

    this.size = 0;

  }

}

添加節(jié)點(diǎn)


push(key, value) {

  this.root = this.insert(this.root, key, value);

}

insert(node, key, value) {

  if (!node) {

    this.size++;

    return new Node(key, value);

  }

  if (key > node.key) {

    node.right = this.insert(node.right, key, value);

  } else if (key < node.key) {

    node.left = this.insert(node.left, key, value);

  } else {

    node.value = value;

  }

  return node;

}

查找節(jié)點(diǎn)


find(key) {

  const node = this.get(this.root, key);

  return node;

}

get(node, key) {

  if (!node) {

    return null;

  }

  if (node.key > key) {

    return this.get(node.left, key);

  } else if (node.key < key) {

    return this.get(node.right, key);

  }

  return node;

}

刪除一棵子樹上的最大節(jié)點(diǎn)


deleteMax() {

  let max;

  this.root = this._deleteMax(this.root, (node) => max = node);

  return max;

}

_deleteMax(node, cb = () => {}) {

  if (!node) {

    cb(node);

    return null;

  }

  if (!node.right) {

    this.size--;

    cb(node);

    return node.left;

  }

  node.right = this._deleteMax(node.right, cb);

  // return node;

  return this.keepBalance(node);

}

刪除任意節(jié)點(diǎn)


delete(key) {

  this.root = this._delete(this.root, key);

}

_delete(node, key) {

  if (!node) {

    return null;

  }

  if (node.key > key) {

    node.left = this._delete(node.left, key);

  } else if (node.key < key) {

    node.right = this._delete(node.right, key);

  } else {

    if (!node.left) {

      this.size--;

      node = node.right;

    } else if (!node.right) {

      this.size--;

      node = node.left;

    } else {

      let successor;

      node.left = this.deleteMax(node.left, (node) => {

        successor = node;

      });

      successor.left = node.left;

      successor.right = node.right;

      node = successor;

    }

  }

  return node;

}

對于一棵二叉樹來說，根據(jù)我們的定義惨撇，剛開始是平衡的伊脓，因?yàn)橹挥幸粋€(gè)節(jié)點(diǎn)的時(shí)候還沒有左右子節(jié)點(diǎn)，其平衡因子為0魁衙。之后是因?yàn)樵黾庸?jié)點(diǎn)從而從平衡變?yōu)榱瞬黄胶獗ㄇ弧Ｖ赖倪@個(gè)原因，只有針對發(fā)生這種結(jié)果的幾種條件一一枚舉出來剖淀，才能具體知道如何去維護(hù)一棵樹的平衡纯蛾。

不平衡條件

第一種

第一種也就是最容易理解的，一直往左子樹添加節(jié)點(diǎn)纵隔，當(dāng)添加到第三個(gè)節(jié)點(diǎn)的時(shí)候此時(shí)不再平衡

此時(shí)節(jié)點(diǎn)8的左子樹高度為2翻诉，右子樹的高度為0，因此節(jié)點(diǎn)8的平衡因子為2

第二種

第二種相反巨朦，一直往右子樹添加節(jié)點(diǎn)米丘，也是當(dāng)添加到第三個(gè)節(jié)點(diǎn)的時(shí)候不再平衡

此時(shí)節(jié)點(diǎn)8的左子樹高度為2，右子樹的高度為2糊啡，此時(shí)節(jié)點(diǎn)8的平衡因子為-2

第三種

第三種情況和第一種情況稍有不同，那就是當(dāng)添加到第三個(gè)節(jié)點(diǎn)的時(shí)候吁津，在第二個(gè)節(jié)點(diǎn)的右子樹上棚蓄，看示例

此時(shí)節(jié)點(diǎn)8的平衡因子和第一種一樣都是2，不同的是節(jié)點(diǎn)4的平衡因子為-1

第四種

第四種情況和第二種也只是稍有不同碍脏，當(dāng)添加第三個(gè)節(jié)點(diǎn)的時(shí)候梭依，在第二個(gè)節(jié)點(diǎn)的左子樹上

此時(shí)節(jié)點(diǎn)8的平衡因子和第二種一樣都是-2，不同的是節(jié)點(diǎn)10的平衡因子為1

這個(gè)時(shí)候我們把四種情況放到一塊再看看


    8      8            8      8

    /      \          /        \

  4        10        4          10

  /          \        \          /

1            12        5        9

(一)        (二)      (三)      (四)

(一)和(三)的情況是節(jié)點(diǎn)8的平衡因子為2典尾， (二)和(四)的情況是節(jié)點(diǎn)8的平衡因子為-2役拴。這只是其中的一點(diǎn)區(qū)別，我們再觀察一下他們的子節(jié)點(diǎn)钾埂。(一)中節(jié)點(diǎn)4的平衡因子為1河闰、(二)中節(jié)點(diǎn)10的平衡因子為-1、(三)中節(jié)點(diǎn)4的平衡因子為-1褥紫、(四)中節(jié)點(diǎn)10的平衡因子為1.

以上只是我們找到的四種情況姜性，那么還有一點(diǎn)沒有關(guān)注的就是根節(jié)點(diǎn)的子節(jié)點(diǎn)，在我們這里就是節(jié)點(diǎn)10和節(jié)點(diǎn)4髓考，它們的平衡因子有可能為0嗎部念？在我們這里都不可能。原因就先拿(一)舉例：如果節(jié)點(diǎn)4的平衡因子為0，說明左右子樹高度相等儡炼，那么也就是在左節(jié)點(diǎn)1插入之前妓湘，已經(jīng)有右節(jié)點(diǎn)了，這是不可能的多柑，因?yàn)槿绻杏夜?jié)點(diǎn)則說明此時(shí)8這棵樹就已經(jīng)不再平衡了秆麸，而不會等到插入節(jié)點(diǎn)1的時(shí)候再去維護(hù)平衡

總結(jié)就是

序號	根節(jié)點(diǎn)的平衡因子	根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子
(一)	2	1
(二)	-2	-1
(三)	2	-1
(四)	-2	1

上面考慮的是根節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)的情況驻龟，同樣的根節(jié)點(diǎn)如果兩個(gè)子節(jié)點(diǎn)都存在凌蔬，是不是還有另外四種情況沒有考慮到？

第五種


      8              8

    /  \          /  \

    4  10    =>  4    10

  /              /

  2              2

                /

              1

這種情況下也是一直往左子樹添加译暂，不同的是根節(jié)點(diǎn)的右節(jié)點(diǎn)也存在象迎。此時(shí)根節(jié)點(diǎn)8的平衡因子為2，左節(jié)點(diǎn)4的平衡因子為2

第六種


      8              8

    /  \          /  \

    4  10    =>  4    10

          \              \

          12            12

                            \

                            14

這種情況下是一直往右子樹添加節(jié)點(diǎn)织中，同樣的是根節(jié)點(diǎn)8存在左節(jié)點(diǎn)层坠。此時(shí)根節(jié)點(diǎn)8的平衡因子為-2，右節(jié)點(diǎn)4的平衡因子為-2

第七種


      8              8

    /  \          /  \

    4  10    =>  4    10

  /                \

  2                  5

                      \

                      7

這種情況下是先往左子樹添加節(jié)點(diǎn)刁笙，之后向右子樹添加節(jié)點(diǎn)破花。此時(shí)根節(jié)點(diǎn)8的平衡因子為2，左節(jié)點(diǎn)4的平衡因子為-2

第八種


      8              8

    /  \          /  \

    4    11  =>  4    11

        /              /

        10            10

                      /   

                    9

這種情況下是先往右子樹添加節(jié)點(diǎn)疲吸，之后向左子樹添加節(jié)點(diǎn)座每。此時(shí)根節(jié)點(diǎn)8的平衡因子為-2，右節(jié)點(diǎn)11的平衡因子為2

從(五)到(八)這四種情況總結(jié)為：

序號	根節(jié)點(diǎn)的平衡因子	根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子
(五)	2	2
(六)	-2	-2
(七)	2	-2
(八)	-2	2

這會也考慮一下摘悴，根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子絕對值有沒有可能小于2峭梳，(五)是可以的，節(jié)點(diǎn)4的平衡因子也可以為1烦租，此時(shí)節(jié)點(diǎn)4也有兩個(gè)子節(jié)點(diǎn)延赌，這是不影響根節(jié)點(diǎn)8的平衡因子。同樣(六)的根節(jié)點(diǎn)的子節(jié)點(diǎn)也可以為-1叉橱，(七)的根節(jié)點(diǎn)的子節(jié)點(diǎn)可以為-1，(八)的根節(jié)點(diǎn)的子節(jié)點(diǎn)可以為1

現(xiàn)在把八種情況放到一塊觀察一下

序號	根節(jié)點(diǎn)的平衡因子	根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子
(一)	2	1
(二)	-2	-1
(三)	2	-1
(四)	-2	1
(五)	2	2或1
(六)	-2	-2或-1
(七)	2	-2或-1
(八)	-2	2或1

一起觀察的時(shí)候可以發(fā)現(xiàn)(一)是(五)的一種特殊情況者蠕，(二)是(六)的一種特殊情況 (三)是(七)的一種特殊情況窃祝，(四)是(八)的一種特殊情況

因此我們可以將二叉樹的不平衡條件分為四種

根節(jié)點(diǎn)平衡因子為2，根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子 > 0
根節(jié)點(diǎn)平衡因子為-2踱侣，根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子 < 0
根節(jié)點(diǎn)平衡因子為2粪小，根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子為< 0
根節(jié)點(diǎn)平衡因子為-2，根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子為 > 0

維持平衡的操作

平衡性是由平衡因子決定的抡句，而平衡因子又是通過節(jié)點(diǎn)的高度計(jì)算出來的探膊，因此需要修改一下Node構(gòu)造函數(shù)，初始默認(rèn)height為1


class Node {

  constructor(key, value) {

    this.key = key;

    this.value = value;

    this.left = null;

    this.right = null;

    this.height = 1;

  }

}

還需要兩個(gè)個(gè)方法待榔，那就是計(jì)算一個(gè)節(jié)點(diǎn)的高度和平衡因子


getHeight(node) {

  if (!node) return 0;

  return node.height

}

getBalanceFactory(node) {

  if (!node) return 0;

  return this.getHeight(node.left) - this.getHeight(node.right);

}

根據(jù)以上我們得到的四種不平衡的條件逞壁，于是就有四種不同的維護(hù)平衡的方法

右旋轉(zhuǎn)RR

右旋

此時(shí) 根節(jié)點(diǎn)平衡因子為2流济，根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子 > 0


// RR 右旋

if (balanceFactory > 1 && this.getBalanceFactory(node.left) > 0) {

  return this.rightRotate(node);

}

左旋轉(zhuǎn)LL

左旋

此時(shí)根節(jié)點(diǎn)平衡因子為-2，根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子 < 0


// LR 左旋

if (balanceFactory < -1 && this.getBalanceFactory(node.right) < 0) {

  return this.leftRotate(node);

}

LRR

左右旋

此時(shí)根節(jié)點(diǎn)平衡因子為2腌闯，根節(jié)點(diǎn)的子節(jié)點(diǎn)的平衡因子為< 0


// LRR 左右旋

if (balanceFactory > 1 && this.getBalanceFactory(node.left) < 0) {

  node.left = this.leftRotate(node.left);

  return this.rightRotate(node);

}

RLR

右左旋


// RLR 右左旋

if (balanceFactory < -1 && this.getBalanceFactory(node.right) > 0) {

  node.right = this.rightRotate(node.right);

  return this.leftRotate(node);

}

因此以上便是四種維護(hù)平衡的方法绳瘟，我們把它封裝為一個(gè)方法


keepBalance(node) {

  if (!node) return node;

  // 當(dāng)前節(jié)點(diǎn)的平衡因子

  const balanceFactory = this.getBalanceFactory(node);

  // 左節(jié)點(diǎn)的平衡因子

  const leftChildBalanceFactory = this.getBalanceFactory(node.left);

  // 右節(jié)點(diǎn)的平衡因子

  const rightChildBalanceFactory = this.getBalanceFactory(node.right);

  if (Math.abs(balanceFactory) > 1) {

    console.log(`balanceFactory: ${balanceFactory}`);

  }

  // RR 右旋

  if (balanceFactory > 1 && leftChildBalanceFactory > 0) {

    return this.rightRotate(node);

  }

  // LR 左旋

  if (balanceFactory < -1 && rightChildBalanceFactory < 0) {

    return this.leftRotate(node);

  }

  // LRR 左右旋

  if (balanceFactory > 1 && leftChildBalanceFactory < 0) {

    node.left = this.leftRotate(node.left);

    return this.rightRotate(node);

  }

  // RLR 右左旋

  if (balanceFactory < -1 && rightChildBalanceFactory > 0) {

    node.right = this.rightRotate(node.right);

    return this.leftRotate(node);

  }

  return node;

}

因此添加節(jié)點(diǎn)操作就需要改為：


insert(node, key, value) {

  if (!node) {

    this.size++;

    return new Node(key, value);

  }

  if (key > node.key) {

    node.right = this.insert(node.right, key, value);

  } else if (key < node.key) {

    node.left = this.insert(node.left, key, value);

  } else {

    node.value = value;

  }

  node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;

  return this.keepBalance(node)

}

同樣刪除操作也需要修改


_delete(node, key) {

  if (!node) {

    return null;

  }

  if (node.key > key) {

    node.left = this._delete(node.left, key);

  } else if (node.key < key) {

    node.right = this._delete(node.right, key);

  } else {

    if (!node.left) {

      this.size--;

      node = node.right;

    } else if (!node.right) {

      this.size--;

      node = node.left;

    } else {

      let successor;

      node.left = this._deleteMax(node.left, (node) => {

        successor = node;

      });

      successor.left = node.left;

      successor.right = node.right;

      node = successor;

    }

  }

  return this.keepBalance(node);

}

// 刪除子樹的最大值

_deleteMax(node, cb = () => {}) {

  if (!node) {

    cb(node);

    return null;

  }

  if (!node.right) {

    this.size--;

    cb(node);

    return node.left;

  }

  node.right = this._deleteMax(node.right, cb);

  return this.keepBalance(node);

}

以上便是整個(gè)AVL樹的內(nèi)容，通過以上也能看到AVL樹就是一棵二叉樹姿骏，它的查找糖声，添加，刪除分瘦，最壞情況下也是O(logN), 因此更加的平衡穩(wěn)定

最后編輯于：2019.08.24 12:45:54

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末蘸泻，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子嘲玫，更是在濱河造成了極大的恐慌悦施，老刑警劉巖，帶你破解...
沈念sama閱讀 212,542評論 6贊 493
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件趁冈，死亡現(xiàn)場離奇詭異歼争，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)渗勘，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,596評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門沐绒，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人旺坠，你說我怎么就攤上這事乔遮。” “怎么了取刃？”我有些...
開封第一講書人閱讀 158,021評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵蹋肮，是天一觀的道長。經(jīng)常有香客問我璧疗，道長坯辩，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,682評論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任崩侠，我火速辦了婚禮漆魔，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘却音。我一直安慰自己改抡，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,792評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布系瓢。她就那樣靜靜地躺著阿纤，像睡著了一般。火紅的嫁衣襯著肌膚如雪夷陋。梳的紋絲不亂的頭發(fā)上欠拾，一...
開封第一講書人閱讀 49,985評論 1贊 291
城市分裂傳說
那天胰锌，我揣著相機(jī)與錄音，去河邊找鬼清蚀。笑死匕荸，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的枷邪。我是一名探鬼主播榛搔，決...
沈念sama閱讀 39,107評論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼东揣！你這毒婦竟也來了践惑？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 37,845評論 0贊 268
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤嘶卧，失蹤者是張志新（化名）和其女友劉穎尔觉，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體芥吟，經(jīng)...
沈念sama閱讀 44,299評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡侦铜，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,612評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了钟鸵。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片钉稍。...
茶點(diǎn)故事閱讀 38,747評論 1贊 341
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖棺耍，靈堂內(nèi)的尸體忽然破棺而出贡未，到底是詐尸還是另有隱情，我是刑警寧澤蒙袍，帶...
沈念sama閱讀 34,441評論 4贊 333
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布俊卤，位于F島的核電站，受9級特大地震影響害幅，放射性物質(zhì)發(fā)生泄漏消恍。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 40,072評論 3贊 317
男人毒藥：我在死后第九天來索命
文/蒙蒙一以现、第九天我趴在偏房一處隱蔽的房頂上張望哺哼。院中可真熱鬧，春花似錦叼风、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,828評論 0贊 21
一樁弒父案无宿，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至枢里，卻和暖如春孽鸡，著一層夾襖步出監(jiān)牢的瞬間蹂午，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,069評論 1贊 267
情欲美人皮
我被黑心中介騙來泰國打工彬碱，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留豆胸，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,545評論 2贊 362
代替公主和親
正文我出身青樓巷疼，卻偏偏與公主長得像晚胡，于是被迫代替她去往敵國和親。傳聞我的和親對象是個(gè)殘疾皇子嚼沿，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,658評論 2贊 350