紅黑樹平衡？

Question

我正在努力生成探戈樹， ，我需要檢查探戈中的每個子樹是否平衡。

如果它不平衡，我需要使其平衡？我努力使整個RB樹平衡，但我沒有得到任何正確的邏輯，所以任何人都可以幫助我？

這裏我添加代碼來檢查如何找到我的樹是平衡的不是但當它不是平衡如何我可以使它平衡。

static boolean verifyProperty5(rbnode n) { 

    int left = 0, right = 0; 
    if (n != null) { 
     bh++; 
     left = blackHeight(n.left, 0); 
     right = blackHeight(n.right, 0); 
    } 
    if (left == right) { 
     System.out.println("black height is :: " + bh); 
     return true; 
    } else { 
     System.out.println("in balance"); 
     return false; 
    } 
} 

public static int blackHeight(rbnode root, int len) { 
     bh = 0; 
     blackHeight(root, path1, len);   
     return bh; 
    } 

    private static void blackHeight(rbnode root, int path1[], int len) { 
     if (root == null) 
      return; 

     if (root.color == "black"){ 
      root.black_count = root.parent.black_count+1; 

     } else{ 
      root.black_count = root.parent.black_count; 
     } 
     if ((root.left == null) && (root.right == null)) {    
      bh = root.black_count;    
     }    
     blackHeight(root.left, path1, len); 
     blackHeight(root.right, path1, len); 
    } 

Answer 1

不要嘗試生成樹並驗證它是否平衡。嘗試從一開始就使用紅黑色的結構。它將保證生成的樹是平衡的。還是我誤解了？

編輯：

看起來探戈樹是基於紅黑樹。這意味着在實現Tango樹之前，您需要先實施紅黑樹。

Answer 2

如果您正在尋找紅黑樹平衡，您可以查看代碼here。