Сбалансированное двоичное дерево поиска

Question

Мне нужно построить сбалансированное двоичное дерево поиска. Пока моя программа вставляет числа от 1 до 26, но моя программа не создает ее в сбалансированное двоичное дерево поиска. Если бы кто-нибудь мог взглянуть на мой код и помочь мне, это было бы очень признательно.

public class TreeNode { 

    TreeNode leftTreeNode, rightTreeNode;// the nodes 
    int data; 
    //int size; 



    public TreeNode(){//Constructer 
    leftTreeNode = null; 
    rightTreeNode = null; 
    } 

    public TreeNode(int newData){//Constructer with new Data coming in for comparison 
    leftTreeNode = null; 
    rightTreeNode = null; 
    data = newData; 
    } 

    public TreeNode getLeft(){ 
    return leftTreeNode; 
    } 
    public TreeNode getRight(){ 
    return rightTreeNode; 
    } 

    public void setLeft(TreeNode leftTreeNode){ 
    this.leftTreeNode = leftTreeNode; 
    } 
    public void setRight(TreeNode rightTreeNode){ 
    this.rightTreeNode = rightTreeNode; 
    } 
    public int getData(){ 
    return data; 
    } 

// public boolean isEmpty(){//Checking to see if the the root is empty 
//  if(size == 0) return true; 
//  else return false; 



    public void print(){ 
    System.out.println("Data is: " + getData()); 
    } 
} 


// public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
// if (root.getLeft() != null){ 
//  traverse (root.getLeft()); 
// } 
// System.out.println(root.data); 
// if (root.getRight() != null){ 
//  traverse (root.getRight()); 
// } 
//} 









public class BinarySearchTree { 
    TreeNode root; 

    public BinarySearchTree(){ 
    root = null; 
    } 

    public TreeNode getRoot(){ 
    return root; 
    } 
    public void insert(int data) { //Insert method checking to see where to put the nodes 
    TreeNode node1 = new TreeNode(data); 
    if (root == null) { 
     root = node1; 
    } 
    else{ 
     TreeNode parIns = root;//Parent 
     TreeNode insNode = root;//Insertion Node 

     while(insNode != null){ 
     parIns = insNode; 

     if(data < insNode.getData()){//If the data is less than the data coming in place it on the left 
      insNode = insNode.getLeft(); 
     }else{//Place it on the right 
      insNode = insNode.getRight(); 
     } 
     }//Searching where to put the node 

     if(data < parIns.getData()){ 
     parIns.setLeft(node1); 
     }else{ 
     parIns.setRight(node1); 
     } 

    } 
    } 

    public void printInorder(TreeNode n){ 
    if(n != null){ 
     printInorder(n.getLeft());//L 
     n.print();//N 
     printInorder(n.getRight());//R 
    } 
    } 
// public TreeNode balance(tree, int start, int end){ 
//  if(start > end) return null; 
//  int mid = (start + end) /2; 
//  TreeNode node; 
//  TreeNode leftChild; 
//  TreeNode rightChild; 
//  
//  if(node <= mid){ 
//  leftChild = balance(arr[mid -1], start, end);/*Make the left child if the node coming in is 
//  less than the mid node */ 
//   
//   
//  }else{ 
//  rightChild = balance(arr[mid]+1, start, end);/*Make the rigth child if the node is 
//   greater than the mid node*/ 
//   
//  } 
//  return node; 
// } 


    public static void main(String[] args) { 
    BinarySearchTree tree = new BinarySearchTree(); 
    tree.insert(1); 
    tree.insert(2); 
    tree.insert(3); 
    tree.insert(4); 
    tree.insert(5); 
    tree.insert(6); 
    tree.insert(7); 
    tree.insert(8); 
    tree.insert(9); 
    tree.insert(10); 
    tree.insert(11); 
    tree.insert(12); 
    tree.insert(13); 
    tree.insert(14); 
    tree.insert(15); 
    tree.insert(16); 
    tree.insert(17); 
    tree.insert(18); 
    tree.insert(19); 
    tree.insert(20); 
    tree.insert(21); 
    tree.insert(22); 
    tree.insert(23); 
    tree.insert(24); 
    tree.insert(25); 
    tree.insert(26); 
    tree.printInorder(tree.getRoot()); 



    } 



} 



//for(int i = 1; i <= 26; i++) 
    //tree.insert(i); 


     public void balance(TreeNode tree, int start, int end){ 
     TreeNode tree1 = new TreeNode(data); 
     if(start <= end){ 
     int mid = (start + end) /2; 
     //TreeNode node; 
     TreeNode leftChild; 
     TreeNode rightChild; 

     if(tree1.getData() <= mid){ 
     leftChild = balance(tree1(mid -1), start, end);/*Make the left child if the node coming in is 
     less than the mid node */ 


     }else{ 
     rightChild = balance(tree1(mid+1), start, end);/*Make the rigth child if the node is 
      greater than the mid node*/ 

     } 

     } 
} 

