2016-02-29 96 views
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; 
     } 
    } 
} 

這種算法完全有效,但你可以想像,這是不是你想的怪物的類型來回答使用與白板面試的問題。任何幫助將非常感激。

+1

是否缺乏遞歸故意?在遞歸數據結構上不使用遞歸勢必是笨重的。你還應該看看BST旋轉,它保持順序,但讓你輕鬆地移動節點(你也可以使用它們來實現平衡)。 – gus

回答

3

這將是更有效的,如果您:

  1. 結合prev()find()通過返回先前的節點,從find()
  2. 找到的節點既給每個節點的父親指針,只是按照它找到prev