JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（十）自平衡樹

msup 發(fā)布于2019-08-26 10:58 / 1572人閱讀

摘要：為了解決這類問題，我們進(jìn)行自平衡樹的學(xué)習(xí)。自平衡樹常見有兩種樹和紅黑樹。自平衡樹準(zhǔn)備知識節(jié)點(diǎn)的高度和平衡因子節(jié)點(diǎn)高度從節(jié)點(diǎn)到任意子節(jié)點(diǎn)的彼岸的最大值。

前面介紹了二叉樹和二叉樹搜索樹的創(chuàng)建和使用，接下來我們繼續(xù)學(xué)習(xí)關(guān)于樹的更多知識。
BST存在一個(gè)問題，就是當(dāng)我們多次添加節(jié)點(diǎn)數(shù)，有可能造成一種情況，樹的一條邊可能會(huì)非常深，有非常多的層，而另一條分支卻只有幾層。當(dāng)我們需要進(jìn)行添加、移除和搜索某一節(jié)點(diǎn)時(shí)，可能會(huì)引起一些性能問題。為了解決這類問題，我們進(jìn)行自平衡樹的學(xué)習(xí)。自平衡樹常見有兩種：AVL樹和紅黑樹。

自平衡樹 準(zhǔn)備知識 節(jié)點(diǎn)的高度和平衡因子

節(jié)點(diǎn)高度：從節(jié)點(diǎn)到任意子節(jié)點(diǎn)的彼岸的最大值。這個(gè)相對來說容易理解。那么獲得節(jié)點(diǎn)高度的代碼實(shí)現(xiàn)如下：

getNodeHeight(node) {
    if (node == null) {
      return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
  }

平衡因子：每個(gè)節(jié)點(diǎn)左子樹高度和右子樹高度的差值。該值為0 、 -1、 1 時(shí)則為正常值，說明該二叉樹已經(jīng)平衡。若果該值不是這三個(gè)值之一，則需要平衡該樹。遵循計(jì)算一個(gè)節(jié)點(diǎn)的平衡因子并返回其值的代碼如下：

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};
getBalanceFactor(node) {
    const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDifference) {
      case -2:
        return BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.UNBALANCED_LEFT;
      default:
        return BalanceFactor.BALANCED;
    }
  }

AVL樹

AVL樹是一種自平衡樹，添加或移除節(jié)點(diǎn)時(shí)，AVL會(huì)嘗試保持自平衡，也就是會(huì)可能嘗試轉(zhuǎn)換為完全樹。接下來介紹平衡樹進(jìn)行自平衡的操作，AVL旋轉(zhuǎn)

AVL旋轉(zhuǎn)

在對AVL進(jìn)行添加或者移除節(jié)點(diǎn)后，我們需要計(jì)算節(jié)點(diǎn)的高度并驗(yàn)證是否需要進(jìn)行平衡。旋轉(zhuǎn)操作分為單旋轉(zhuǎn)和雙旋轉(zhuǎn)兩種。

左-左LL（向右的單旋轉(zhuǎn)）

/**
   * Left left case: rotate right
   *
   *       b                           a
   *      /                          / 
   *     a   e -> rotationLL(b) ->   c   b
   *    /                              / 
   *   c   d                           d   e
   *
   * @param node Node
   */
rotationLL(node){
    const tmp = node.right;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
}

右-右RR（向左的單旋轉(zhuǎn)）

/**
   * Right right case: rotate left
   *
   *     a                              b
   *    /                             / 
   *   c   b   -> rotationRR(a) ->    a   e
   *      /                         / 
   *     d   e                      c   d
   *
   * @param node Node
   */
  rotationLL(node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
  }

左-右（LR）：向右的雙旋轉(zhuǎn)

/**
   * Left right case: rotate left then right
   * @param node Node
   */
  rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
  }

右-左（RL）：向左的雙旋轉(zhuǎn)

/**
   * Right left case: rotate right then left
   * @param node Node
   */
  rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rotationRR(node);
  }

完成平衡操作（旋轉(zhuǎn)）的學(xué)習(xí)后，我們接下來完善一下AVL樹添加或者移除節(jié)點(diǎn)的操作

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

insert(key) {
    this.root = this.insertNode(this.root, key);
  }

  insertNode(node, key) {
    if (node == null) {
      return new Node(key);
    } if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, key);
    } else {
      return node; // duplicated key
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
        // Left left case
        node = this.rotationLL(node);
      } else {
        // Left right case
        return this.rotationLR(node);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
        // Right right case
        node = this.rotationRR(node);
      } else {
        // Right left case
        return this.rotationRL(node);
      }
    }
    return node;
  }

