CODEWITHSUNDEEP
sortingbinary-treebinary-search-tree
Alexander Mills
Alexander Mills

Reputation: 100020

How to keep balanced and sorted binary tree

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)).

enter image description here

Upvotes: 0

Views: 563

Answers (3)

trincot
trincot

Reputation: 350270

There are several structures and related algorithms that provide self-balancing trees -- or more generally -- sorted lists.

Among binary trees there are AVL trees and red-black trees. But in my own experience -- when having to deal with millions of values -- a B+tree has been an efficient option. It has some interesting features:

  • easy to balance: no rotations, but splits and joins.
  • memory is allocated in blocks -- ready for storing more than one value -- so that the number of allocations is much less than the number of stored values
  • you can play with the branching factor to see which one gives best performance
  • when the bottom layer is linked as a linked list, you have easy access to the ordered sequence of values

Upvotes: 1

John McLeod VII
John McLeod VII

Reputation: 26

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.

Upvotes: 1

Alexander Mills
Alexander Mills

Reputation: 100020

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.

Upvotes: 0

Related Questions