二叉排序樹

Soarkey 發(fā)布于2019-08-23 14:14 / 675人閱讀

摘要：節(jié)點(diǎn)的構(gòu)造函數(shù)默認(rèn)為其初始化都是。二叉排序樹插入插入節(jié)點(diǎn)只要遵循一個(gè)原則就好大與就向中插入，小于就向插入。初始化數(shù)據(jù)樹現(xiàn)在來試試實(shí)例化一個(gè)來看看效果。

JavaScript 數(shù)據(jù)結(jié)構(gòu)篇之 BST 前言

有段時(shí)間沒有寫文章了，整個(gè)人感覺變得有點(diǎn)懶散了，大家可不要向我一樣哦~
今天開始 seaconch 打算開始記錄 JavaScript 數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)經(jīng)歷。
至此，開始。

課本：《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 (第2版)》

術(shù)語：

BST (binary sort tree)

LST (left subtree)

RST (right subtree)

OUTLINE

特性

定義

插入

查找

最大

最小

移除

遍歷

AVL

源碼

特性

BST 有如下特性：

若 LST 不為空，則 LST 所有節(jié)點(diǎn)值都小于它的根節(jié)點(diǎn)值

若 RST 不為空，則 RST 所有節(jié)點(diǎn)值都大于它的根節(jié)點(diǎn)值

左右子樹也都是 BST

沒有重復(fù)鍵

定義

為了存儲(chǔ) BST，我們先定義一個(gè) Node 類型，存儲(chǔ)各個(gè)節(jié)點(diǎn)。

Node 節(jié)點(diǎn)的構(gòu)造函數(shù)默認(rèn)為其初始化 Subtree 都是 null。

/**
 * 節(jié)點(diǎn)
 */
class Node {

  constructor (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }

}

然后是 BST

BST 的類型我們只初始化了一個(gè)根節(jié)點(diǎn) root。

/**
 * 二叉排序樹
 */
class BinarySearchTree {

  constructor() {
    this.root = null;
  }

}

插入

插入節(jié)點(diǎn)只要遵循一個(gè)原則就好：大與 node.key 就向 node.right 中插入，小于 node.key 就向 node.left 插入。

首先定義私有函數(shù)。

const insertNode = Symbol("insertNode");

  /**
   * 插入節(jié)點(diǎn)
   */
  insert(key) {

    let newNode = new Node(key);
    if (this.root === null) this.root = newNode;
    else this[insertNode](this.root, newNode);

  }

  /**
   * 插入節(jié)點(diǎn)
   * @param {當(dāng)前節(jié)點(diǎn)} node 
   * @param {新節(jié)點(diǎn)} newNode 
   */
  [insertNode] (node, newNode) {

    if (newNode.key < node.key) {

      if (node.left === null) node.left = newNode;
      else this[insertNode](node.left, newNode);

    } else {

      if (node.right === null) node.right = newNode;
      else this[insertNode](node.right, newNode);

    }
  }

這里稍微的說明一下，之所以寫成私有函數(shù)，無非就是為了不希望外部看到這些沒必要的。

其實(shí)東西多了感覺也會(huì)亂糟糟的...

接下來為了查看一下效果，我們來寫一個(gè)初始化 BST 的函數(shù)。

我們的目標(biāo)是初始化一個(gè)這樣的 BST。

/**
 * 初始化數(shù)據(jù)
 * @param {樹} tree 
 */
function initialization(tree) {

  let treeKeys = [50, 25, 13, 5, 19, 35, 28, 49, 75, 64, 56, 74, 85, 79, 99];

  treeKeys.forEach( key => tree.insert(key) )

}

現(xiàn)在來試試實(shí)例化一個(gè) BST 來看看效果。

let tree = new BinarySearchTree();

initialization(tree);

console.log(tree.root);

打印效果如圖

查找

由:

若 LST 不為空，則 LST 所有節(jié)點(diǎn)值都 小 于它的根節(jié)點(diǎn)值
若 RST 不為空，則 RST 所有節(jié)點(diǎn)值都 大 于它的根節(jié)點(diǎn)值
左右子樹也都是 BST

因此我們可以相對(duì)快速的查找元素。

