How to keep balanced and sorted binary tree-CodePudding

I have this binary tree which is supposed to be sorted, with each node having values from [0,1], so 0.5 is a good root node to keep it balanced.

But as I sort, I get two long legs with no further branches..I know I have seen this before, but I dont remember how to do this right.

Like I said, the problem is it starts looking like a linked list instead of a tree and thats not what I want. Because I want to insert/delete in O(log(n)).

CodePudding user response：

If you implement either an AVL tree orca red black trees, the algorithm will stay balanced with no need to add any seed nodes. The guarantee on AVL trees is that no branch is more than one node longer than any other branch. red black trees have a slightly less robust guarantee, but it is still good.

CodePudding user response：

Looks like AVL or Red/Black trees is answer to keep things balanced. Additionally, since I am building a BST for sorted values between [0,1], one option might be to start with a relatively complete tree? like so:

                 Node(0.875)
                /
            Node(0.75)
           /    \
          /      Node(0.625)
  RootNode(0.5)
          \      Node(0.375)
           \    /
            Node(0.25)
                \
                 Node(0.125)

and then adding nodes using that base tree, which will make everything cleaner, to expand even further:

                                / Node(0.9375)
                     Node(0.875)
                    /           \ Node(0.8125)
            Node(0.75)
           /        \           / Node(0.6875)
          /          Node(0.625)
         /                      \ Node(0.5625)
        /
  RootNode(0.5)                 / Node(0.4375)
          \          Node(0.375)       
           \        /           \ Node(0.3125)
            Node(0.25)
                    \           / Node(0.1875)
                     Node(0.125)
                                \ Node(0.625)

Using the above as a seed, will keep things relatively balanced, out of the gate.