Binary tree

[AlexPython]

let said that I get a randomly created array of 12 numbers for this tree below instead of having the number picked by me, should I hand-pick the root? or should I let it be one of the random numbers of the array? I asking this is because I just don't want that by change the tree end up without a number on one of the sides(left or right). For example, let said the random array gives me this list 1-2-3-4-5-6-7-8-9-10 and the program choose 1 as the root I only going to get numbers on the right side. I guess I could just get the mean of the list and use int no to get decimals? or is there an easier way?

class Node:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

    def insert(self, data):
        if data < self.data:
            if self.leftChild:
                self.leftChild.insert(data)
            else:
                self.leftChild = Node(data)
                return
        else:
            if self.rightChild:
                self.rightChild.insert(data)
            else:
                self.rightChild = Node(data)
                return

    def PrintTree(self):
        if self.leftChild:
            self.leftChild.PrintTree()
        print( self.data),
        if self.rightChild:
            self.rightChild.PrintTree()

root = Node(27)
root.insert(28)
root.insert(30)
root.insert(26)
root.insert(22)
root.insert(18)
root.insert(17)
root.insert(14)
root.insert(35)
root.insert(31)
root.insert(10)
root.insert(19)
root.PrintTree()

Output:
10
14
17
18
19
22
26
27
28
30
31
35

Process finished with exit code 0

[deanhystad]

The median, not the mean. The median is the middle value. There will be close to an equal number of values left and right of the median. The mean doesn't have to be close to the middle at all. The mean of 1, 2, 3, 4, 5, 6, 7, 8, 9, 100000 is 10004.5. The median is 5.

That doesn't really balance the tree though. If the values are sorted end up with a funny shape like this:

Output:
   5
 /   \
1     6
 \      \
  2      7
   \       \
    3       8
      \       \
       4       9

You could comput the median again for values left and right of the top node. And repeat the process for the next level, and the next level and so on.
root = median(1, 2, 3, 4, 5, 6, 7, 8, 9(
root.left = median(1, 2, 3, 4)
root.right = median(6, 7, 8, 9)
root.left.left = 1
root.left.right = median(3, 4)
root.left.right.right = 4
root.right.left = 6
root.right.right = median(8, 9)
root.right.right.right =

Output:
       5
     /   \
    /      \
   2        7
  /  \     /  \
 1    3   6     8
        \         \
         4         9

What you want to is a way to balance the tree after it is created. This allows adding nodes to the tree after you create it and then re-balancing the tree. It is a challenging problem, but there are lots articles about how to balance a binary tree.

[AlexPython]

The median, not the mean. The median is the middle value. There will be close to an equal number of values left and right of the median. The mean doesn't have to be close to the middle at all. The mean of 1, 2, 3, 4, 5, 6, 7, 8, 9, 100000 is 10004.5. The median is 5.

That doesn't really balance the tree though. If the values are sorted end up with a funny shape like this:

Output:
   5
 /   \
1     6
 \      \
  2      7
   \       \
    3       8
      \       \
       4       9

You could comput the median again for values left and right of the top node. And repeat the process for the next level, and the next level and so on. But this still wouldn't keep the tree balanced as values were added later.

What you want to do is balance the tree after values are added. There are many articles written on how to balance binary trees.

Thanks

[ndc85430]

Binary search tree.