trees

package
v0.0.0-...-08da8a6 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 30, 2020 License: MIT Imports: 4 Imported by: 0

README

Trees

This package implements some common tree data structures and its extensions.

  • Binary Search Tree
  • Max(Min) Heap
  • Indexed Priority Queue (using Heap)

Binary Search Tree

Binary Search Tree has the following properties:

  • The values in left sub-tree nodes are always smaller than the value in the root.
  • The values in the right sub-tree nodes are always bigger than the value in the root.
Insert

To insert a node into a binary search tree, just compare it with the current root, if it's smaller than the root, insert it into the left sub-tree, otherwise, insert into the right sub-tree. The time complexity is O(logN), the worse case scenario is O(N), in which case, the tree is extremely unbalanced and is essentially a linked list. The space complexity is O(N).

To search a node, it's the same of insertion, starting from the root, if the value matches, return; if the value is smaller than the root's value, search it recursively in the left sub-tree; if the value is bigger than the root's value, search it recursively in the right sub-tree. The time complexity is O(logN), the worse case scenario is O(N), in which case, the tree is extremely unbalanced and is essentially a linked list. The space complexity is O(N).

Deletion

Deleting a node is tricky, first of all, find the node by the searching method. When the node is found, there are a few cases:

  • The node is a leaf: we point the parent of this node to nil.
  • The node has only left child: we point parent of this node to its left child.
  • The node has only right child: we point parent of this node to its right child.
  • The node has both children:
    • We find the maximum value in the node's left sub-tree.
    • We assign this value to the node.
    • We point the node's parent to the maximum node's left sub-tree.

Tips: To make the deletion work, we make a fake parent who's right child is the root to start with.

The time complexity is O(logN), but the same as the above, worse case is O(N). The space complexity is O(N).

Max(Min) Heap

Heap has the following properties:

  • A heap is a Complete Binary Tree
  • A Complete Binary Tree is a tree that:
    • Every level is completely filled, except that the last level can be partially filled.
    • If a node is partially filled, its child must be the left child.
  • For a given node in a heap, the values of the nodes for its children are always smaller&bigger than this node's value, for Max and Min heap respectively.
  • The sub-trees of a node are also heaps.

Notes: The best way to store a heap is using an array list. for a given node with index i, the left child is i * 2, the right child is i * 2 + 1 for a given node with index i, the parent node is i / 2. The root node is at index 1. We can use list[0] as a functional slot in heap operations.

For the following section, we assume it's a Max heap, for Min heap it's all the same, only the comparison is the other way round.

Build Heap For a List

To build a heap from a given list, we do the following:

  • Start from the parent of the last node, and loop back toward the root of the heap, for each of them:

    • If the node doesn't have left node, finish.
    • Find the node with larger value, let it be left or right.
    • If this value is not bigger than the value of the node, finish.
    • Otherwise switch the value, and let the current node to be this node.
    • Repeat.

    The time complexity of this operation is O(N). The space complexity of this operation is O(N).

Insert

To insert a node into a heap, just attach it to the end of the list, which makes it the last leaf node. Then we do the following to make sure the heap is still valid:

  • Start from the last leaf node you just added.
  • Compare the node with its parent's value, if this value is bigger than the value of its parent, switch the value.
  • Let the parent node be the current one, repeat the last operation unless we reach the root.

The time complexity of this operation is O(logN). The space complexity of this operation is O(N).

Peek/Pop

Peek is just to get the value of the top node. Pop is to assign the value of the last node to the top node, and remove the last node. Then do the following:

  • Start from the root where index = 1

  • If the node has no children, finish.

  • Compare the value with its left and right child's value, get the large one, if it's the node itself, finish.

  • If the largest value is the left or right child, switch this value with the node, and left node = node with largest value, repeat.

  • The node is a leaf: we point the parent of this node to nil.

  • The node has only left child: we point parent of this node to its left child.

  • The node has only right child: we point parent of this node to its right child.

  • The node has both children:

    • We find the maximum value in the node's left sub-tree.
    • We assign this value to the node.
    • We point the node's parent to the maximum node's left sub-tree.

