Thread: Binary search trees

  1. #1
    Registered User
    Join Date
    May 2016

    Question Binary search trees

    Hello everyone

    Does anyone know how to make an algorithm that transforms a binary search tree into an AVL tree, and yes transforms it and not make another tree (so it will only be done using rotations) and not with the DSW technique... and in C.
    So basically the hardest part is treating all the cases since there is 4 types of rotations.
    Thank you so much if you help !!

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    No, there are two types of rotation, left-rotation and right-rotation.
    First build a random tree, then test out your code that performs rotations.
    Once that works, here's an idea:
    At each node... find the height of each subtree... if they differ by no more than 1 then make a recursive call for each subtree... otherwise perform a rotation in the appropriate direction... then repeat the above for the current node.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. ABt Binary Search Trees
    By ging ging in forum C++ Programming
    Replies: 4
    Last Post: 10-17-2009, 12:58 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. Binary Search Trees
    By chaos in forum C Programming
    Replies: 1
    Last Post: 06-14-2005, 05:42 AM
  4. STL and Binary Search Trees
    By xshapirox in forum C++ Programming
    Replies: 2
    Last Post: 11-29-2004, 12:12 PM
  5. binary search trees in C
    By seeks in forum C Programming
    Replies: 1
    Last Post: 02-18-2002, 04:22 AM

Tags for this Thread