定義私有函數(shù)

const searchNode = Symbol("searchNode");

  /**
   * 是否存在目標(biāo) key
   */
  existKey(key) {
    return this[searchNode](this.root, key);
  }

  /**
   * 
   * @param {當(dāng)前節(jié)點(diǎn)} node 
   * @param {key} key 
   */
  [searchNode] (node, key) {

    if (node === null) return false;
    
    if (key < node.key) return this[searchNode](node.left, key);
    
    else if (key > node.key) return this[searchNode](node.right, key);
    
    else return true;
    
  }

我們的思路是這樣的：

如果要查找的 key值小于當(dāng)前節(jié)點(diǎn)的 key值，則向 LST 繼續(xù)查找;
如果要查找的 key值大于當(dāng)前節(jié)點(diǎn)的 key值，則向 RST 繼續(xù)查找;
如果要查找的 key值等于當(dāng)前節(jié)點(diǎn)的 key值，則返回 true

運(yùn)行效果如下：

最大值

由：

若 RST 不為空，則 RST 所有節(jié)點(diǎn)值都 大 于它的根節(jié)點(diǎn)值
左右子樹也都是 BST

我們可以求得最大值

很明顯是這樣的

代碼如下

定義私有函數(shù)

const maxNode = Symbol("maxNode");

  /**
   * 獲取最大節(jié)點(diǎn) key
   */
  max() {
    return this[maxNode](this.root);
  }

  /**
   * 獲取最大節(jié)點(diǎn) key
   * @param {節(jié)點(diǎn)} node 
   */
  [maxNode] (node) {

    if (node) {
    
      while (node && node.right !== null) {
      
        node = node.right;
      }
      return node.key;
    }
    return null;
  }

輸出結(jié)果為：99

最小值

獲取最小值的方法與最大值類似，只是方向變了一下

定義私有函數(shù)

const minNode = Symbol("minNode");

  /**
   * 獲取最小節(jié)點(diǎn) key
   */
  min() {
    return this[minNode](this.root);
  }

  /**
   * 獲取最小節(jié)點(diǎn) key
   * @param {節(jié)點(diǎn)} node 
   */
  [minNode] (node) {

    if (node) {
    
      while (node && node.left !== null) {
      
        node = node.left;
      }
      return node.key;
    }
    return null;
  }

運(yùn)行結(jié)果自然是：5

移除

移除相對(duì)來說復(fù)雜一點(diǎn)，因?yàn)榧偃缥覀円瞥氖且粋€(gè)父節(jié)點(diǎn)，那他們的子節(jié)點(diǎn)怎么辦？

當(dāng)然也是有相應(yīng)的應(yīng)對(duì)措施的。

對(duì)于沒有 subtree 的 node 來說，只需要把他們修改為 null 即可

對(duì)于存在 subtree 的 node 來說，就要考慮所有情況分別處理

當(dāng) LST === null 時(shí) => RST 上前來頂替待刪除節(jié)點(diǎn)的位置

當(dāng) RST === null 時(shí) => LST 上前來頂替待刪除節(jié)點(diǎn)的位置

當(dāng) LST && RST 都不是 null 時(shí)，由 RST 中最小節(jié)點(diǎn)上前來頂起待刪除節(jié)點(diǎn)的位置

圖例說明：

1. LST 等于 null

2. RST 等于 null

3. LST 和 RST 都不等于 null

定義私有函數(shù)