The time complexity of this operation is O(logN). The space complexity of this operation is O(N).

Segment Tree

Segment Tree basically is used to speed up the following operation:

  • For a given array of size N, from a range i to j, where 0 <= i < N and i <= j < N, query the minimum, maximum or sum from the range.

A naive approach is to traverse from i to j, and find the minimum, maximum or calculate the sum, this will introduce a time complexity of O(N), assuming N is very large.

The segment tree however, can speed up this range query to a time complexity of O(logN), by reducing the searching range, it's actually a binary search tree.

The segment tree can be defined as follows:

  • For an array A of a length of N, the segment tree has 2N - 1 nodes.
  • The segment tree is a complete binary tree.
  • Each node of a segment tree store a segment or interval of the array.
  • The leaf nodes are elements of array from A[0] to A[N-1].
  • The root of will represent the whole array A[0~N).
  • The internal nodes represent the union of elementary intervals/segment for A[i~j].

Tips: since segment tree is a complete binary tree, the best way to store it is to use an array and start the node at index 1, then for each node i, the left node is at i2, and right node is at i2+1.

For a segment tree, there are basically two things we can do about it once we built it, update and query.

Build the segment tree

The best way to build the segment tree is to build it from bottom up because we know from tree[n] to tree[2n-1], these leaf nodes represents A[i] to A[i-1], which are the values of the array. And also for a complete binary tree, a node's left child is node*2, right child is node * 2 + 1. The following code assumes we are calculating sum:

build(array) {
  for i = 0; i < len(array); i++ {
    tree[i+n] = array[i]
  }
  node := n - 1
  for node > 0 {
    tree[node] = tree[node*2] + tree[node*2+1]
  }
}
Update the segment tree

Update a value is very straightforward as we will just update it and propagate the updates from bottom to up. The following code assumes we are calculating sum.

update(i val) {
    // take the update.
    tree[i+n] = val
    node = i + n
    // if node is not the root.
    for node > 1 {
      left, right = node, node
      if node % 2 == 0 {
        // if node is the left child.
        right += 1
      } else {
        left -= 1
      }
      // update parent
      tree[node/2] = sum(tree[left] + tree[right])
      node /= 2
    }
}
Query the segment tree

The query operations query from i to j, which corresponds to the n+i and n+j leaf nodes. We call it left and right. As long as left <= right, we can keep looking back to their parents. But there are two cases we need to take care of:

  • If left is the right child, then we can't take its parent's value as the left child is out of the scope.
  • If right is the left child, then we can't take its parent's value as the right child is out of the scope. The following code assumes we are getting sum.
query(i, j) {
  left = n+i
  right = n+j
  for left <= right {
    if left % 2 == 1 {
      sum += tree[left]
      left++
    }
    if right % 2 == 0 {
      sum += tree[right]
      right--
    }
    // go to their parents
    left /= 2
    right /= 2
  }
  return sum
}

Binary Indexed Tree

Imaging a scenario, you are given an array of N, and your task is to query the sum of from 0 to i and update the value of i, where i < N. How would you do it? The most naive way would be store the array of N as it is, then

  • To get the sum from 0 to i, the time complexity will be O(N).
  • To update a value at i, the time complexity will be O(1). If you are going to update the array very frequently and rarely calculate the sum, this approach might be ok. However, if you wanna speed up the get sum operation, you could store the prefix-accumulated sum in another array B, so that B[i] = A[0] + ... + A[i], then
  • To get the sum from 0 to 9, the time complexity will be O(1).
  • To update a value at i, you have to update all elements in B[i] to B[N-1], thus the time complexity is O(N).