移除節(jié)點(diǎn)

 removeNode(node, key) {
    node = super.removeNode(node, key); // {1}
    if (node == null) {
      return node;
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      // Left left case
      if (
        this.getBalanceFactor(node.left) === BalanceFactor.BALANCED
        || this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
      ) {
        return this.rotationLL(node);
      }
      // Left right case
      if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationLR(node.left);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      // Right right case
      if (
        this.getBalanceFactor(node.right) === BalanceFactor.BALANCED
        || this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
      ) {
        return this.rotationRR(node);
      }
      // Right left case
      if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationRL(node.right);
      }
    }
    return node;
  }
}

以上就是關(guān)于AVL樹基礎(chǔ)知識的學(xué)習(xí)，接下來我們介紹另一種平衡樹——紅黑樹。
和AVL樹一樣，紅黑樹也是一個(gè)自平衡二叉樹。紅黑樹本質(zhì)上也是AVL樹，但可以包含多次插入和刪除。在紅黑樹中，每個(gè)節(jié)點(diǎn)都遵循以下規(guī)則：

顧名思義，每個(gè)節(jié)點(diǎn)不是紅的就是黑的；

樹的根節(jié)點(diǎn)就是黑的；

所有葉節(jié)點(diǎn)都是黑的；

如果一個(gè)節(jié)點(diǎn)是紅的，那么他的兩個(gè)子節(jié)點(diǎn)都是黑的

不能有兩個(gè)相鄰的紅節(jié)點(diǎn)，一個(gè)紅節(jié)點(diǎn)不能有紅的父節(jié)點(diǎn)或子節(jié)點(diǎn)；

從給定的節(jié)點(diǎn)到他的后代節(jié)點(diǎn)（NULL葉節(jié)點(diǎn)）的所有路徑包含相同數(shù)量的黑色節(jié)點(diǎn)。

紅黑樹 創(chuàng)建紅黑樹的骨架

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};
//定義顏色類
const Colors = {
  RED:"red",
  BLACK:"black"
};
//創(chuàng)建紅黑樹的節(jié)點(diǎn)類型
class RedBlackNode extends Node{
  constructor(key){
    super(key);
    this.key = key;
    this.color = Colors.RED;
    this.parent = null;
  }
  isRed(){
    return this.color === Colors.RED;
  }
};
class RedBlackTree extends BinarySearchTree{
  constructor(compareFn = defaultCompare){
    super(compareFn);
    this.compareFn = compareFn;
    this.root = null;
  };
}

旋轉(zhuǎn)操作

向右單旋轉(zhuǎn)

 //rotationLL
  static rotationLL(node){
    const tmp = node.left;
    node.left = tmp.right;
    if(tmp.right && tmp.right.key){
      tmp.right.parent = node;
    }
    tmp.right.parent = node.parent;
    if (!node.parent){
      this.root = tmp;
    }else{
      if(node === node.parent.left){
        node.parent.left = tmp;
      }else{
        node.parent.right = tmp;
      }
      tmp.right = node;
      node.parent = tmp;
    }
  };

向左單旋轉(zhuǎn)

//rotationRR
  static rotationRR(node){
    const tmp = node.right;
    node.right = tmp.left;
    if (tmp.left && tmp.left.key){
      tmp.left.parent = node;
    }
    tmp.parent = node.parent;
    if (!node.parent){
      this.root = tmp;
    }else{
      if(node === node.parent.left){
        node.parent.left = tmp;
      }else{
        node.parent.right = tmp;
      }
    }
    tmp.left = node;
    node.parent = tmp;
  }