const removeNode = Symbol("removeNode");
const findMinNode = Symbol("findMinNode");

  /**
   * 刪除節(jié)點(diǎn)
   */
  remove(key) {
    this[removeNode](this.root, key);
  }

  /**
   * 刪除節(jié)點(diǎn)，返回刪除后的 tree
   * @param {當(dāng)前節(jié)點(diǎn)} node 
   * @param {key} key 
   */
  [removeNode] (node, key) {

    if (node === null) /** the tree is empty or does not have this key who you want to remove. */ return null;

    if (key < node.key) /** the key of currrent node is bigger than target key. */ {

      node.left = this[removeNode](node.left, key);
      return node;

    } else if (key > node.key) /** smaller */ {

      node.right = this[removeNode](node.right, key);
      return node;

    } else /** 相等 */ {

      if (node.left === null && node.right === null) {
        /**
         * 當(dāng)前節(jié)點(diǎn)沒有左右節(jié)點(diǎn)，可以放心刪除
         */
        node = null;
        return node;
      }

      /**
       * 當(dāng)前節(jié)點(diǎn)有一個(gè)節(jié)點(diǎn)，讓子節(jié)點(diǎn)`頂`上來
       */
      if (node.left === null) {
        
        node = node.right;
        return node

      } else if (node.right === null) {

        node = node.left;
        return node;

      }

      /**
       * 來到這里代表當(dāng)前節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
       */
      let aux = this[findMinNode](node.right); // 找到右節(jié)點(diǎn)的最小節(jié)點(diǎn)
      node.key = aux.key; // 把要?jiǎng)h除的節(jié)點(diǎn)的 key 覆蓋為右側(cè)最小節(jié)點(diǎn) key
      node.right = this[removeNode](node.right, aux.key); // 重構(gòu) right side tree (刪除上面找到的 aux 節(jié)點(diǎn))
      return node;
    }
  }

  /**
   * 返回目標(biāo)節(jié)點(diǎn)分支下最小節(jié)點(diǎn)
   * @param {目標(biāo)節(jié)點(diǎn)} node 
   */
  [findMinNode] (node) {

    while (node && node.left !== null) {
    
      node = node.left;
    }
    return node;
  }

好了，現(xiàn)在來一起運(yùn)行一下，看一下效果吧

遍歷

遍歷 BST 一般有三種方式：

- 先序
- 中序
- 后序

seaconch 畫了 3 張圖幫助理解:

先序遍歷：

中序遍歷：

后序遍歷：

這里我們只演示中序遍歷的代碼

中序遍歷

所謂前序，中序，后序一般都是指具體操作的位置，在這里表示回調(diào)函數(shù)的位置

定義私有函數(shù)

