HEIGHT BALANCED TREES


AVL Trees:
     An AVL Tree is a binary search tree in which
1.The heights of the right subtree and left subtree differ by at most 1.
2.The left subtree and right subtree are them selves AVL Trees.
3.A node is said to be
   left-high    if the left subtree has greater height
   right-high    if the right subtree has greater height
   equl    if the heights of left subtree and right subtree are equl.

Red-Black Trees:

A red black tree is a binary search tree where on any path from the root to a leaf is not more than twice as long any other path from the root to a leaf.

A BST is called an RBT if it satisfies the following four properties.
1.Every node is coloured either block or red.
2.Every leaf is black.(Missing node property)
3.If a node is red , then both of its children are black.(Red constraint)
4.Every simple path from a node to a descendent leaf contains the same number of black nodes.(Black constraint)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s