Is there a way to make the get sum and the update operation both faster? Yes, that's where Binary Indexed Tree comes in to play. Instead of storing the prefix-accumulated sum, the idea of Binary Indexed Tree is to store the postfix-accumulated sum in an array C, where:

C[i] = A[i] + A[i-1] + ... + A[i-lowbit(i)+1]

Note that here i is 1-indexed, not 0-indexed.

So the key the lowbit function, what it does is, for a given integer x, turn it into binrary format, then turn all bits into 0, except for the first 1 encountered, from low bit to high bit. e.g. 6 => 0110 => lowbit(0110) => 0010.

If we visualize the Indexed Binrary Tree, we will see the following:

                                  C[8]
                                /   |
                              /     |
                            /       |
                          /         |
                        /           |
                      /             |
                    /               |
                  /                ...
              C[4]              /   |
             /  |             /     |
           /    |           /       |
         /      |         /         |
     C[2]      ...      C[6]       ...
     /|       / |      /  |      /  |
C[1] ...  C[3] ...  C[5] ...  C[7] ...
 |    |    |    |    |    |    |    |
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

And we can see:

C[1] = A[1]                                     (1 => 001 => lowbit(001) => 001, C[1] = A[1] + ... + A[1-1+1])
C[2] = A[2]+A[1]                                (2 => 010 => lowbit(010) => 010, C[2] = A[2] + ... + A[2-2+1])
C[3] = A[3]                                     (3 => 011 => lowbit(001) => 001, C[2] = A[3] + ... + A[3-1+1])
C[4] = A[4]+A[3]+A[2]+A[1]                      (4 => 100 => lowbit(100) => 100, C[4] = A[4] + ... + A[4-4+1])
C[5] = A[5]                                     (5 => 101 => lowbit(001) => 001, C[1] = A[5] + ... + A[5-1+1])
C[6] = A[6]+A[5]                                (6 => 110 => lowbit(010) => 010, C[6] = A[6] + ... + A[6-2+1])
C[7] = A[7]                                     (7 => 111 => lowbit(001) => 001, C[7] = A[7] + ... + A[7-1+1])
C[8] = A[8]+A[7]+A[6]+A[5]+A[4]+A[3]+A[2]+A[1]  (8 => 1000 => lowbit(1000) => 1000, C[8] = A[8] + ... + A[8-8+1])
Build the Binary Indexed Tree

Building the tree essentially is to construct the array C from the given input A.

build(C, A, N) {
  for i = 1; i <= N; i++ {
    // from tree bottom, update to up.
    val = A[i]
    for i <= N {
      C[i] += val
      i += lowbit(i)
    }
  }
}
// A and C is 1-indexed.

The time complexity is O(NlogN)

Get Sum using the Binary Indexed Tree
getSum(C, j) int {
  res = 0
  for j > 0 {
    res += C[j]
    j -= lowbit(j)
  }
}
// C is 1-indexed

The time complexity is O(logN)

Update a idx by delta using the Binary Indexed Tree
update(C, i, delta) {
  for i <= N {
    C[i] += delta
    i += lowbit(1)
  }
}

The time complexity is O(logN)

Trie Tree

Trie Tree is also called Radix Tree, or Prefix Tree. It's a search tree that can be used store a collection of strings and provides the following functionality:

  • Insert a string into the trie tree.
  • Search exactly a string from the trie tree.
  • Count the occurrence of strings.
  • Sort strings.
  • Auto-completion, as in, for a given prefix, find out all strings that share the same prefix.

We can define the Trie Tree as follows:

  • The root node does not contain any character, it represents "".
  • Each other node has only one character, assembling all the characters from the root node down to this node forms a prefix string.
  • Each non-leaf node contains 0 - 26 children, representing a-z.
  • All the strings that are represented by the children a node, share the the same prefix mentioned above.
  • Do a pre-order traversing of the trie tree can prints all strings that are stored in it.

