2
堆棧溢出算法神,借給我你的實力!我剛剛完成了我的第一個二叉搜索樹remove
函數,這是主要的優化需求。我花了很多時間在這隻小狗身上,這是我能管理的最好的。有沒有更簡單的方法來做到這一點?有沒有人有任何優化建議?對我來說,它似乎是必然的海量代碼。優化二進制搜索樹'刪除'功能
對於初學者...
我的二叉搜索樹...
function BST() {
this.root = null;
}
我的 '刪除' 功能...
BST.prototype.remove = function(data) {
if(this.root.data === data){
var curr = this.root.left;
while(true){
if(curr.right.left === null && curr.right.right === null){
this.root.data = curr.right.data;
curr.right = null;
break;
}
curr = curr.right;
}
}
var curr = this.root;
var found_data = this.find(data);
if(found_data.left !== null && found_data.right !== null){
var runner = found_data.right;
var runner_prev = found_data;
while(true){
if(runner.left === null && runner.right === null){
found_data.data = runner.data;
if(runner_prev.left === runner){
runner_prev.left = null;
}else{
runner_prev.right = null;
}
break;
}
runner_prev = runner;
runner = runner.left;
}
}else if(found_data.left === null || found_data.right === null){
var prev = this.prev(found_data.data);
if(prev.right === found_data){
if(found_data.left){
prev.right = found_data.left;
}else{
prev.right = found_data.right;
}
}else{
if(found_data.left){
prev.left = found_data.left;
}else{
prev.left = found_data.right;
}
}
}else{
var prev = this.prev(found_data.data);
if(prev.left === found_data){
prev.left = null;
}else{
prev.right = null;
}
}
};
你會注意到在我使用我的remove()
功能中的支持功能,如prev()
和find()
它們是我的總體功能BST()
功能的一部分,可以通過使用this.
對其進行預處理來使用。
支持功能我內remove()
(prev()
和find()
)
BST.prototype.find = function(data) {
if(this.root === null){
return 'wrong';
}
var curr = this.root;
while(true){
if(data > curr.data){
curr = curr.right;
}else if(data < curr.data){
curr = curr.left;
}else{
if(curr.data enter code here=== data){
return curr;
}else{
return 'not here player'
}
}
}
}
BST.prototype.prev = function(data){
if(this.root === null){
return false;
}
var prev = this.root;
var curr = this.root;
while(true){
if(curr.left === null && curr.right === null){
return prev;
}
if(data < curr.data){
prev = curr;
curr = curr.left;
}else if(data > curr.data){
prev = curr;
curr = curr.right;
}else{
return prev;
}
}
}
這種算法完全有效,但你可以想像,這是不是你想的怪物的類型來回答使用與白板面試的問題。任何幫助將非常感激。
是否缺乏遞歸故意?在遞歸數據結構上不使用遞歸勢必是笨重的。你還應該看看BST旋轉,它保持順序,但讓你輕鬆地移動節點(你也可以使用它們來實現平衡)。 – gus