驗(yàn)證節(jié)點(diǎn)顏色屬性

 //插入節(jié)點(diǎn)后驗(yàn)證紅黑樹的屬性
  static fixTreeProperties(node){
    while (node && node.parent && node.parent.color.isRed() && node.color !== Colors.BLACK){
      let parent = node.parent;
      const grandParent = parent.parent;
      //case A:父節(jié)點(diǎn)是左側(cè)子節(jié)點(diǎn)
      if (grandParent && grandParent.left === parent){
        const uncle = grandParent.right;
        //case 1A：叔節(jié)點(diǎn)也是紅色——只需要重新填色
        if (uncle && uncle.color === Colors.RED){
          grandParent.color = Colors.RED;
          parent.color  = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        }else{
          // case 2A:節(jié)點(diǎn)是右側(cè)子節(jié)點(diǎn)——右旋轉(zhuǎn)
          if (node === parent.left){
            RedBlackTree.rotationRR(parent);
            node = parent;
            parent = node.parent;
          }
          //case 3A:子節(jié)點(diǎn)是左側(cè)子節(jié)點(diǎn)——左旋轉(zhuǎn)
          else if(node === parent.right){
            RedBlackTree.rotationRR(grandParent);
            parent.color = Colors.BLACK;
            grandParent.color = Colors.RED;
            node = parent;
          }
        }
      }
      //case B:父節(jié)點(diǎn)是右側(cè)子節(jié)點(diǎn)
      else{
        const uncle = grandParent.left;
        //case1B:叔節(jié)點(diǎn)是紅色——只需要重新填色
        if(uncle && uncle.color === Colors.RED){
          grandParent.color = Colors.RED;
          parent.color = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        }
        //case2B:節(jié)點(diǎn)是左側(cè)子節(jié)點(diǎn)—右旋轉(zhuǎn)
        if (node === parent.left){
          RedBlackTree.rotationLL(parent);
          node = parent;
          parent = node.parent;
        }
        //case3B:節(jié)點(diǎn)是右側(cè)子節(jié)點(diǎn)——左旋轉(zhuǎn)
        else if(node === parent.right){
          RedBlackTree.rotationRR(grandParent);
          parent.color = Colors.BLACK;
          grandParent.color = Colors.RED;
          node = parent;
        }
      }
      this.root.color = Colors.BLACK;
    }
  }

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

 //向紅黑樹插入新節(jié)點(diǎn)
  insertNode(node,key){
    if(this.compareFn(key,node.key) === Compare.LESS_THAN){
      if(node.left === null){
        node.left = new RedBlackNode(key);
        node.left.parent = node;
        return node.left;
      }
      else{
        return this.insertNode(node.left,key);
      }
    }
    else if(node.right === null){
      node.right = new RedBlackNode(key);
      node.right.parent = node;
      return node.right;
    }
  };
  insert(key) {
    if (this.root === null){
      this.root = new RedBlackNode(key);
      this.root.color = Colors.BLACK;
    }else{
      const newNode = this.insertNode(this.root, key);
      RedBlackTree.fixTreeProperties(newNode);
    }
  };

云服務(wù)器 GPU云服務(wù)器平衡樹 python 平衡樹平衡二叉樹課程設(shè)計(jì) 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘決策樹

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/106920.html

發(fā)表評論

登陸后可評論

0條評論

msup

男|高級講師

我要關(guān)注我要私信

TA的文章

如何在godaddy購買主機(jī)-godaddy主機(jī)怎么樣？

閱讀 1116·2021-09-22 15:37
OpenInfra 基金會(huì)已與微軟簽署協(xié)議，成為最新的白金會(huì)員

閱讀 1143·2021-09-13 10:27
Aperture：$10.3/月/1GB內(nèi)存/8GB空間/600GB流量/150Mbps-500Mb

閱讀 2489·2021-08-25 09:38
JS 中 __proto__ 和 prototype 存在的意義是什么？

閱讀 2458·2019-08-26 11:42
現(xiàn)代CSS進(jìn)化史

閱讀 1538·2019-08-26 11:39
JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（十）自平衡樹

閱讀 1573·2019-08-26 10:58
vue-video-player使用筆記（兼容m3u8）

閱讀 2333·2019-08-26 10:56
結(jié)合作用域，執(zhí)行上下文圖解閉包

閱讀 2581·2019-08-23 18:08

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（十）自平衡樹

左-左LL（向右的單旋轉(zhuǎn)）

右-右RR（向左的單旋轉(zhuǎn)）

左-右（LR）：向右的雙旋轉(zhuǎn)

右-左（RL）：向左的雙旋轉(zhuǎn)

向右單旋轉(zhuǎn)

向左單旋轉(zhuǎn)

相關(guān)文章

**學(xué)習(xí)*JavaScript**數(shù)據(jù)結(jié)構(gòu)*與算法 — AVL樹**

**《學(xué)習(xí)*JavaScript**數(shù)據(jù)結(jié)構(gòu)*與算法》（第8章）（平衡二叉樹代碼實(shí)現(xiàn)）**

數(shù)據(jù)結(jié)構(gòu)與算法——常用高級數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹算法

PHP面試：說說你理解的二叉樹吧

發(fā)表評論

0條評論

msup

男|高級講師

TA的文章

如何在godaddy購買主機(jī)-godaddy主機(jī)怎么樣？

OpenInfra 基金會(huì)已與微軟簽署協(xié)議，成為最新的白金會(huì)員

Aperture：$10.3/月/1GB內(nèi)存/8GB空間/600GB流量/150Mbps-500Mb

JS 中 proto 和 prototype 存在的意義是什么？

現(xiàn)代CSS進(jìn)化史