The following gives an example:

                                    root
                                    /  \
                                  'a'  'b'
                                  /      \
                                 'b'     'e'
                                /        / \
                               'u'      'e' 'd'
                              /
                            's'
                            /
                           'e'

The above trie tree represents the collection of strings ["abuse", "bee", "bed", "be"].

Please note that, to be able to have "be" marked as a string, we need a flag in the tree node.

Inserting into a trie tree.

Inserting into a trie is a process of a travering down the tree based on the string to be inserted.

  • for each character in the string, 0 <= i < N, where N is the length of the string.
  • At a given node, if it has a child that matches the current character, move the node to this child.
  • At a given ndoe, if it does not have a child that matches the current character, create the child with the value of this character and move the node to this child.
  • repeat until all character of the strings are inserted, when reaching the last character, mark the node using a flag to indicate it represents a string, optionally, we can have a count field in a node to count occurrence of the string.

Storing all children nodes for a node using [26]*TreeNode is a trick, because we only have a-z in alphabet.

Search from a trie tree.

For a given prefix, we can find out all the strings that started with it. If prefix == "", it means all the strings.

  • Starting from the root, we will firstly search down the tree to find out whether prefix exists by matching character by character.
  • If prefix does not exist, return empty.
  • If find the prefix, at a node, we will print all the strings represented by this node's subtrees.
  • In order to achieve it, we can use a pre-order DFS traverse.

With the above operations, we can achieve what we want using trie tree.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BTree 

type BTree struct {
	Root *BTreeNode // root has min 2 children if it's not leaf.
	// contains filtered or unexported fields
}

BTree defines a B-Tree

func NewBTree 

func NewBTree(order int, comparator shared.Comparator) *BTree

NewBTree creates a new B-Tree

func (*BTree) Clear 

func (b *BTree) Clear()

Clear clears the B-Tree

func (*BTree) Delete 

func (b *BTree) Delete(key interface{}) (value interface{}, err error)

Delete deletes the key (index) and its value from the B-Tree

func (*BTree) GetHeight 

func (b *BTree) GetHeight() int

GetHeight gets the height of the B-Tree.

func (*BTree) GetSize 

func (b *BTree) GetSize() int

GetSize gets the total number of values.

func (*BTree) Put 

func (b *BTree) Put(key, value interface{})

Put puts an key (index) and it's value into the B-Tree, if the key exists, update the value

func (*BTree) Search 

func (b *BTree) Search(key interface{}) (node *BTreeNode, index int, err error)

Search searchs the key (index) to get the value from the B-Tree

type BTreeNode 

type BTreeNode struct {
	Keys     []interface{} // The separation keys, for non-leaf node, count = count(children) - 1
	Values   []interface{}
	Children []*BTreeNode // The childrens, maximum at order
	Parent   *BTreeNode
}

BTreeNode defines a B-Tree Node

type BinaryIndexedTree 

type BinaryIndexedTree struct {
	// contains filtered or unexported fields
}

BinaryIndexedTree defines a binary indexes tree

func NewBinaryIndexedTree 

func NewBinaryIndexedTree(input []int) *BinaryIndexedTree

NewBinaryIndexedTree creates a binary indexes tree from a given input array.

func (*BinaryIndexedTree) GetSum 

func (b *BinaryIndexedTree) GetSum(idx int) int

GetSum returns the sum of values from index 0 to idx.

func (*BinaryIndexedTree) RangeSum 

func (b *BinaryIndexedTree) RangeSum(i, j int) int

RangeSum gets the range sum from idx i to j. where i and j is from [0, N).

func (*BinaryIndexedTree) Update 

func (b *BinaryIndexedTree) Update(idx, delta int)

Update updates the val at idx by a delta, idx is from 0 to N-1

type BinarySearchTree 

type BinarySearchTree struct {
	BinaryTree
	// contains filtered or unexported fields
}

BinarySearchTree defines a binary search tree

