Packages
avl_tree

1.0.0
Pure Elixir AVL tree implementation
HexDocs
Current section
Files
Jump to
Readme 1 Version 0 Dependencies Dependants Files Activity
avl_tree test avl_tree_test.exs
Raw
9 files
bench
- run.exs
lib
- avl_tree
  
  node.ex
  
  tree.ex
  
  view.ex
test
- avl_tree_test.exs
- test_helper.exs
LICENSE
README.md
mix.exs
test/avl_tree_test.exs

defmodule AVLTreeTest do
  use ExUnit.Case

  doctest AVLTree, except: [view: 1]

  use ExUnit.Case

  test "protocols" do
    tree1 = Enum.into([5, 9, 3, 8, 1, 6, 7], AVLTree.new())
    assert Enum.to_list(tree1) == [1, 3, 5, 6, 7, 8, 9]
    assert Enum.member?(tree1, 6)
    assert !Enum.member?(tree1, 10)
    tree2 = Enum.into([8, 4, 2, 5, 7, 2, 1, 3], AVLTree.new())
    assert Enum.to_list(tree2) == [1, 2, 2, 3, 4, 5, 7, 8]
    assert Enum.zip(tree1, tree2) == [{1, 1}, {3, 2}, {5, 2}, {6, 3}, {7, 4}, {8, 5}, {9, 7}]
  end

  test "new" do
    asc = &Kernel.</2
    desc = &Kernel.>/2

    %AVLTree{root: nil, size: 0, less: ^asc} = AVLTree.new()
    %AVLTree{root: nil, size: 0, less: ^asc} = AVLTree.new(:asc)
    %AVLTree{root: nil, size: 0, less: ^desc} = AVLTree.new(:desc)
  end

  test "put" do
    tree = Enum.into([5, 9, 3, 8, 1, 6, 7], AVLTree.new())
    assert Enum.to_list(tree) == [1, 3, 5, 6, 7, 8, 9]
    assert AVLTree.member?(tree, 3)
    assert !AVLTree.member?(tree, 2)

    assert AVLTree.size(tree) == 7
    assert AVLTree.height(tree) == 4

    assert inspect(tree) == "#AVLTree<[1, 3, 5, 6, 7, 8, 9]>"

    #    5
    #  ┌─┴───┐
    #  3     8
    # ┌┴┐  ┌─┴┐
    # 1    6  9
    #     ┌┴┐
    #       7
    assert tree.root ==
             {5, 4, {3, 2, {1, 1, nil, nil}, nil},
              {8, 3, {6, 2, nil, {7, 1, nil, nil}}, {9, 1, nil, nil}}}

    tree = Enum.into([11, 10, 12], tree)
    assert Enum.to_list(tree) == [1, 3, 5, 6, 7, 8, 9, 10, 11, 12]
    assert AVLTree.size(tree) == 10
    assert AVLTree.height(tree) == 4

    #        8
    #    ┌───┴─┐
    #    5    10
    #  ┌─┴─┐  ┌┴─┐
    #  3   6  9 11
    # ┌┴┐ ┌┴┐   ┌┴─┐
    # 1     7     12
    assert tree.root ==
             {8, 4, {5, 3, {3, 2, {1, 1, nil, nil}, nil}, {6, 2, nil, {7, 1, nil, nil}}},
              {10, 3, {9, 1, nil, nil}, {11, 2, nil, {12, 1, nil, nil}}}}

    tree = AVLTree.put(tree, 4)
    assert Enum.to_list(tree) == [1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    assert AVLTree.size(tree) == 11
    assert AVLTree.height(tree) == 4

    #        8
    #    ┌───┴─┐
    #    5    10
    #  ┌─┴─┐  ┌┴─┐
    #  3   6  9 11
    # ┌┴┐ ┌┴┐   ┌┴─┐
    # 1 4   7     12
    assert tree.root ==
             {8, 4,
              {5, 3, {3, 2, {1, 1, nil, nil}, {4, 1, nil, nil}}, {6, 2, nil, {7, 1, nil, nil}}},
              {10, 3, {9, 1, nil, nil}, {11, 2, nil, {12, 1, nil, nil}}}}

    assert tree == AVLTree.put(tree, 7)
  end

  test "get" do
    tree =
      [{5, 50}, {1, 10}, {9, 90}, {1, 20}, {5, 40}, {7, 70}, {2, 20}]
      |> Enum.into(AVLTree.new(fn {k1, _}, {k2, _} -> k1 < k2 end))

    assert AVLTree.get(tree, {7, nil}) == {7, 70}
    assert AVLTree.get(tree, {9, nil}) == {9, 90}
    assert AVLTree.get(tree, {5, nil}) == {5, 50}
    assert AVLTree.get(tree, {1, nil}) == {1, 20}
    assert AVLTree.get(tree, {6, nil}) == nil
    assert AVLTree.get(tree, {6, nil}, :error) == :error
  end

  test "get first/last" do
    tree =
      [{5, 50}, {1, 10}, {9, 90}, {1, 20}, {5, 40}, {7, 70}, {2, 20}]
      |> Enum.into(AVLTree.new(fn {k1, _}, {k2, _} -> k1 < k2 end))

    assert AVLTree.get_first(tree) == {1, 10}
    assert AVLTree.get_last(tree) == {9, 90}

    tree = AVLTree.new()
    assert AVLTree.get_first(tree) == nil
    assert AVLTree.get_first(tree, :error) == :error

    assert AVLTree.get_last(tree) == nil
    assert AVLTree.get_last(tree, :error) == :error
  end

  test "get lower/upper" do
    tree =
      [{5, 50}, {1, 10}, {9, 90}, {1, 20}, {5, 40}, {7, 70}, {2, 20}]
      |> Enum.into(AVLTree.new(fn {k1, _}, {k2, _} -> k1 < k2 end))

    assert AVLTree.get_lower(tree, {1, nil}) == {1, 10}
    assert AVLTree.get_upper(tree, {1, nil}) == {1, 20}

    assert AVLTree.get_lower(tree, {5, nil}) == {5, 50}
    assert AVLTree.get_upper(tree, {5, nil}) == {5, 40}

    assert AVLTree.get_lower(tree, {6, nil}) == nil
    assert AVLTree.get_upper(tree, {6, nil}) == nil

    assert AVLTree.get_lower(tree, {6, nil}, :error) == :error
    assert AVLTree.get_upper(tree, {6, nil}, :error) == :error
  end

  test "put/delete lower/upper" do
    tree =
      [{1, 10}, {5, 50}, {9, 90}, {7, 70}, {2, 20}]
      |> Enum.into(AVLTree.new(fn {k1, _}, {k2, _} -> k1 < k2 end))

    assert Enum.to_list(tree) == [{1, 10}, {2, 20}, {5, 50}, {7, 70}, {9, 90}]
    assert AVLTree.size(tree) == 5
    assert AVLTree.height(tree) == 3

    #         {5, 50}
    #    ┌───────┴───────┐
    # {1, 10}         {9, 90}
    #   ┌┴───┐       ┌───┴┐
    #     {2, 20} {7, 70}
    assert tree.root ==
             {{5, 50}, 3, {{1, 10}, 2, nil, {{2, 20}, 1, nil, nil}},
              {{9, 90}, 2, {{7, 70}, 1, nil, nil}, nil}}

    tree = AVLTree.put(tree, {7, 700})
    assert Enum.to_list(tree) == [{1, 10}, {2, 20}, {5, 50}, {7, 700}, {9, 90}]
    assert AVLTree.size(tree) == 5
    assert AVLTree.height(tree) == 3

    #         {5, 50}
    #    ┌───────┴────────┐
    # {1, 10}          {9, 90}
    #   ┌┴───┐        ┌───┴┐
    #     {2, 20} {7, 700}
    assert tree.root ==
             {{5, 50}, 3, {{1, 10}, 2, nil, {{2, 20}, 1, nil, nil}},
              {{9, 90}, 2, {{7, 700}, 1, nil, nil}, nil}}

    assert AVLTree.put_lower(tree, {8, 80}) == AVLTree.put_upper(tree, {8, 80})
    assert AVLTree.put_lower(tree, {8, 80}) == AVLTree.put(tree, {8, 80})

    tree = AVLTree.put_lower(tree, {7, 71})
    tree = AVLTree.put_lower(tree, {7, 72})
    tree = AVLTree.put_lower(tree, {7, 73})

    assert Enum.to_list(tree) == [
             {1, 10},
             {2, 20},
             {5, 50},
             {7, 73},
             {7, 72},
             {7, 71},
             {7, 700},
             {9, 90}
           ]

    assert AVLTree.size(tree) == 8
    assert AVLTree.height(tree) == 4

    #         {5, 50}
    #    ┌───────┴───────────────┐
    # {1, 10}                {7, 700}
    #   ┌┴───┐           ┌───────┴───┐
    #     {2, 20}     {7, 72}     {9, 90}
    #                ┌───┴───┐
    #             {7, 73} {7, 71}
    assert tree.root ==
             {{5, 50}, 4, {{1, 10}, 2, nil, {{2, 20}, 1, nil, nil}},
              {{7, 700}, 3, {{7, 72}, 2, {{7, 73}, 1, nil, nil}, {{7, 71}, 1, nil, nil}},
               {{9, 90}, 1, nil, nil}}}

    tree = AVLTree.put_upper(tree, {7, 74})
    tree = AVLTree.put_upper(tree, {7, 75})
    tree = AVLTree.put_upper(tree, {7, 76})

    assert Enum.to_list(tree) == [
             {1, 10},
             {2, 20},
             {5, 50},
             {7, 73},
             {7, 72},
             {7, 71},
             {7, 700},
             {7, 74},
             {7, 75},
             {7, 76},
             {9, 90}
           ]

    #                        {7, 700}
    #            ┌───────────────┴───────┐
    #         {5, 50}                 {7, 75}
    #    ┌───────┴───────┐           ┌───┴───────┐
    # {1, 10}         {7, 72}     {7, 74}     {9, 90}
    #   ┌┴───┐       ┌───┴───┐               ┌───┴┐
    #     {2, 20} {7, 73} {7, 71}         {7, 76}
    assert tree.root ==
             {{7, 700}, 4,
              {{5, 50}, 3, {{1, 10}, 2, nil, {{2, 20}, 1, nil, nil}},
               {{7, 72}, 2, {{7, 73}, 1, nil, nil}, {{7, 71}, 1, nil, nil}}},
              {{7, 75}, 3, {{7, 74}, 1, nil, nil}, {{9, 90}, 2, {{7, 76}, 1, nil, nil}, nil}}}

    tree = AVLTree.delete_upper(tree, {7, nil})

    #                        {7, 700}
    #            ┌───────────────┴───────┐
    #         {5, 50}                 {7, 75}
    #    ┌───────┴───────┐           ┌───┴───┐
    # {1, 10}         {7, 72}     {7, 74} {9, 90}
    #   ┌┴───┐       ┌───┴───┐
    #     {2, 20} {7, 73} {7, 71}
    assert tree.root ==
             {{7, 700}, 4,
              {{5, 50}, 3, {{1, 10}, 2, nil, {{2, 20}, 1, nil, nil}},
               {{7, 72}, 2, {{7, 73}, 1, nil, nil}, {{7, 71}, 1, nil, nil}}},
              {{7, 75}, 2, {{7, 74}, 1, nil, nil}, {{9, 90}, 1, nil, nil}}}

    tree = AVLTree.delete_lower(tree, {7, nil})

    #                    {7, 700}
    #            ┌───────────┴───────┐
    #         {5, 50}             {7, 75}
    #    ┌───────┴───┐           ┌───┴───┐
    # {1, 10}     {7, 72}     {7, 74} {9, 90}
    #   ┌┴───┐      ┌┴───┐
    #     {2, 20}     {7, 71}
    assert tree.root ==
             {{7, 700}, 4,
              {{5, 50}, 3, {{1, 10}, 2, nil, {{2, 20}, 1, nil, nil}},
               {{7, 72}, 2, nil, {{7, 71}, 1, nil, nil}}},
              {{7, 75}, 2, {{7, 74}, 1, nil, nil}, {{9, 90}, 1, nil, nil}}}

    tree = AVLTree.delete_lower(tree, {7, nil})

    #                {7, 700}
    #            ┌───────┴───────┐
    #         {5, 50}         {7, 75}
    #    ┌───────┴───┐       ┌───┴───┐
    # {1, 10}     {7, 71} {7, 74} {9, 90}
    #   ┌┴───┐
    #     {2, 20}
    assert tree.root ==
             {{7, 700}, 4,
              {{5, 50}, 3, {{1, 10}, 2, nil, {{2, 20}, 1, nil, nil}}, {{7, 71}, 1, nil, nil}},
              {{7, 75}, 2, {{7, 74}, 1, nil, nil}, {{9, 90}, 1, nil, nil}}}

    tree = AVLTree.delete_lower(tree, {7, nil})

    #            {7, 700}
    #        ┌───────┴───────┐
    #     {2, 20}         {7, 75}
    #    ┌───┴───┐       ┌───┴───┐
    # {1, 10} {5, 50} {7, 74} {9, 90}
    assert tree.root ==
             {{7, 700}, 3, {{2, 20}, 2, {{1, 10}, 1, nil, nil}, {{5, 50}, 1, nil, nil}},
              {{7, 75}, 2, {{7, 74}, 1, nil, nil}, {{9, 90}, 1, nil, nil}}}

    tree = AVLTree.delete_upper(tree, {7, nil})

    #            {7, 700}
    #        ┌───────┴───┐
    #     {2, 20}     {7, 74}
    #    ┌───┴───┐      ┌┴───┐
    # {1, 10} {5, 50}     {9, 90}

    assert tree.root ==
             {{7, 700}, 3, {{2, 20}, 2, {{1, 10}, 1, nil, nil}, {{5, 50}, 1, nil, nil}},
              {{7, 74}, 2, nil, {{9, 90}, 1, nil, nil}}}

    assert ^tree = AVLTree.delete_upper(tree, {6, nil})
    assert ^tree = AVLTree.delete_lower(tree, {6, nil})
  end

  test "delete" do
    tree = Enum.into([5, 9, 3, 8, 1, 6, 7], AVLTree.new())
    assert match?(^tree, AVLTree.delete(tree, 4))
    tree = AVLTree.delete(tree, 3)

    assert Enum.to_list(tree) == [1, 5, 6, 7, 8, 9]
    assert AVLTree.size(tree) == 6
    assert AVLTree.height(tree) == 3

    #    6
    #  ┌─┴─┐
    #  5   8
    # ┌┴┐ ┌┴┐
    # 1   7 9
    assert tree.root ==
             {6, 3, {5, 2, {1, 1, nil, nil}, nil}, {8, 2, {7, 1, nil, nil}, {9, 1, nil, nil}}}

    tree = AVLTree.delete(tree, 1)
    assert Enum.to_list(tree) == [5, 6, 7, 8, 9]
    assert AVLTree.size(tree) == 5 and AVLTree.height(tree) == 3

    #  6
    # ┌┴─┐
    # 5  8
    #   ┌┴┐
    #   7 9
    assert tree.root == {6, 3, {5, 1, nil, nil}, {8, 2, {7, 1, nil, nil}, {9, 1, nil, nil}}}

    tree = AVLTree.delete(tree, 8)
    assert Enum.to_list(tree) == [5, 6, 7, 9]
    assert AVLTree.size(tree) == 4 and AVLTree.height(tree) == 3

    #  6
    # ┌┴─┐
    # 5  7
    #   ┌┴┐
    #     9
    assert tree.root == {6, 3, {5, 1, nil, nil}, {7, 2, nil, {9, 1, nil, nil}}}

    tree = Enum.into([3, 1, 2, 4, 8, 0], tree)
    assert Enum.to_list(tree) == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    assert AVLTree.size(tree) == 10 and AVLTree.height(tree) == 4

    #        6
    #    ┌───┴─┐
    #    3     8
    #  ┌─┴─┐  ┌┴┐
    #  1   5  7 9
    # ┌┴┐ ┌┴┐
    # 0 2 4
    assert tree.root ==
             {6, 4,
              {3, 3, {1, 2, {0, 1, nil, nil}, {2, 1, nil, nil}}, {5, 2, {4, 1, nil, nil}, nil}},
              {8, 2, {7, 1, nil, nil}, {9, 1, nil, nil}}}

    tree = AVLTree.delete(tree, 6)
    assert Enum.to_list(tree) == [0, 1, 2, 3, 4, 5, 7, 8, 9]
    assert AVLTree.size(tree) == 9 and AVLTree.height(tree) == 4

    #      5
    #    ┌─┴─┐
    #    3   8
    #  ┌─┴┐ ┌┴┐
    #  1  4 7 9
    # ┌┴┐
    # 0 2
    assert tree.root ==
             {5, 4, {3, 3, {1, 2, {0, 1, nil, nil}, {2, 1, nil, nil}}, {4, 1, nil, nil}},
              {8, 2, {7, 1, nil, nil}, {9, 1, nil, nil}}}

    tree = Enum.into([0, 3, 2, 1, 4, 8, 7, 9, 5, 6, 11, 12, 10, 14, 13, 15], AVLTree.new())
    tree = AVLTree.delete(tree, 4)
    assert Enum.to_list(tree) == [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    assert AVLTree.size(tree) == 15 and AVLTree.height(tree) == 5

    #      5
    #    ┌─┴──────┐
    #    2       11
    #  ┌─┴┐  ┌────┴──┐
    #  0  3  7      13
    # ┌┴┐   ┌┴─┐    ┌┴─┐
    #   1   6  9   12 14
    #         ┌┴─┐    ┌┴─┐
    #         8 10      15
    assert tree.root ==
             {5, 5, {2, 3, {0, 2, nil, {1, 1, nil, nil}}, {3, 1, nil, nil}},
              {11, 4, {7, 3, {6, 1, nil, nil}, {9, 2, {8, 1, nil, nil}, {10, 1, nil, nil}}},
               {13, 3, {12, 1, nil, nil}, {14, 2, nil, {15, 1, nil, nil}}}}}

    tree = tree |> AVLTree.delete(3) |> AVLTree.delete(2)
    assert Enum.to_list(tree) == [0, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

    assert AVLTree.size(tree) == 13 and AVLTree.height(tree) == 5

    #          11
    #    ┌──────┴──┐
    #    5        13
    #  ┌─┴─┐      ┌┴─┐
    #  1   7     12 14
    # ┌┴┐ ┌┴─┐      ┌┴─┐
    # 0   6  9        15
    #       ┌┴─┐
    #       8 10
    assert tree.root ==
             {11, 5,
              {5, 4, {1, 2, {0, 1, nil, nil}, nil},
               {7, 3, {6, 1, nil, nil}, {9, 2, {8, 1, nil, nil}, {10, 1, nil, nil}}}},
              {13, 3, {12, 1, nil, nil}, {14, 2, nil, {15, 1, nil, nil}}}}
  end

  test "view" do
    tree =
      [{5, 50}, {1, 10}, {9, 90}, {1, 20}, {5, 40}, {6, 60}, {7, 70}, {2, 20}]
      |> Enum.into(AVLTree.new(fn {k1, _}, {k2, _} -> k1 < k2 end))

    assert AVLTree.view(tree) ==
             Enum.join(
               [
                 "            {5, 50}                ",
                 "       ┌───────┴───────┐           ",
                 "    {1, 20}         {6, 60}        ",
                 "   ┌───┴───┐       ┌───┴───────┐   ",
                 "{1, 10} {2, 20} {5, 40}     {9, 90}",
                 "                           ┌───┴┐  ",
                 "                        {7, 70}    "
               ],
               "\n"
             )
  end
end
Operator	Description	Example
name:	Match package name. Supports * wildcards and repo/package form	name:phx* or name:hexpm/phoenix
description:	Full-text search of package descriptions	description:auth
depends:	Packages depending on a given package. Supports repo:package form	depends:ecto or depends:hexpm:ecto
build_tool:	Filter by build tool	build_tool:mix
updated_after:	Packages updated after an ISO8601 datetime	updated_after:2025-01-01T00:00:00Z
extra:	Match custom metadata (key,value). Nested keys are separated by commas	extra:license,MIT