AVL and red-black trees 
Author Message
 AVL and red-black trees

Hi, i'm new in this group and I need an implementation of AVL trees and
red-black trees to make a comparation.

--

Thanks in advance.

Roberto



Sat, 04 Oct 2003 20:14:31 GMT  
 AVL and red-black trees

Quote:

> Hi, i'm new in this group and I need an implementation of AVL trees and
> red-black trees to make a comparation.

Compare the implementations how?  The concepts of each are language
independent and layed out in any decent data structures textbook.

Marc A. Criley
Senior Staff Engineer
Quadrus Corporation
www.quadruscorp.com



Sun, 05 Oct 2003 09:53:32 GMT  
 AVL and red-black trees
I must search 2 implementations (better in Ada to not translate) and make a
lot of tests (insert, delete and search) with them.

The problem is that I haven't found an implementation with the remove
operation (and the explanations that I've found in Internet aren't clear).

--

Greetings

Roberto



Sun, 05 Oct 2003 21:41:33 GMT  
 AVL and red-black trees
Quote:

> I must search 2 implementations (better in Ada to not translate) and make a
> lot of tests (insert, delete and search) with them.

> The problem is that I haven't found an implementation with the remove
> operation (and the explanations that I've found in Internet aren't clear).

> --

> Greetings

> Roberto

Here are the sample implementations that were provided by my uni. you
will need to
split them up and get them working.

AVL
==============================

with text_io; use text_io;

procedure avl is

type balance is (left_heavy, balanced, right_heavy);

type node;

type ptr_to_node is access node;

type node is record
               data        : integer;
               count       : positive    := 1;
               left, right : ptr_to_node := null;
               bal         : balance     := balanced;
             end record;

root : ptr_to_node := null;

hh : boolean := false;

procedure print (p : ptr_to_node; n : integer) is

  i : integer;