func (*BinarySearchTree) Clear 

func (b *BinarySearchTree) Clear()

Clear clears the binary search tree.

func (*BinarySearchTree) ConvertFromDoubleLinkedList 

func (b *BinarySearchTree) ConvertFromDoubleLinkedList(head *BinaryTreeNode, length int)

ConvertFromDoubleLinkedList converts double linked list back to

func (*BinarySearchTree) ConvertToDoubleLinkedList 

func (b *BinarySearchTree) ConvertToDoubleLinkedList() (head *BinaryTreeNode, tail *BinaryTreeNode)

ConvertToDoubleLinkedList converts the BST to A Double Linked List.

func (*BinarySearchTree) Delete 

func (b *BinarySearchTree) Delete(data interface{}) error

Delete deletes a data node from binary search tree.

func (*BinarySearchTree) GetSize 

func (b *BinarySearchTree) GetSize() int

GetSize gets the size of the tree.

func (*BinarySearchTree) Put 

func (b *BinarySearchTree) Put(key, value interface{})

Put puts a data node into the binary search tree, if the key exists already, update its value.

func (*BinarySearchTree) Search 

func (b *BinarySearchTree) Search(key interface{}) (value interface{})

Search searchs value by key.

func (*BinarySearchTree) ToSortedSlice 

func (b *BinarySearchTree) ToSortedSlice() []interface{}

ToSortedSlice traverse the tree and store the data into a sorted slice

type BinaryTree 

type BinaryTree struct {
	Root       *BinaryTreeNode
	Comparator shared.Comparator
}

BinaryTree defines a general binary tree

func (*BinaryTree) BreadthFirstTraverse 

func (b *BinaryTree) BreadthFirstTraverse() []interface{}

BreadthFirstTraverse traverse the tree breadth-first way, a.k.a level by level. The idea is to use a QUEUE to store candidate left and right children along the way.

func (*BinaryTree) DepthFirstTraverse 

func (b *BinaryTree) DepthFirstTraverse() []interface{}

DepthFirstTraverse traverse the tree depth-first way. The idea is to use a STACK to store candidate right and left children along the way.

type BinaryTreeNode 

type BinaryTreeNode struct {
	Key   interface{}
	Value interface{}
	Left  *BinaryTreeNode
	Right *BinaryTreeNode
}

BinaryTreeNode defines a tree node of a binary search tree

type Heap 

type Heap struct {
	HeapType HeapType

	Comparator shared.Comparator
	// contains filtered or unexported fields
}

Heap defines a heap

func (*Heap) GetValues 

func (h *Heap) GetValues() []interface{}

GetValues gets the values of the heap

func (*Heap) InitHeap 

func (h *Heap) InitHeap(values []interface{})

InitHeap initializes a heap using a list of values.

func (*Heap) Insert 

func (h *Heap) Insert(data interface{})

Insert inserts a node into a heap

func (*Heap) Peek 

func (h *Heap) Peek() interface{}

Peek returns the top value of the heap

func (*Heap) Pop 

func (h *Heap) Pop() interface{}

Pop returns the top value of the heap.

func (*Heap) Size 

func (h *Heap) Size() int

Size gets the current size

type HeapType 

type HeapType int

HeapType defines the heap type 

const (
	HeapTypeMax HeapType = iota
	HeapTypeMin
)

Enum values of HeapType

type IndexedPriorityQueue 

type IndexedPriorityQueue struct {
	// contains filtered or unexported fields
}

IndexedPriorityQueue defines an indexed priority queue based on a heap.

func NewIndexedPriorityQueue 

func NewIndexedPriorityQueue(capacity int, heapType HeapType, comparator shared.Comparator) *IndexedPriorityQueue

NewIndexedPriorityQueue creates a new indexed priority queue with capacity, heapType and value comparator specified

func (*IndexedPriorityQueue) ChangeValue 

