473,396 Members | 1,671 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,396 software developers and data experts.

AVL (Height Balanced) Tree

I have to code Insert/Remove for and AVL tree derived from a BST. I have a fully functional Insert working. Do determine the heights, I call a Height function that recursively calculates the height of each node. Does this violate the constraints on an AVL tree that all functions are to run in O(log n)?
Nov 19 '10 #1
1 2735
mac11
256 100+
It's been a long time since I've thought about implementation details of balanced trees (thanks to STL).

Does your Height calculate the height of each node in the entire tree, or does it just calculate the Height of the branch that the new node is on?

Calculating for every node in the tree is O(n), calculating the height for only the branch is likely O(log n).
Nov 19 '10 #2

Sign in to post your reply or Sign up for a free account.

Similar topics

6
by: Kenneth McDonald | last post by:
I can't see anything about this in the notes on the upcoming 2.4 on python.org, but for some reason I thought I remembered seeing that a balanced tree sequence type would be included in Python in...
7
by: Peter Tkacz | last post by:
Are there any data types within STL that implement a balanced tree? Peter
4
by: Max | last post by:
Hi guys, did some searching on the topic, but can't find much more then just basic info on binary trees. I need to write a binary tree implementation so that it is always complete. In other words...
0
by: j | last post by:
Hi, Anyone out there with binary search tree experience. Working on a project due tomorrow and really stuck. We need a function that splits a binary tree into a bigger one and smaller one(for a...
6
by: Ravi | last post by:
Hi, I need to find the non-recursive algorithm to find the height of a Binary Tree. Regards, SunLight.
4
by: Likush | last post by:
Hello, I'm looking for an implementation of the B-tree (balanced Tree) Data Structure(C# code).
3
by: heroma | last post by:
Hi! I want to implement B-Tree(Balanced Tree) with C but i don't know how can i do this! is there any friend that can help me?
10
by: Will Honea | last post by:
I have a data set which I need to analyze but I am having a problem figuring out a structure for the database - or whether there are better ways of attacking the problem. The base data set is a...
0
by: preetkanwal0678 | last post by:
Hello all, Am working on PYTHON +BRANWAVE(framework) Actually am Trying 2 make a tree menu using d both. Am not able 2 target the (.tmpl) files and not getting how 2 make frames in...
0
by: kasthurirangan.balaji | last post by:
Hello, I have some items in memory(character array) separarted with the newline character and the items are sorted inside the array. I already have a version of the code using a multimap object....
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
0
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
0
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.