begin

  if p /= null then
    print (p.right, n+4);
    for i in 1 .. n loop
      put(' ');
    end loop;
    put(integer'image(p.data));
    new_line;
    print (p.left, n+4);
  end if;

end print;

procedure insert (x : integer; p : in out ptr_to_node; h : in out
boolean) is

  p1, p2 : ptr_to_node;

begin

  if p = null then

    -- word is not in tree : insert it
    p := new node;
    p.data := x;
    h := true;

  elsif x < p.data then

    insert (x, p.left, h);

    if h then

      case p.bal is

        when right_heavy => p.bal := balanced;
                            h := false;

        when balanced    => p.bal := left_heavy;

        when left_heavy  => p1 := p.left;

                            if p1.bal = left_heavy then

                              -- single LL rotation
                              p.left := p1.right;
                              p1.right := p;
                              p.bal := balanced;
                              p := p1;

                            else

                              -- double LR rotation
                              p2 := p1.right;
                              p1.right := p2.left;
                              p2.left := p1;
                              p.left := p2.right;
                              p2.right := p;

                              if p2.bal = left_heavy then
                                p.bal := right_heavy;
                              else
                                p.bal := balanced;
                              end if;

                              if p2.bal = right_heavy then
                                p1.bal := left_heavy;
                              else
                                p1.bal := balanced;
                              end if;

                            end if;

                            p.bal := balanced;
                            h := false;

      end case;

    end if;

  elsif x > p.data then

    insert (x, p.right, h);

    if h then

      case p.bal is

        when left_heavy  => p.bal := balanced;
                            h := false;

        when balanced    => p.bal := right_heavy;

        when right_heavy => -- rebalance
                            p1 := p.right;

                            if p.bal = right_heavy then

                              -- single RR rotation
                              p.right := p1.left;
                              p1.left := p;
                              p.bal := balanced;
                              p := p1;

                            else

                              -- double RL rotation
                              p2 := p1.left;
                              p1.left := p2.right;
                              p2.right := p1;
                              p.right := p2.left;
                              p2.left := p;

                              if p2.bal = right_heavy then
                                p.bal := left_heavy;
                              else
                                p.bal := balanced;
                              end if;

                              if p2.bal = left_heavy then
                                p1.bal := right_heavy;
                              else
                                p1.bal := balanced;
                              end if;

                            end if;

                            p.bal := balanced;
                            h := false;

      end case;

    end if;

  else

    p.count := p.count + 1;
    h := false;

  end if;

end;

procedure delete (x : integer; p : in out ptr_to_node; h : in out
boolean) is

  q : ptr_to_node;

  procedure balance_1 (p : in out ptr_to_node; h : in out boolean) is

    p1, p2 : ptr_to_node;
    b1, b2 : balance;
  begin
    -- h = true, left branch has become less high
    case p.bal is
      when left_heavy  => p.bal := balanced;
      when balanced    => p.bal := right_heavy;
                          h := false;
      when right_heavy => -- rebalance
                          p1 := p.right;
                          b1 := p1.bal;
                          if b1 >= balanced then
                            -- single RR rotation
                            p.right := p1.left;
                            p1.left := p;
                            if b1 = balanced then
                              p.bal := right_heavy;
                              p1.bal := left_heavy;
                              h := false;
                            else
                              p.bal := balanced;
                              p1.bal := balanced;
                            end if;
                            p := p1;
                          else
                            -- double RL rotation
                            p2 := p1.left;
                            b2 := p2.bal;
                            p1.left := p2.right;
                            p2.right := p1;
                            p.right := p2.left;
                            p2.left := p;
                            if b2 = right_heavy then
                              p.bal := left_heavy;
                            else
                              p.bal := balanced;
                            end if;
                            if b2 = left_heavy then
                              p1.bal := right_heavy;
                            else
                              p1.bal := balanced;
                            end if;
                            p := p2;
                            p2.bal := balanced;
                          end if;
    end case;
  end;

  procedure balance_2 (p : in out ptr_to_node; h : in out boolean) is

    p1, p2 : ptr_to_node;
    b1, b2 : balance;

  begin
    case p.bal is
      when right_heavy => p.bal := balanced;
      when balanced    => p.bal := left_heavy;
                          h := false;
      when left_heavy  => -- rebalance
                          p1 := p.left;
                          b1 := p1.bal;
                          if b1 <= balanced then
                            -- single LL rotation
                            p.left := p1.right;
                            p1.right := p;
                            if b1 = balanced then
                              p.bal := left_heavy;
                              p1.bal := right_heavy;
                              h := false;
                            else
                              p.bal := balanced;
                              p1.bal := balanced;
                            end if;
                            p := p1;
                          else
                            -- double LR rotation
                            p2 := p1.right;
                            b2 := p2.bal;
                            p1.right := p2.left;
                            p2.left := p1;
                            p.left := p2.right;
                            p2.right := p;
                            if b2 = left_heavy then
                              p.bal := right_heavy;
                            else
                              p.bal := balanced;
                            end if;
                            if b2 = right_heavy then
                              p1.bal := left_heavy;
                            else
                              p1.bal := balanced;
                            end if;
                            p := p2;
                            p2.bal := balanced;
                          end if;
    end case;
  end balance_2;

  procedure del (r : in out ptr_to_node; h : in out boolean) is
  begin
    -- h = false
    if r.right /= null then
      del (r.right, h);
      if h then
        balance_2(r, h);
      end if;
    else
      q.data := r.data;
      q.count := r.count;
      r := r.left;
      h := true;
    end if;
  end;

begin -- delete
  if p = null then
    --put_line("data is not in tree");
    h := false;
  elsif x < p.data then
    delete (x, p.left, h);
    if h then
      balance_1 (p, h);
    end if;
  elsif x > p.data then
    delete (x, p.right, h);
    if h then
      balance_2 (p, h);
    end if;
  else
    -- delete p
    q := p;
    if q.right = null then
      p := q.left;
      h := true;
    elsif q.left = null then
      p := q.right;
      h := true;
    else
      del (q.left, h);
      if h then
        balance_1 (p, h);
      end if;
    end if;
    -- dispose(q);
  end if;
end delete;

begin

  for i in 1 .. 31 loop
    insert (i, root, hh);
  end loop;

  print(root, 1);

  for i in 10 .. 20 loop
    delete (i, root, hh);
  end loop;

  print(root, 1);

end;

=================================
Red-black
=================================
with tree_dec; use tree_dec;
with ansi; use ansi;

package rb_tree is

   x:integer:=0;

   procedure Initialize (t: in out tree);

   procedure  insert     (x: tree; e: item);
   procedure delete     (t: in out tree; e: item; successful: out
...

read more »



Mon, 06 Oct 2003 10:53:25 GMT  
 AVL and red-black trees

Quote:

> Hi, i'm new in this group and I need an implementation of AVL trees
> and red-black trees to make a comparation.

The Boock Components at http://www.pushface.org/components/bc/ have an
AVL tree implementation.


Mon, 06 Oct 2003 03:04:31 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. searching trees (AVL, 2-3-4 and red-black trees)

2. Red Black Tree - delete function

3. Program to create Red-Black Trees

4. need code for red-black binary search tree

5. Red-Black tree in PROLOG

6. Red Black Tree in PROLOG

7. red-black trees in fortran

8. Red - black trees

9. Red-Black-Trees and Fortran 2003 Features

10. Red-Black trees

11. AVL Tree,Binary Tree,Sorting..

12. AVL trees under OOP

 

 
Powered by phpBB® Forum Software