Как исправить функцию баланса для правильного баланса моего дерева?

Answer 1

Поскольку ваше дерево не самобалансируется, независимо от того, сбалансировано оно или нет, оно будет зависеть от порядка вставки элементов.

Если вы хотите, чтобы ваше дерево было сбалансировано независимо, вам нужно будет позаботиться о балансировке в своем классе. Например, посмотрите на структуру данных Red-Black Tree.

Answer 2

public class BinarySearchTree { 
    TreeNode root; 

    public BinarySearchTree(){ 
    root = new TreeNode(); 
    } 

    public TreeNode getRoot(){ 
    return root; 
    } 
    public void insert(int data) { 
    root = insert(root, data); 
    }//Insert method checking to see where to put the nodes 

// public void insert(TreeNode node, int data){ 
// TreeNode node1 = new TreeNode(data); 
// if (root == null) { 
//  root = node1; 
// } 
// else{ 
//  TreeNode parIns = root;//Parent 
//  TreeNode insNode = root;//Insertion Node 
//  
//  while(insNode != null){ 
//  parIns = insNode; 
//   
//  if(data < insNode.getData()){//If the data is less than the data coming in place it on the left 
//   insNode = insNode.getLeft(); 
//  }else{//Place it on the right 
//   insNode = insNode.getRight(); 
//  } 
//  }//Searching where to put the node 
//  
//  if(data < parIns.getData()){ 
//  parIns.setLeft(node1); 
//  }else{ 
//  parIns.setRight(node1); 
//  } 
//  
// } 
// } 

    private TreeNode insert(TreeNode node, int data) { 
    if(root.data == 0) 
     root.data = data; 
    else if (node==null) { 
     node = new TreeNode(data); 
    } 
    else { 
     if (data <= node.data) { 
     node.leftTreeNode = insert(node.leftTreeNode, data); 
     } 
     else { 
     node.rightTreeNode = insert(node.rightTreeNode, data); 
     } 
    } 

    return(node); // in any case, return the new pointer to the caller 
    } 
    public void printPreOrder(){ 
    printPreOrder(root); 
    } 
    public void printPreOrder(TreeNode n){ 
    if(n != null){ 
     n.print();//N 
     printPreOrder(n.getLeft());//L 
     printPreOrder(n.getRight());//R 
    } 
    } 

    public TreeNode balance(int[] a, int start, int end){ 
    TreeNode node = new TreeNode(); 
    if(start <= end){ 
     int mid = start + (end - start) /2; 
     node.data = a[mid]; 

     if(root.data == 0) 
     root = node; 
     node.leftTreeNode = balance(a, start, mid -1);/*Make the left child if the node coming in is 
     less than the mid node */ 


     node.rightTreeNode = balance(a, mid + 1, end);/*Make the rigth child if the node is 
     greater than the mid node*/ 
    } 
     else{ 
     return null; 
     } 


    return node; 
    } 



    public static void main(String[] args) { 
    BinarySearchTree tree = new BinarySearchTree(); 
    //int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,21,22,23,24,25,26}; 
    int[] a = new int[26]; 
    for(int i = 0; i < 26; i++){ 
     a[i] = i + 1; 
    } 
    for(int i = 1; i <= 26; i++) 
     tree.insert(i); 

    tree.printPreOrder(); 
    BinarySearchTree tree2 = new BinarySearchTree(); 
    tree2.balance(a, 0, 25); 
    System.out.println("Now I am going to balance my tree"); 
    tree2.printPreOrder(); 

    } 

} 



public class TreeNode { 

    TreeNode leftTreeNode, rightTreeNode;// the nodes 
    int data; 
    //int size; 



    public TreeNode(){//Constructer 
    leftTreeNode = null; 
    rightTreeNode = null; 
    data = 0; 
    } 

    public TreeNode(int newData){//Constructer with new Data coming in for comparison 
    leftTreeNode = null; 
    rightTreeNode = null; 
    data = newData; 
    } 

    public TreeNode getLeft(){ 
    return leftTreeNode; 
    } 
    public TreeNode getRight(){ 
    return rightTreeNode; 
    } 

    public void setLeft(TreeNode leftTreeNode){ 
    this.leftTreeNode = leftTreeNode; 
    } 
    public void setRight(TreeNode rightTreeNode){ 
    this.rightTreeNode = rightTreeNode; 
    } 
    public int getData(){ 
    return data; 
    } 


// public boolean isEmpty(){//Checking to see if the the root is empty 
//  if(size == 0) return true; 
//  else return false; 



    public void print(){ 
    System.out.println("Data is: " + getData()); 
    } 


}