Geek asks and answers

Creating binary search trees

If I build a binary search tree by adding the following values ​​in order:

 10, 7, 16, 12, 5, 11, 2, 20, 1, 14

I get a tree of height 5. Is there a method (other than trial and error) that I can use to determine the order of integers that would create a tree of height 4?

+5
source share
3 answers

I did not think about it completely, but one way to get a tree of a specific depth is to sort your elements before inserting them: i.e. sorting and then inserting elements Ninto a binary search tree will create a depth tree N.

You may be able to:

  • Sort Items
  • Paste specific into them K=4to create a depth treeK
  • , .

(, , K , , , ?)

. , , K . :

  • 10, 7, 16, 12, 5, 11, 2, 20, 1, 14
  • : 1, 2, 5, 7, 10, 11, 12, 14, 16, 20
  • K = 4 , K-1, K-2 .., 1.

, 4:

12
  \
   14
     \
      16
        \
         20

... 3:

  12
 /  \
7    14
 \     \
  10    16
    \     \
     11    20

... 2:

    12
   /  \
  7    14
 / \     \
2   10    16
 \    \     \
  5    11    20

... , , :

      12
     /  \
    7    14
   / \     \
  2   10    16
 / \    \     \
1   5    11    20

... BST K = 4.

, , K - , K(K+1)/2 >= N.

+5

, , , .

, .

,

 1 2 5 7 10 11 12 14 16 20

( )

            11
     5            14
 1     7       12    16
   2     10             20

( , , ).

11 5 14 1 7 12 16 2 10 20
+5
public void testMakeBinarySearchTree() {
    List<Integer> array = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        array.add(i+1);
    }


    Collections.shuffle(array);


    Node root = new Node(array.get(5));
    for (int value : array) {
        binarySearchTreeInsertNode(root, value);
    }
}


private void binarySearchTreeInsertNode(Node node, int value) {
    int data = node.getData();
    if ( value > data) {
        Node right = node.getRight();
        if (right != null) {
            binarySearchTreeInsertNode(right, value);
        } else {
            node.setRight(new Node(value));
        }
    } else if (value < data) {
        Node left = node.getLeft();
        if (left != null) {
            binarySearchTreeInsertNode(left, value);
        } else {
            node.setLeft(new Node(value));
        }
    }
}
0
source

More articles:


All Articles