const inOrderTraverseNode = Symbol("inOrderTraverseNode");

  /**
   * 中序遍歷，標(biāo)準(zhǔn)名稱為: `inOrderTraverse`
   */
  middleOrderTraverse(cb) {
    this[inOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {當(dāng)前節(jié)點(diǎn)} node 
   * @param {回調(diào)} cb 
   */
  [inOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[inOrderTraverseNode](node.left, cb);
      cb(node.key); // 回調(diào)在中間就是中序
      this[inOrderTraverseNode](node.right, cb);
    }
  }

結(jié)果是按照順序輸出了各個(gè)節(jié)點(diǎn)的 key:

AVL

Adelson-Velskii-Landi(AVL) 自平衡樹

BST 有一定的問題，比如當(dāng)你添加了很多大于 root 的元素，而只添加了很少的小于 root 的元素，那么 BST 將嚴(yán)重失衡，最直觀的一個(gè)說明就是，獲取最大值的速度明顯沒有獲取最小值的速度快。

AVL 樹就是為了解決 BST 失衡的問題

AVL 在每次添加或刪除元素的時(shí)候，嘗試自平衡，使左右子樹高度差 >= 1

(hr(右子樹高度) - hl(左子樹高度) in (-1, 0, 1))

源碼

源碼如下：

/**
 * 節(jié)點(diǎn)
 */
class Node {

  constructor (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

const insertNode = Symbol("insertNode");
const removeNode = Symbol("removeNode");
const findMinNode = Symbol("findMinNode");
const minNode = Symbol("minNode");
const maxNode = Symbol("maxNode");
const searchNode = Symbol("searchNode");
const inOrderTraverseNode = Symbol("inOrderTraverseNode");
const preOrderTraverseNode = Symbol("preOrderTraverseNode");
const postOrderTraverseNode = Symbol("postOrderTraverseNode");
/**
 * 二叉排序樹
 */
class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  /**
   * 插入節(jié)點(diǎn)
   */
  insert(key) {

    let newNode = new Node(key);
    if (this.root === null) this.root = newNode;
    else this[insertNode](this.root, newNode);

  }

  /**
   * 插入節(jié)點(diǎn)
   * @param {當(dāng)前節(jié)點(diǎn)} node 
   * @param {新節(jié)點(diǎn)} newNode 
   */
  [insertNode] (node, newNode) {

    if (newNode.key < node.key) {

      if (node.left === null) node.left = newNode;
      else this[insertNode](node.left, newNode);

    } else {

      if (node.right === null) node.right = newNode;
      else this[insertNode](node.right, newNode);

    }
  }

  /**
   * 刪除節(jié)點(diǎn)
   */
  remove(key) {
    this[removeNode](this.root, key);
  }

  /**
   * 刪除節(jié)點(diǎn)，返回刪除后的 tree
   * @param {當(dāng)前節(jié)點(diǎn)} node 
   * @param {key} key 
   */
  [removeNode] (node, key) {

    if (node === null) /** the tree is empty or does not have this key who you want to remove. */ return null;

    if (key < node.key) /** the key of currrent node is bigger than target key. */ {

      node.left = this[removeNode](node.left, key);
      return node;

    } else if (key > node.key) /** smaller */ {

      node.right = this[removeNode](node.right, key);
      return node;

    } else /** 相等 */ {

      if (node.left === null && node.right === null) {
        /**
         * 當(dāng)前節(jié)點(diǎn)沒有左右節(jié)點(diǎn)，可以放心刪除
         */
        node = null;
        return node;
      }

      /**
       * 當(dāng)前節(jié)點(diǎn)有一個(gè)節(jié)點(diǎn)，讓子節(jié)點(diǎn)`頂`上來
       */
      if (node.left === null) {
        
        node = node.right;
        return node

      } else if (node.right === null) {

        node = node.left;
        return node;

      }

      /**
       * 來到這里代表當(dāng)前節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
       */
      let aux = this[findMinNode](node.right); // 找到右節(jié)點(diǎn)的最小節(jié)點(diǎn)
      node.key = aux.key; // 把要?jiǎng)h除的節(jié)點(diǎn)的 key 覆蓋為右側(cè)最小節(jié)點(diǎn) key
      node.right = this[removeNode](node.right, aux.key); // 重構(gòu) right side tree (刪除上面找到的 aux 節(jié)點(diǎn))
      return node;
    }
  }

  /**
   * 返回目標(biāo)節(jié)點(diǎn)分支下最小節(jié)點(diǎn)
   * @param {目標(biāo)節(jié)點(diǎn)} node 
   */
  [findMinNode] (node) {

    while (node && node.left !== null) {

      node = node.left;
    }
    return node;
  }

  /**
   * 獲取最小節(jié)點(diǎn) key
   */
  min() {
    return this[minNode](this.root);
  }

  /**
   * 獲取最小節(jié)點(diǎn) key
   * @param {節(jié)點(diǎn)} node 
   */
  [minNode] (node) {

    if (node) {

      while (node && node.left !== null) {

        node = node.left;
      }
      return node.key;
    }
    return null;
  }

  /**
   * 獲取最大節(jié)點(diǎn) key
   */
  max() {
    return this[maxNode](this.root);
  }

  /**
   * 獲取最大節(jié)點(diǎn) key
   * @param {節(jié)點(diǎn)} node 
   */
  [maxNode] (node) {

    if (node) {

      while (node && node.right !== null) {

        node = node.right;
      }
      return node.key;
    }
    return null;
  }

  /**
   * 是否存在目標(biāo) key
   */
  existKey(key) {
    return this[searchNode](this.root, key);
  }

  /**
   * 
   * @param {當(dāng)前節(jié)點(diǎn)} node 
   * @param {key} key 
   */
  [searchNode] (node, key) {

    if (node === null) return false;

    if (key < node.key) return this[searchNode](node.left, key);

    else if (key > node.key) return this[searchNode](node.right, key);

    else return true;

  }

  /**
   * 中序遍歷，標(biāo)準(zhǔn)名稱為: `inOrderTraverse`
   */
  middleOrderTraverse(cb) {
    this[inOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {當(dāng)前節(jié)點(diǎn)} node 
   * @param {回調(diào)} cb 
   */
  [inOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[inOrderTraverseNode](node.left, cb);
      cb(node.key); // 回調(diào)在中間就是中序
      this[inOrderTraverseNode](node.right, cb);
    }
  }

  preOrderTraverse(cb) {
    this[preOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {*} node 
   * @param {*} cb 
   */
  [preOrderTraverseNode] (node, cb) {
    if (node !== null) {
      cb(node.key); // 回調(diào)在前
      this[preOrderTraverseNode](node.left, cb);
      this[preOrderTraverseNode](node.right, cb);
    }
  }

  postOrderTraverse(cb) {
    this[postOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {*} node 
   * @param {*} cb 
   */
  [postOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[postOrderTraverseNode](node.left, cb);
      this[postOrderTraverseNode](node.right, cb);
      cb(node.key); // 回調(diào)在后
    }
  }
}


/**
 * 初始化數(shù)據(jù)
 * @param {樹} tree 
 */
function initialization(tree) {

  let treeKeys = [50, 25, 13, 5, 19, 35, 28, 49, 75, 64, 56, 74, 85, 79, 99];

  treeKeys.forEach( key => tree.insert(key) )

}

let tree = new BinarySearchTree();

initialization(tree);

// tree.preOrderTraverse(v => console.log(v));
tree.middleOrderTraverse(v => console.log(v));
// tree.postOrderTraverse(v => console.log(v));

// console.log("the min node.key is: ", tree.min());
// console.log("the max node.key is: ", tree.max());

// let tempKey = 49;
// console.log("the key of [", tempKey, "]", tree.existKey(tempKey) ? "real" : "not", "exist.");

// tree.remove(49)
// console.log("remove key [", tempKey, "]");

// console.log("the key of [", tempKey, "]", tree.existKey(tempKey) ? "real" : "not", "exist.");

continue...

GPU云服務(wù)器云服務(wù)器二叉樹排序樹規(guī)則二叉排序樹刪除二叉排序樹c語言二叉查找樹

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/100324.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Soarkey

男|高級(jí)講師

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

TA的文章

tensorflow1.4

閱讀 2156·2023-04-25 19:03
曙光發(fā)布“城市云腦”系列解決方案十大場(chǎng)景全賦能智慧城市_云資訊

閱讀 1324·2021-10-14 09:42
云主機(jī)3m帶寬支持多少人在線-云服務(wù)器上5M帶寬大概支持多少人同時(shí)在線？

閱讀 3517·2021-09-22 15:16
?算法入門?《二叉樹 - 二叉搜索樹》簡(jiǎn)單05 —— LeetCode 897. 遞增順序搜索樹

閱讀 1070·2021-09-10 10:51
硬件創(chuàng)業(yè)：智能硬件產(chǎn)品詳細(xì)開發(fā)指南

閱讀 1749·2021-09-06 15:00
淺談pc和移動(dòng)端的響應(yīng)式

閱讀 2474·2019-08-30 15:55
css3過渡

閱讀 542·2019-08-29 16:22
大話Redux

閱讀 942·2019-08-26 13:49

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

二叉排序樹

相關(guān)文章

二叉樹遍歷

JS實(shí)現(xiàn)二叉排序樹

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 非線性表中的樹、堆是干嘛用的？其數(shù)據(jù)結(jié)構(gòu)是怎樣的？

堆排序就這么簡(jiǎn)單

用JS實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)----排序二叉樹

發(fā)表評(píng)論

0條評(píng)論

Soarkey

男|高級(jí)講師

TA的文章

tensorflow1.4

曙光發(fā)布“城市云腦”系列解決方案十大場(chǎng)景全賦能智慧城市_云資訊

云主機(jī)3m帶寬支持多少人在線-云服務(wù)器上5M帶寬大概支持多少人同時(shí)在線？

?算法入門?《二叉樹 - 二叉搜索樹》簡(jiǎn)單05 —— LeetCode 897. 遞增順序搜索樹

硬件創(chuàng)業(yè)：智能硬件產(chǎn)品詳細(xì)開發(fā)指南

淺談pc和移動(dòng)端的響應(yīng)式

css3過渡

大話Redux

最新活動(dòng)

資訊專欄INFORMATION COLUMN

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

二叉排序樹

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

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