第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

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

在 Javascript 中實(shí)現(xiàn)由 Array 備份的 BST

在 Javascript 中實(shí)現(xiàn)由 Array 備份的 BST

千萬里不及你 2023-05-25 16:02:01
我正在嘗試使用數(shù)組實(shí)現(xiàn) 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);      }    }  }}我嘗試了以下內(nèi)容: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看起來不正確。不知道我在哪里犯了錯(cuò)誤。
查看完整描述

2 回答

?
POPMUISE

TA貢獻(xiàn)1765條經(jīng)驗(yàn) 獲得超5個(gè)贊

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

通常,數(shù)組支持結(jié)構(gòu)用于二進(jìn)制堆,它受益于數(shù)組在堆分配節(jié)點(diǎn)和指針上的內(nèi)存布局和速度;堆操作不允許稀疏性,并且很容易使用您在此處使用的相同父子關(guān)系在線性結(jié)構(gòu)中進(jìn)行推理。

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

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);


查看完整回答
反對 回復(fù) 2023-05-25
?
叮當(dāng)貓咪

TA貢獻(xiàn)1776條經(jīng)驗(yàn) 獲得超12個(gè)贊

我沒有檢查代碼,但結(jié)果對我來說是正確的。數(shù)組中的第一項(xiàng)是根。然后接下來的兩個(gè)是等級 1 節(jié)點(diǎn)然后接下來的 4 個(gè)是等級 2 節(jié)點(diǎn)。那么接下來的 8 個(gè)是 rank 4 節(jié)點(diǎn) 你的結(jié)果應(yīng)該是


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

查看完整回答
反對 回復(fù) 2023-05-25
  • 2 回答
  • 0 關(guān)注
  • 154 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號