3
\$\begingroup\$

Mostly as a learning exercise, and partly as I thought it might be useful, I have written an implementation of AVL trees ( https://en.wikipedia.org/wiki/AVL_tree ).

An AVL tree is a height-balanced binary search tree, where if the height difference of the left and right sub-trees becomes more than one a "rotate" operation is applied to re-balance the tree, which keeps the tree nodes in the same order, but promoting a child node upwards, with the unbalanced node being demoted.

Implementing C# iterators was totally new to me, so that has been a learning exercise, and I'm not quite sure if my style on that is quite right.

There are two main classes, a key-only tree AvlTree, and a key/value dictionary AvlDict.

I tend to stick to C# version 2, for reasons I won't go into, and I do not generally use _ for private fields, please don't comment on that - all other comments and reviews welcome. The way I have implemented dictionary assignment is perhaps a little questionable, but I wanted to separate out the key/value pair logic from the AVL tree. Is there a better way to do that?

Here is the code, starting with a usage example:

using Collections = System.Collections;
using Generic = System.Collections.Generic;
using Console = System.Console; // For example usage.

class AvlExample
{
  public static void Usage()
  {
    AvlTree<long> tree = new AvlTree<long>();

    int testSize = 5 * 1000 * 1000;

    // Insert keys 0, 10, 20 ... into the tree.
    for ( int i = 0; i < testSize; i += 10 ) tree.Insert( i );

    Console.WriteLine( "Should print 50,60..100" );
    foreach ( long x in tree.Range( 50, 100 ) ) Console.WriteLine( x );

    // Remove 4/5 of the keys to test Remove.
    for ( int i = 0; i < testSize; i += 10 ) if ( i % 50 != 0 ) tree.Remove( i );

    Console.WriteLine( "Should print 50,100..250" );
    foreach ( long x in tree.Range( 50, 250 ) ) Console.WriteLine( x );    

    AvlDict<int,string> dict = new AvlDict<int,string>( "" );

    dict[ 100 ] = "There";
    dict[ 50 ] = "Hello";
    dict[ 100 ] = "there";

    foreach ( int i in dict ) Console.WriteLine( dict[ i ] );
  }
}

class AvlTree<T> : Generic.IEnumerable<T> 
{
  public delegate int DComparer( T key1, T key2 );

  public AvlTree() // Initialise with default compare.
  {    
    Compare = Generic.Comparer<T>.Default.Compare;
  }

  public AvlTree( DComparer compare ) // Initialise with specific compare function.
  {    
    Compare = compare;
  }

  public void Insert( T key ) 
  // Insert key into the tree. If key is already in tree, Found is called.
  {    
    bool heightIncreased;
    Root = Insert( Root, key, out heightIncreased );
  }

  public bool Contains( T key )
  {
    return Lookup( key ) != null;
  }

  public void Remove( T key ) 
  // Remove key from the tree. If key is not present, has no effect. 
  {
    bool heightIncreased;
    Root = Remove( Root, key, out heightIncreased );
  }

  public Generic.IEnumerator<T> GetEnumerator() 
  {   
    if ( Root != null ) foreach( T key in Root ) yield return key;
  }

  Collections.IEnumerator Collections.IEnumerable.GetEnumerator() 
  { 
    return GetEnumerator(); 
  } 

  public Generic.IEnumerable<T> Range( T start, T end )
  {
    if ( Root != null ) foreach( T key in Root.Range( start, end, Compare ) ) yield return key;
  }

  protected virtual Node NewNode( T key )
  { 
    // Called by Insert if key not found.
    return new Node( key ); 
  }

  protected virtual void Found( Node x )
  {
    // Called by Insert when an existing key is found.
  }

  protected virtual void FreeNode( Node x )
  {
    // Called by Remove when a Node is removed.
  }

  protected Node Lookup( T key )
  {
    Node x = Root;
    while ( x != null )
    {
      int cf = Compare( key, x.Key );
      if ( cf < 0 ) x = x.Left;
      else if ( cf > 0 ) x = x.Right;
      else return x;
    }
    return null;
  }

  protected class Node : Generic.IEnumerable<T>
  {
    public Node Left, Right;
    public readonly T Key;
    public sbyte Balance;
    public Node( T key ) 
    { 
      Key = key;
    }

    public Generic.IEnumerator<T> GetEnumerator() 
    {
      if ( Left != null ) foreach ( T key in Left ) yield return key;
      yield return Key;
      if ( Right != null ) foreach ( T key in Right ) yield return key;      
    }

    Collections.IEnumerator Collections.IEnumerable.GetEnumerator() 
    { 
      return GetEnumerator(); 
    } 

    public Generic.IEnumerable<T> Range( T start, T end, DComparer compare )
    {
      int cstart = compare( start, Key );
      int cend = compare( end, Key );
      if ( cstart < 0 && Left != null )
      {
        foreach ( T key in Left.Range( start, end, compare ) ) yield return key;
      }
      if ( cstart <= 0 && cend >= 0 ) yield return Key;
      if ( cend > 0 && Right != null )
      {
        foreach ( T key in Right.Range( start, end, compare ) ) yield return key;
      }
    }

  } // Node

  // Fields.

  private readonly DComparer Compare;
  private Node Root;

  // Constant values for Node.Balance.
  private const int LeftHigher = -1, Balanced = 0, RightHigher = 1;

  // Private methods.

  private Node Insert( Node x, T key, out bool heightIncreased )
  {
    if ( x == null )
    {
      x = NewNode( key );
      heightIncreased = true;
    }
    else 
    {
      int compare = Compare( key, x.Key );
      if ( compare < 0 )
      {
        x.Left = Insert( x.Left, key, out heightIncreased );
        if ( heightIncreased )
        {
          if ( x.Balance == Balanced )
          {
            x.Balance = LeftHigher;
          }
          else
          {
            heightIncreased = false;
            if ( x.Balance == LeftHigher )
            {
              bool heightDecreased;
              return RotateRight( x, out heightDecreased );
            }
            x.Balance = Balanced;
          }
        }
      }
      else if ( compare > 0 )
      {
        x.Right = Insert( x.Right, key, out heightIncreased );
        if ( heightIncreased )
        {
          if ( x.Balance == Balanced )
          {
            x.Balance = RightHigher;
          }
          else
          {
            heightIncreased = false;
            if ( x.Balance == RightHigher )
            {
              bool heightDecreased;
              return RotateLeft( x, out heightDecreased );
            }
            x.Balance = Balanced;
          }
        }
      }
      else // compare == 0
      {
        Found( x );
        heightIncreased = false;
      }
    }
    return x;
  }

  private Node Remove( Node x, T key, out bool heightDecreased )
  {
    if ( x == null ) // key not found.
    {
      heightDecreased = false;
      return x;
    }
    int compare = Compare( key, x.Key );
    if ( compare == 0 )
    {
      Node deleted = x;
      if ( x.Left == null )
      {
        heightDecreased = true;
        x = x.Right;
      }
      else if ( x.Right == null )
      {
        heightDecreased = true;
        x = x.Left;
      }
      else
      {
        // Remove the smallest element in the right sub-tree and substitute it for x.
        Node right = RemoveLeast( deleted.Right, out x, out heightDecreased );
        x.Left = deleted.Left;
        x.Right = right;
        x.Balance = deleted.Balance;
        if ( heightDecreased )
        {
          if ( x.Balance == LeftHigher )
          {
            x = RotateRight( x, out heightDecreased );
          }
          else if ( x.Balance == RightHigher )
          {
            x.Balance = Balanced;
          }
          else
          {
            x.Balance = LeftHigher;
            heightDecreased = false;
          }
        }
      }
      FreeNode( deleted );
    }
    else if ( compare < 0 )
    {
      x.Left = Remove( x.Left, key, out heightDecreased );
      if ( heightDecreased )
      {
        if ( x.Balance == RightHigher )
        {
          return RotateLeft( x, out heightDecreased );
        }
        if ( x.Balance == LeftHigher )
        {
          x.Balance = Balanced;
        }
        else
        {
          x.Balance = RightHigher;
          heightDecreased = false;
        }
      }
    }
    else
    {
      x.Right = Remove( x.Right, key, out heightDecreased );
      if ( heightDecreased )
      {
        if ( x.Balance == LeftHigher )
        {
          return RotateRight( x, out heightDecreased );
        }
        if ( x.Balance == RightHigher )
        {
          x.Balance = Balanced;
        }
        else
        {
          x.Balance = LeftHigher;
          heightDecreased = false;
        }
      }
    }
    return x;
  }

  private static Node RemoveLeast( Node x, out Node least, out bool heightDecreased )
  {
    if ( x.Left == null )
    {
      heightDecreased = true;
      least = x;
      return x.Right;
    }
    else
    {
      x.Left = RemoveLeast( x.Left, out least, out heightDecreased );
      if ( heightDecreased )
      {
        if ( x.Balance == RightHigher )
        {
          return RotateLeft( x, out heightDecreased );
        }
        if ( x.Balance == LeftHigher )
        {
          x.Balance = Balanced;
        }
        else
        {
          x.Balance = RightHigher;
          heightDecreased = false;
        }
      }
      return x;
    }
  }

  private static Node RotateRight( Node x, out bool heightDecreased )
  {
    // Left is 2 levels higher than Right.
    heightDecreased = true;
    Node z = x.Left;
    Node y = z.Right;
    if ( z.Balance != RightHigher ) // Single rotation.
    {
      z.Right = x;
      x.Left = y;
      if ( z.Balance == Balanced ) // Can only occur when deleting values.
      {
        x.Balance = LeftHigher;
        z.Balance = RightHigher;
        heightDecreased = false;
      }
      else // z.Balance = LeftHigher
      {
        x.Balance = Balanced;
        z.Balance = Balanced;
      }
      return z;
    }
    else // Double rotation.
    {
      x.Left = y.Right;
      z.Right = y.Left;
      y.Right = x;
      y.Left = z;
      if ( y.Balance == LeftHigher )
      {
        x.Balance = RightHigher;
        z.Balance = Balanced;
      }
      else if ( y.Balance == Balanced )
      {
        x.Balance = Balanced;
        z.Balance = Balanced;
      }
      else // y.Balance == RightHigher
      {
        x.Balance = Balanced;
        z.Balance = LeftHigher;
      }
      y.Balance = Balanced;
      return y;
    }
  }

  private static Node RotateLeft( Node x, out bool heightDecreased )
  {
    // Right is 2 levels higher than Left.
    heightDecreased = true;
    Node z = x.Right;
    Node y = z.Left;
    if ( z.Balance != LeftHigher ) // Single rotation.
    {
      z.Left = x;
      x.Right = y;
      if ( z.Balance == Balanced ) // Can only occur when deleting values.
      {
        x.Balance = RightHigher;
        z.Balance = LeftHigher;
        heightDecreased = false;
      }
      else // z.Balance = RightHigher
      {
        x.Balance = Balanced;
        z.Balance = Balanced;
      }
      return z;
    }
    else // Double rotation
    {
      x.Right = y.Left;
      z.Left = y.Right;
      y.Left = x;
      y.Right = z;
      if ( y.Balance == RightHigher )
      {
        x.Balance = LeftHigher;
        z.Balance = Balanced;
      }
      else if ( y.Balance == Balanced )
      {
        x.Balance = Balanced;
        z.Balance = Balanced;
      }
      else // y.Balance == LeftHigher
      {
        x.Balance = Balanced;
        z.Balance = RightHigher;
      }
      y.Balance = Balanced;
      return y;
    }
  }
}

class AvlDict<TKey,TValue> : AvlTree<TKey>
{
  public AvlDict( TValue def ) : base() { Default = def; }

  public AvlDict( TValue def, DComparer compare ) : base( compare ) { Default = def; }

  public TValue this [ TKey key ] 
  { 
    get
    {
      Pair p = (Pair) Lookup( key );
      return p != null ? p.Value : Default;
    } 
    set
    {
      Value = value;
      Insert( key );
    }
  }

  private readonly TValue Default;
  private TValue Value;

  private class Pair : AvlTree<TKey>.Node
  {
    public TValue Value;
    public Pair( TKey key, TValue value ) : base( key ) { Value = value; }
  }

  protected override Node NewNode( TKey key )
  {
    return new Pair( key, Value );
  }

  protected override void Found( Node x )
  {
    Pair p = (Pair) x;
    p.Value = Value;
  }
}
\$\endgroup\$
  • \$\begingroup\$ @t3chb0t how are your C# v2 programming skills? :p \$\endgroup\$ – dfhwze Jul 15 at 15:11
  • 1
    \$\begingroup\$ @dfhwze wasn't the first version 7.3? ;-P \$\endgroup\$ – t3chb0t Jul 15 at 15:50
1
\$\begingroup\$

I re-organised my code into a base class AvlTree and two derived classes SortedSet and SortedDictionary. I feel this is an improvement because a SortedDictionary user no longer has access to inappropriate operations in AvlTree, this seems much neater altogether. It's also now on github here.

I have also added set union and intersection operations. Here's the revised code, again starting with the example usage, then the derived classes SortedSet and SortedDictionary and finally the base class AvlTree:

using Collections = System.Collections;
using Generic = System.Collections.Generic;
using Console = System.Console; // For example usage.

class AvlExample
{
  public static void Usage()
  {
    SortedSet<long> set = new SortedSet<long>();

    int testSize = 5 * 1000 * 1000;

    // Insert elements 0, 10, 20 ... into the set.
    for ( int i = 0; i < testSize; i += 10 ) 
    {
      set[ i ] = true; 
    }

    Console.WriteLine( "Should print 50,60..100" );
    foreach ( long x in set.Range( 50, 100 ) ) Console.WriteLine( x );

    // Remove 4/5 of the elements from the set.
    for ( int i = 0; i < testSize; i += 10 ) if ( i % 50 != 0 ) 
    { 
      set[ i ] = false;
    }

    Console.WriteLine( "Should print 50,100..250" );
    foreach ( long x in set.Range( 50, 250 ) ) Console.WriteLine( x );   

    // Test set union and intersection.
    SortedSet<int> s1 = new SortedSet<int>(); 
    SortedSet<int> s2 = new SortedSet<int>(); 
    s1[ 1 ] = true; s1[ 3 ] = true; s1[ 4 ] = true; s1[ 6 ] = true;
    s2[ 2 ] = true; s2[ 3 ] = true; s2[ 5 ] = true; s2[ 6 ] = true;
    Console.WriteLine( "Should print 3, 6" );
    foreach ( int e in s1 & s2 ) Console.WriteLine( e );    
    Console.WriteLine( "Should print 1..6" );
    foreach ( int e in s1 | s2 ) Console.WriteLine( e );  

    SortedDictionary<int,string> dict = new SortedDictionary<int,string>( "" );

    dict[ 100 ] = "There";
    dict[ 50 ] = "Hello";
    dict[ 100 ] = "there";

    Console.WriteLine( "Should print Hello there" );
    foreach ( int i in dict.Keys ) Console.WriteLine( dict[ i ] );
  }
}


class SortedSet<T> : AvlTree<T>, Generic.IEnumerable<T>
// Generic sorted set implemented as  height-balanced binary search tree. 
{
  public SortedSet() : base() 
  // Initialise with default ordering for T.
  { 
  } 

  public SortedSet( DCompare compare ) : base( compare ) 
  // Initialise with a specific ordering.
  { 
  } 

  public bool this [ T element ]
  // Include or Remove an element or check whether an element is in the set.
  { 
    set
    {
      if ( value ) Insert( element ); else Remove( element );
    }
    get
    {
      return Lookup( element ) != null;
    } 
  }

  public Generic.IEnumerator<T> GetEnumerator() 
  // Iterate over the set elements.
  {   
    if ( Root != null ) foreach( T key in Root ) yield return key;
  }

  public Generic.IEnumerable<T> Range( T start, T end )
  // Interate over the set elements in the specified range.
  {
    if ( Root != null ) foreach( T key in Root.Range( start, end, Compare ) ) yield return key;
  }

  public static SortedSet<T> operator & ( SortedSet<T> a, SortedSet<T> b )
  // Set intersection.
  {
    SortedSet<T> result = new SortedSet<T>( a.Compare );
    Generic.IEnumerator<T> ea = a.GetEnumerator();
    Generic.IEnumerator<T> eb = b.GetEnumerator();
    bool aok = ea.MoveNext();
    bool bok = eb.MoveNext();
    while ( aok && bok )
    {
      int compare = a.Compare( ea.Current,  eb.Current );
      if ( compare == 0 )
      {
        result.Append( ea.Current );
        aok = ea.MoveNext();
        bok = eb.MoveNext();
      }
      else if ( compare < 0 )
      {
        aok = ea.MoveNext();
      }
      else
      {
        bok = eb.MoveNext();
      }        
    }
    return result;
  }

  public static SortedSet<T> operator | ( SortedSet<T> a, SortedSet<T> b )
  // Set union.
  {
    SortedSet<T> result = new SortedSet<T>( a.Compare );
    Generic.IEnumerator<T> ea = a.GetEnumerator();
    Generic.IEnumerator<T> eb = b.GetEnumerator();
    bool aok = ea.MoveNext();
    bool bok = eb.MoveNext();
    while ( aok && bok )
    {
      int compare = a.Compare( ea.Current,  eb.Current );
      if ( compare == 0 )
      {
        result.Append( ea.Current );
        aok = ea.MoveNext();
        bok = eb.MoveNext();
      }
      else if ( compare < 0 )
      {
        result.Append( ea.Current );
        aok = ea.MoveNext();
      }
      else
      {
        result.Append( eb.Current );
        bok = eb.MoveNext();
      }        
    }
    while ( aok )
    {
      result.Append( ea.Current );
      aok = ea.MoveNext();
    }
    while ( bok )
    {
      result.Append( eb.Current );
      bok = eb.MoveNext();
    }
    return result;
  }

  Collections.IEnumerator Collections.IEnumerable.GetEnumerator() 
  // This is required by IEnumerable<T>. 
  { 
    return GetEnumerator(); 
  }

  protected override Node NewNode( T key )
  { 
    return new Node( key );
  }
}


class SortedDictionary<TKey,TValue> : AvlTree<TKey>
// Generic sorted dictionary implemented as a height-balanced binary search tree.
{
  public SortedDictionary( TValue defaultValue ) : base() 
  // Initialise with default order for TKey.
  // defaultValue is the value returned if an unassigned key is accessed.
  { 
    DefaultValue = defaultValue; 
  }

  public SortedDictionary( DCompare compare, TValue defaultValue ) : base( compare ) 
  // Initialise with specific order.
  // defaultValue is the value returned if an unassigned key is accessed.
  { 
    DefaultValue = defaultValue; 
  }

  public TValue this [ TKey key ]
  // Set or get an indexed dictionary value. 
  { 
    set
    {
      AssignValue = value;
      Insert( key );
    }
    get
    {
      Pair p = (Pair) Lookup( key );
      return p != null ? p.Value : DefaultValue;
    } 
  }

  public Generic.IEnumerable<TKey> Keys 
  // Iterate over all the dictionary keys.
  {
    get
    {   
      if ( Root != null ) foreach( TKey key in Root ) yield return key;
    }
  }

  public Generic.IEnumerable<TKey> KeyRange( TKey start, TKey end )
  // Iterate over the specified range of dictionary keys.
  {
    if ( Root != null ) foreach( TKey key in Root.Range( start, end, Compare ) ) yield return key;
  }

  private readonly TValue DefaultValue;

  private TValue AssignValue;

  private class Pair : AvlTree<TKey>.Node
  {
    public TValue Value;

    public Pair( TKey key, TValue value ) : base( key ) 
    { 
      Value = value; 
    }
  }

  protected override Node NewNode( TKey key )
  {
    return new Pair( key, AssignValue );
  }

  protected override void Update( Node x )
  {
    Pair p = (Pair) x;
    p.Value = AssignValue;
  }
}


abstract class AvlTree<T> 
// Height-balanced binary search tree.
{
  public delegate int DCompare( T key1, T key2 );

  protected AvlTree() 
  // Initialise with default compare function.
  {    
    Compare = Generic.Comparer<T>.Default.Compare;
  }

  protected AvlTree( DCompare compare ) 
  // Initialise with specific compare function.
  {    
    Compare = compare;
  }

  protected void Insert( T key ) 
  // Insert key into the tree. If key is already in tree, Update is called.
  {    
    bool heightIncreased;
    Root = Insert( Root, key, out heightIncreased );
  }

  protected void Append( T key )
  // Append a key to the tree.
  {
    bool heightIncreased;
    Root = Append( Root, key, out heightIncreased );
  }

  protected void Remove( T key ) 
  // Remove key from the tree. If key is not present, has no effect. 
  {
    bool heightIncreased;
    Root = Remove( Root, key, out heightIncreased );
  }

  protected abstract Node NewNode( T key ); 
  // Factory method called by Insert if key not found.

  protected virtual void Update( Node x )
  // Called by Insert when an existing key is found.
  {    
  }

  protected virtual void FreeNode( Node x )
  // Called by Remove when a Node is removed.
  {    
  }

  protected Node Lookup( T key )
  {
    // Search tree for Node with Key equal to key.
    Node x = Root;
    while ( x != null )
    {
      int cf = Compare( key, x.Key );
      if ( cf < 0 ) x = x.Left;
      else if ( cf > 0 ) x = x.Right;
      else return x;
    }
    return null;
  }

  protected class Node
  {
    public Node Left, Right;
    public readonly T Key;
    public sbyte Balance;
    public Node( T key ) 
    { 
      Key = key;
    }

    public Generic.IEnumerator<T> GetEnumerator() 
    {
      if ( Left != null ) foreach ( T key in Left ) yield return key;
      yield return Key;
      if ( Right != null ) foreach ( T key in Right ) yield return key;      
    }

    public Generic.IEnumerable<T> Range( T start, T end, DCompare compare )
    {
      int cstart = compare( start, Key );
      int cend = compare( end, Key );
      if ( cstart < 0 && Left != null )
      {
        foreach ( T key in Left.Range( start, end, compare ) ) yield return key;
      }
      if ( cstart <= 0 && cend >= 0 ) yield return Key;
      if ( cend > 0 && Right != null )
      {
        foreach ( T key in Right.Range( start, end, compare ) ) yield return key;
      }
    }

  } // Node

  // Fields.

  protected readonly DCompare Compare;
  protected Node Root;

  // Constant values for Node.Balance.
  private const int LeftHigher = -1, Balanced = 0, RightHigher = 1;

  // Private methods used to implement key insertion and removal.

  private Node Insert( Node x, T key, out bool heightIncreased )
  {
    if ( x == null )
    {
      x = NewNode( key );
      heightIncreased = true;
    }
    else 
    {
      int compare = Compare( key, x.Key );
      if ( compare < 0 )
      {
        x.Left = Insert( x.Left, key, out heightIncreased );
        if ( heightIncreased )
        {
          if ( x.Balance == Balanced )
          {
            x.Balance = LeftHigher;
          }
          else
          {
            heightIncreased = false;
            if ( x.Balance == LeftHigher )
            {
              bool heightDecreased;
              return RotateRight( x, out heightDecreased );
            }
            x.Balance = Balanced;
          }
        }
      }
      else if ( compare > 0 )
      {
        x.Right = Insert( x.Right, key, out heightIncreased );
        if ( heightIncreased )
        {
          if ( x.Balance == Balanced )
          {
            x.Balance = RightHigher;
          }
          else
          {
            heightIncreased = false;
            if ( x.Balance == RightHigher )
            {
              bool heightDecreased;
              return RotateLeft( x, out heightDecreased );
            }
            x.Balance = Balanced;
          }
        }
      }
      else // compare == 0
      {
        Update( x );
        heightIncreased = false;
      }
    }
    return x;
  }

  private Node Append( Node x, T key, out bool heightIncreased )
  {
    if ( x == null )
    {
      x = NewNode( key );
      heightIncreased = true;
    }
    else 
    {
      x.Right = Insert( x.Right, key, out heightIncreased );
      if ( heightIncreased )
      {
        if ( x.Balance == Balanced )
        {
          x.Balance = RightHigher;
        }
        else
        {
          heightIncreased = false;
          if ( x.Balance == RightHigher )
          {
            bool heightDecreased;
            return RotateLeft( x, out heightDecreased );
          }
          x.Balance = Balanced;
        }
      }
    }
    return x;
  }

  private Node Remove( Node x, T key, out bool heightDecreased )
  {
    if ( x == null ) // key not found.
    {
      heightDecreased = false;
      return x;
    }
    int compare = Compare( key, x.Key );
    if ( compare == 0 )
    {
      Node deleted = x;
      if ( x.Left == null )
      {
        heightDecreased = true;
        x = x.Right;
      }
      else if ( x.Right == null )
      {
        heightDecreased = true;
        x = x.Left;
      }
      else
      {
        // Remove the smallest element in the right sub-tree and substitute it for x.
        Node right = RemoveLeast( deleted.Right, out x, out heightDecreased );
        x.Left = deleted.Left;
        x.Right = right;
        x.Balance = deleted.Balance;
        if ( heightDecreased )
        {
          if ( x.Balance == LeftHigher )
          {
            x = RotateRight( x, out heightDecreased );
          }
          else if ( x.Balance == RightHigher )
          {
            x.Balance = Balanced;
          }
          else
          {
            x.Balance = LeftHigher;
            heightDecreased = false;
          }
        }
      }
      FreeNode( deleted );
    }
    else if ( compare < 0 )
    {
      x.Left = Remove( x.Left, key, out heightDecreased );
      if ( heightDecreased )
      {
        if ( x.Balance == RightHigher )
        {
          return RotateLeft( x, out heightDecreased );
        }
        if ( x.Balance == LeftHigher )
        {
          x.Balance = Balanced;
        }
        else
        {
          x.Balance = RightHigher;
          heightDecreased = false;
        }
      }
    }
    else
    {
      x.Right = Remove( x.Right, key, out heightDecreased );
      if ( heightDecreased )
      {
        if ( x.Balance == LeftHigher )
        {
          return RotateRight( x, out heightDecreased );
        }
        if ( x.Balance == RightHigher )
        {
          x.Balance = Balanced;
        }
        else
        {
          x.Balance = LeftHigher;
          heightDecreased = false;
        }
      }
    }
    return x;
  }

  private static Node RemoveLeast( Node x, out Node least, out bool heightDecreased )
  {
    if ( x.Left == null )
    {
      heightDecreased = true;
      least = x;
      return x.Right;
    }
    else
    {
      x.Left = RemoveLeast( x.Left, out least, out heightDecreased );
      if ( heightDecreased )
      {
        if ( x.Balance == RightHigher )
        {
          return RotateLeft( x, out heightDecreased );
        }
        if ( x.Balance == LeftHigher )
        {
          x.Balance = Balanced;
        }
        else
        {
          x.Balance = RightHigher;
          heightDecreased = false;
        }
      }
      return x;
    }
  }

  private static Node RotateRight( Node x, out bool heightDecreased )
  {
    // Left is 2 levels higher than Right.
    heightDecreased = true;
    Node z = x.Left;
    Node y = z.Right;
    if ( z.Balance != RightHigher ) // Single rotation.
    {
      z.Right = x;
      x.Left = y;
      if ( z.Balance == Balanced ) // Can only occur when deleting values.
      {
        x.Balance = LeftHigher;
        z.Balance = RightHigher;
        heightDecreased = false;
      }
      else // z.Balance = LeftHigher
      {
        x.Balance = Balanced;
        z.Balance = Balanced;
      }
      return z;
    }
    else // Double rotation.
    {
      x.Left = y.Right;
      z.Right = y.Left;
      y.Right = x;
      y.Left = z;
      if ( y.Balance == LeftHigher )
      {
        x.Balance = RightHigher;
        z.Balance = Balanced;
      }
      else if ( y.Balance == Balanced )
      {
        x.Balance = Balanced;
        z.Balance = Balanced;
      }
      else // y.Balance == RightHigher
      {
        x.Balance = Balanced;
        z.Balance = LeftHigher;
      }
      y.Balance = Balanced;
      return y;
    }
  }

  private static Node RotateLeft( Node x, out bool heightDecreased )
  {
    // Right is 2 levels higher than Left.
    heightDecreased = true;
    Node z = x.Right;
    Node y = z.Left;
    if ( z.Balance != LeftHigher ) // Single rotation.
    {
      z.Left = x;
      x.Right = y;
      if ( z.Balance == Balanced ) // Can only occur when deleting values.
      {
        x.Balance = RightHigher;
        z.Balance = LeftHigher;
        heightDecreased = false;
      }
      else // z.Balance = RightHigher
      {
        x.Balance = Balanced;
        z.Balance = Balanced;
      }
      return z;
    }
    else // Double rotation
    {
      x.Right = y.Left;
      z.Left = y.Right;
      y.Left = x;
      y.Right = z;
      if ( y.Balance == RightHigher )
      {
        x.Balance = LeftHigher;
        z.Balance = Balanced;
      }
      else if ( y.Balance == Balanced )
      {
        x.Balance = Balanced;
        z.Balance = Balanced;
      }
      else // y.Balance == LeftHigher
      {
        x.Balance = Balanced;
        z.Balance = RightHigher;
      }
      y.Balance = Balanced;
      return y;
    }
  }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ As long as there are no anwswers yet it's usually a better idea to edit the question and update the code there. \$\endgroup\$ – t3chb0t Feb 15 at 10:56
  • 1
    \$\begingroup\$ Please merge this answer in your question. It's very confusing for people reviewing your question. \$\endgroup\$ – dfhwze Jul 15 at 15:05
  • \$\begingroup\$ At this point in time (5 months down the line) it is pragmatic to leave this answer standing. It is a self-answer, but that's OK. If you want your new solution reviewed, post a new question... \$\endgroup\$ – rolfl Jul 15 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.