func (i *IndexedPriorityQueue) ChangeValue(index int, value interface{}) error

ChangeValue changes the value at a given index, if the index is out of range or no value was added, error will be returned.

func (*IndexedPriorityQueue) Contains 

func (i *IndexedPriorityQueue) Contains(index int) bool

Contains check whether the queue contains a value with the given index.

func (*IndexedPriorityQueue) DeleteValue 

func (i *IndexedPriorityQueue) DeleteValue(index int) error

DeleteValue deletes the value at a given index, if the index is out of range or no value was added, error will be returned.

func (*IndexedPriorityQueue) GetValue 

func (i *IndexedPriorityQueue) GetValue(index int) (interface{}, error)

GetValue gets value at a given index, if index is out of range or no value was added, error will be returned.

func (*IndexedPriorityQueue) Insert 

func (i *IndexedPriorityQueue) Insert(index int, value interface{}) error

Insert inters a value into the queue with a given index, if the index is not valid or is taken, error will be return.

func (*IndexedPriorityQueue) IsEmpty 

func (i *IndexedPriorityQueue) IsEmpty() bool

IsEmpty returns whether the queue is empty.

func (*IndexedPriorityQueue) Peek 

func (i *IndexedPriorityQueue) Peek() (index int, value interface{}, err error)

Peek peeks the priority queue, it returns the heap top value with it's index. if queue is empty, error will be returned.

func (*IndexedPriorityQueue) Pop 

func (i *IndexedPriorityQueue) Pop() (index int, value interface{}, err error)

Pop returns the heap top value of the queue, and remove it from the queue in the meantime, error will be returned if queue is empty.

func (*IndexedPriorityQueue) Size 

func (i *IndexedPriorityQueue) Size() int

Size returns the number of values stored in the queue.

type SegmentTree 

type SegmentTree struct {
	// contains filtered or unexported fields
}

SegmentTree represents a segment tree.

func NewSegmentTree 

func NewSegmentTree(input []int, segmentTreeType SegmentTreeType) *SegmentTree

NewSegmentTree creates a segment tree for the input array.

func (*SegmentTree) Query 

func (s *SegmentTree) Query(i, j int) int

Query queries the result from range i to j. Then we can get it's real position in nodes at left and right. Where left = n + i, and right = n + j. As long as i <= j, we can exam the value at i and j first and then move up to their parents level.

func (*SegmentTree) Update 

func (s *SegmentTree) Update(i, update int)

Update updates the value of a given index i. The idea is that, for a given index i, the leaf node of it is at n + i We will then propogate the update from bottom to up.

type SegmentTreeType 

type SegmentTreeType int

SegmentTreeType defines the segment tree types. 

const (
	SegmentTreeMin SegmentTreeType = iota + 1
	SegmentTreeMax
	SegmentTreeSum
)

Define 3 types of segment tree. These are for 3 types of query respectively, query range minimum, range max and range sum.

type TrieNode 

type TrieNode struct {
	// contains filtered or unexported fields
}

TrieNode defines a trie node.

type TrieTree 

type TrieTree struct {
	// contains filtered or unexported fields
}

TrieTree defines a trie tree.

func NewTrieTree 

func NewTrieTree() *TrieTree

NewTrieTree creates a new trie tree with no strings

func (*TrieTree) Count 

func (t *TrieTree) Count(str string) int

Count counts the number of apperances of a given str.

func (*TrieTree) GetAll 

func (t *TrieTree) GetAll() []string

GetAll returns all strings stored in the trie tree.

func (*TrieTree) Insert 

func (t *TrieTree) Insert(str string)

Insert inserts a string into the trie tree.

func (*TrieTree) Search 

func (t *TrieTree) Search(str string) bool

Search searches a given str against a trie tree and see whether it exists.

func (*TrieTree) StartsWith 

func (t *TrieTree) StartsWith(prefix string) []string

StartsWith returns all strings that starts with the prefix.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.