亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

在 Javascript 中實現由 Array 備份的 BST

在 Javascript 中實現由 Array 備份的 BST

千萬里不及你 2023-05-25 16:02:01
我正在嘗試使用數組實現 bst,但沒有成功:class BST {  constructor() {    this.array =[]    this.rootSet = false;    this.index = 0  }  getLeft(index) {    return (2 * index) + 1  }  getRight(index) {    return 2 * (index + 1)  }  getParent(index) {    return index >>> 1  }  insert(value) {    if (!this.rootSet) {      this.rootSet = true      this.array = [value]      this.index++;    } else {      // inserts recursively.      this.insertHelper(this.getParent(0), value);    }  }    // helper function to insert recursively.  insertHelper(index, value) {    if (value < this.array[index] && this.array[this.getLeft(index)] === undefined) {      this.array[this.getLeft(index)] = value    } else if (value >= this.array[index] && this.array[this.getRight(index)] === undefined) {      this.array[this.getRight(index)] = value    } else {      if (value < this.array[index]) {        this.insertHelper(this.getLeft(index), value);      } else {        this.insertHelper(this.getRight(index), value);      }    }  }}我嘗試了以下內容:a.insert(2)a.insert(0)a.insert(3)a.insert(10)a.insert(30)a.array // [2, 0, 3, empty × 3, 10, empty × 7, 30]a.array看起來不正確。不知道我在哪里犯了錯誤。
查看完整描述

2 回答

?
POPMUISE

TA貢獻1765條經驗 獲得超5個贊

你的結果對我來說是正確的。稀疏性的原因是這是二叉樹基于數組的支持結構的典型特征。如果樹不完整,則由于空元素表示未填充的子樹,因此存在浪費的條目。由于 BST 通常需要平衡以保持最佳時間復雜度,因此基于鏈接節點的方法是典型的解決方案,它使旋轉和平衡更容易。

通常,數組支持結構用于二進制堆,它受益于數組在堆分配節點和指針上的內存布局和速度;堆操作不允許稀疏性,并且很容易使用您在此處使用的相同父子關系在線性結構中進行推理。

話雖如此,您可以大大簡化代碼:

class BST {

? constructor() {

? ? this.array = [];

? }


? insert(value, ix=0) {

? ? if (this.array[ix] === undefined) {

? ? ? this.array[ix] = value;

? ? }

? ? else if (value < this.array[ix]) {

? ? ? this.insert(value, ix * 2 + 1);

? ? }

? ? else {

? ? ? this.insert(value, ix * 2 + 2);

? ? }

? }

}


/*

? ? 2

? ?/ \

? 0? ?3

? ? ? ?\

? ? ? ? 10

? ? ? ? ?\

? ? ? ? ? 30

*/

const bst = new BST();

[2, 0, 3, 10, 30].forEach(e => bst.insert(e));

console.log(bst.array);


查看完整回答
反對 回復 2023-05-25
?
叮當貓咪

TA貢獻1776條經驗 獲得超12個贊

我沒有檢查代碼,但結果對我來說是正確的。數組中的第一項是根。然后接下來的兩個是等級 1 節點然后接下來的 4 個是等級 2 節點。那么接下來的 8 個是 rank 4 節點 你的結果應該是


http://img1.sycdn.imooc.com//646f165a00016cf201100130.jpg

查看完整回答
反對 回復 2023-05-25
  • 2 回答
  • 0 關注
  • 148 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號