School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Dream.In.Code > Programming Help > Computer Science

Welcome to Dream.In.Code
	Become an Expert! Join 307,149 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 1,703 people online right now. Registration is fast and FREE... Join Now! Chat LIVE With a Expert

Updating balance of AVL Tree after rotation is made

Updating balance of AVL Tree after rotation is made

skwo	30 Sep, 2009 - 10:05 PM Post #1
New D.I.C Head Joined: 19 Sep, 2009 Posts: 27 My Contributions	Hi there! I'm trying to implement AVL Trees. For now I bother only about addition. I experience problems with the balance. After I added node, I traverse the tree back to the root, updating balance of each node I visit (if I came from left son the balance will be decreased by one, otherwise increased by one). The moment the balance of one of the nodes becomes 0, I stop and the tree is balanced. But if the balance becomes +/-2 I need to do a rotation. Assuming that I did on of the rotations, how do I calculate the new balance of the subtree? Should I also calculate the new balance of the parent of non-balanced subtree? Thanks a lot!
	This Post Was Helpful!

Register for Free to Make These Ads Go Away!

Neumann	RE: Updating Balance Of AVL Tree After Rotation Is Made 9 Oct, 2009 - 11:56 AM Post #2
I can judge a book by its cover Joined: 8 Jul, 2009 Posts: 686 Thanked: 93 times Dream Kudos: 225 My Contributions	QUOTE(skwo @ 30 Sep, 2009 - 10:05 PM) how do I calculate the new balance of the subtree? Balance = height(left subtree) - height(right subtree). The height algorithm is extremely simple, so I assume that if you're working with AVL trees you know how to implement it. QUOTE Should I also calculate the new balance of the parent of non-balanced subtree? Yes, you should re-calculate the balance of all the nodes you had to visit while performing the addition. You should visit them in the reverse order, starting with the parent of the inserted node. Because the addition is recursive it is very simple to do this. For example, the addition can look something like this: CODE addNode (root, item) if root is null root = item else add the item to the correct subtree if height(t.left) - height(t.right) = 2 perform the correct rotations
	This Post Was Helpful!

Fast Reply

Reply to this topic

Start new topic

Display Mode: Standard · Switch to: Linear+ · Switch to: Outline

Track this topic · Email this topic · Print this topic · Subscribe to this forum

Time is now: 11/21/09 04:22PM

Invision Power Board v2.1.7 © 2009 IPS, Inc.

Licensed to: MediaGroup1

Advertising | Terms of Use | Privacy Policy | About Us | Site Map

Advertise on this site through Lake Quincy Media

Forum Index: Programming Help | C and C++ | VB6 | Java | VB.NET | C# | ASP.NET | PHP | ColdFusion | Perl and Python | Ruby | Databases | Other Languages | Game Programming | Mobile Development | Software Development | Computer Science | Industry News | Programming Tutorials | C++ Tutorials | Visual Basic Tutorials | Java Tutorials | VB.NET Tutorials | C# Tutorials | Linux Tutorials | PHP Tutorials | ColdFusion Tutorials | Windows Tutorials | HTML/JavaScript Tutorials | CSS Tutorials | Flash Tutorials | Web Promotion Tutorials | Graphic Design & Photoshop Tutorials | Software Development Tutorials | Database Tutorials | Other Language Tutorials | ASP.NET Tutorials | Game Programming Tutorials | WPF & Silverlight Tutorials |

Copyright 2001-2008 MediaGroup1 LLC, All Rights Reserved
A MediaGroup1 LLC Production - Version 6.0.2.1.36
Server: secure2

Search^Updated!w00t

Over 509,000 Pages! Advanced Forum Search

Live Help!

Be Social

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Join our IRC Chat

Bye Bye Ads

Monthly Drawing

Top Contributors

Top 10 Kudos This Month