example_test.go 1.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
  1. // example_test.go - AVL tree example.
  2. //
  3. // To the extent possible under law, Yawning Angel has waived all copyright
  4. // and related or neighboring rights to avl, using the Creative
  5. // Commons "CC0" public domain dedication. See LICENSE or
  6. // <http://creativecommons.org/publicdomain/zero/1.0/> for full details.
  7. package avl
  8. import "fmt"
  9. func CompareIntegers(a, b interface{}) int {
  10. // Returns < 0, 0, > 1 if a < b, a == b, a > b respectively.
  11. return a.(int) - b.(int)
  12. }
  13. func Example() {
  14. // Create a new tree that will store integers.
  15. tree := New(CompareIntegers)
  16. // Insert a handful of integers in random order.
  17. s := []int{5, 2, 6, 3, 1, 4}
  18. for _, i := range s {
  19. tree.Insert(i)
  20. }
  21. // Traverse the tree forward in-order.
  22. forwardInOrder := make([]int, 0, len(s))
  23. tree.ForEach(Forward, func(node *Node) bool {
  24. forwardInOrder = append(forwardInOrder, node.Value.(int))
  25. return true
  26. })
  27. fmt.Println(forwardInOrder)
  28. // Traverse the tree backward using an interator.
  29. backwardInOrder := make([]int, 0, len(s))
  30. iter := tree.Iterator(Backward)
  31. for node := iter.First(); node != nil; node = iter.Next() {
  32. backwardInOrder = append(backwardInOrder, node.Value.(int))
  33. // It is safe to remove the current node while iterating.
  34. tree.Remove(node)
  35. }
  36. fmt.Println(backwardInOrder)
  37. // The tree is empty after the Remove() calls.
  38. fmt.Println(tree.Len())
  39. // Output: [1 2 3 4 5 6]
  40. // [6 5 4 3 2 1]
  41. // 0
  42. }