AVL樹代碼 - 我不明白

void insert(const Comparable & x, AvlNode * & t) 
{ 
    if(t == NULL) 
      t = new AvlNode(x, NULL, NULL); 
    else if(x < t->element) 
    { 
      insert(x, t->left); 
      if(height(t->left) - height(t->right) == 2) 
        if(x < t->left->element) 
          rotateWithRightChild(t); 
        else 
          doubleWithLeftChild(t); 
    } 
    else if(t->element < x) 
    { 
      insert(x, t->right); 
      if(height(t->right) - height(t->left) == 2) 
        if(x < t->left->element) 
          rotateWithRightChild(t); 
        else 
          doubleWithLeftChild(t); 
    } 
    else 
      ; // Duplicate; do nothing 
    t->height = max(height(t->left), height(t->right)) + 1; 

} 

int height(AvlNode *t) const { return t == NULL ? -1 : t->height; }

他們怎麼能調高樹的高度？AVL樹代碼 - 我不明白

 1 
    0 
    -1

高度（-1） - 高度（空）= 1＆不平衡？

來源

2009-11-20 nXqd

究竟是什麼，你不明白？理解C++語法有問題還是隻涉及算法？ – sellibitze 2009-11-20 15:38:34

我真的不明白它計算樹的高度的方式嗎？算法我的意思是。謝謝:) – nXqd 2009-11-20 15:43:29

這不是100％清楚你要問什麼。代碼

AvlNode * & t

聲明t是對非const指針的引用。因此，該函數插入可能會更改調用方的指針對象。由於指針可以爲空的代碼可能使用功能稱爲height作爲一種快捷方式來處理空指針的特殊情況：

inline int height(AvlNode * tree) { 
    return tree ? tree->height : 0; 
}

（只是我的會是什麼高度類似的猜測）在您編輯完您的問題後添加： 看起來每個節點都有一個名爲height的成員，該成員保持同步並反映從當前節點到葉節點的最大路徑長度。由於空指針並不指向節點，因此子樹將爲空，這將解釋返回-1的height（）中的特殊情況。

來源

2009-11-20 15:31:29 sellibitze

int height（AvlNode * t）const { return t == NULL？ -1：t-> height; } 這是高度功能，我完全不明白XD XD。你能否在前面解釋樹，高度必須加總，對不對？ Thx發表評論。 – nXqd 2009-11-20 15:35:15

AVL樹代碼 - 我不明白

回答

相關問題