NOTE
2.7 tree
Binary trees, BST, AVL tree, Trie, and Huffman tree.
This is a historical learning note and may contain outdated or incomplete understanding.
1. What Is a Binary Tree
Each node has at most two child nodes.
2. Binary Tree Operations
2.1. Traversal
2.1.1. Preorder Traversal
Visit the root first, then the left subtree, and finally the right subtree.
2.1.2. Inorder Traversal
Visit the left subtree first, then the root, and finally the right subtree.
2.1.3. Postorder Traversal
Visit the left subtree first, then the right subtree, and finally the root.
2.1.4. Depth-First Traversal
It is essentially preorder traversal + backtracking.
2.1.5. Breadth-First Traversal
Use a queue. Every time a node is visited, add its left and right children to the queue.
2.2. Predecessor and Successor
2.2.1. Predecessor
// Predecessor: the previous node in inorder traversal, and the largest node smaller than the current node
func predecessor(n *node) *node {
if n == nil {
return nil
}
// The left subtree is non-empty
if n.left != nil {
return max(n.left)
}
// The left subtree is empty but the parent is non-nil
for n.parent != nil {
if n.parent.right == n {
return n.parent
}
n = n.parent
}
// Both the left subtree and the parent are nil
return nil
}2.2.2. Successor
// Successor: the next node in inorder traversal, and the smallest node larger than the current node
func successor(n *node) *node {
if n == nil {
return nil
}
// The right subtree is non-empty
if n.right != nil {
return min(n.right)
}
// The right subtree is empty but the parent is non-nil
for n.parent != nil {
if n.parent.left == n {
return n.parent
}
n = n.parent
}
// Both the right subtree and the parent are nil
return nil
}3. Binary Tree Categories
3.1. Full Binary Tree
3.2. Complete Binary Tree
3.3. Binary Search Tree 【BST Tree】
All nodes in the left subtree < root node < all nodes in the right subtree. Unlike heap, a heap has parent value > left and right child values.
3.3.1. Data Structure
- Binary-tree nodes
- Length
3.3.2. API
type IBinarySearchTree interface {
// Print the binary tree
String() string
// Number of nodes in the binary tree
Length() int
// Whether the binary tree is empty
IsEmpty() bool
// Add an element to the binary tree
Add(data model.Comparable)
// Whether the binary tree contains an element
Contains(data model.Comparable) bool
// Preorder traversal
PreOrder() []*node
// Inorder traversal
InOrder() []*node
// Postorder traversal
PostOrder() []*node
// Level-order traversal
LevelOrder() []*node
// Maximum value in the binary tree
Max() *node
// Minimum value in the binary tree
Min() *node
// Delete an element from the binary tree
Remove(data model.Comparable)
// Delete the maximum element from the binary tree
RemoveMax() *node
// Delete the minimum element from the binary tree
RemoveMin() *node
}3.3.3. Implementation
type node struct {
data model.Comparable
left *node
right *node
}
func (n *node) String() string {
return fmt.Sprintf("%v", n.data)
}
func newNode(value model.Comparable) *node {
return &node{
data: value,
}
}
type BinarySearchTree struct {
root *node
length int
}
func NewBinarySearchTree() *BinarySearchTree {
return &BinarySearchTree{}
}
func (b *BinarySearchTree) String() string {
s := fmt.Sprintf("length=%v, data={", b.Length())
if b.root == nil {
s += "}"
return s
}
line := make([]model.Comparable, 0)
allLines := make([][]model.Comparable, 0)
queue := list.New()
queue.PushBack(b.root)
currentLineLast := b.root
var nextLineLast *node
for queue.Len() > 0 {
n := queue.Remove(queue.Front()).(*node)
line = append(line, n.data)
if n.left != nil {
queue.PushBack(n.left)
nextLineLast = n.left
}
if n.right != nil {
queue.PushBack(n.right)
nextLineLast = n.right
}
if n == currentLineLast {
currentLineLast = nextLineLast
allLines = append(allLines, line)
line = make([]model.Comparable, 0)
}
}
for _, l := range allLines {
s += fmt.Sprintf("%v\n", l)
}
s += "}"
return s
}
func (b *BinarySearchTree) Length() int {
return b.length
}
func (b *BinarySearchTree) IsEmpty() bool {
return b.root == nil
}
func (b *BinarySearchTree) Add(data model.Comparable) {
b.root = add(b.root, data)
b.length++
}
func add(n *node, data model.Comparable) *node {
if n == nil {
return newNode(data)
}
if data.CompareTo(n.data) <= 0 {
// The following code is only for easier understanding
//if n.left == nil {
// n.left = newNode(data)
// return n
//}
n.left = add(n.left, data)
return n
} else {
//if n.right == nil {
// n.right = newNode(data)
// return n
//}
n.right = add(n.right, data)
return n
}
}
func (b *BinarySearchTree) Contains(data model.Comparable) bool {
return contains(b.root, data)
}
func contains(node *node, data model.Comparable) bool {
if node == nil {
return false
}
if data.CompareTo(node.data) < 0 {
return contains(node.left, data)
} else if data.CompareTo(node.data) > 0 {
return contains(node.right, data)
} else {
return true
}
}
func (b *BinarySearchTree) PostOrderNoRecur() []*node {
res := make([]*node, 0)
if b.root == nil {
return res
}
stack := make([]*node, 0)
stack = append(stack, b.root)
var prev *node
for len(stack) > 0 {
top := stack[len(stack)-1]
if isLeaf(top) || hasVisitedChild(prev, top) {
prev = top
stack = stack[:len(stack)-1]
res = append(res, top)
} else {
if top.right != nil {
stack = append(stack, top.right)
}
if top.left != nil {
stack = append(stack, top.left)
}
}
}
return res
}
func hasVisitedChild(child *node, parent *node) bool {
return child != nil && (parent.right == child || parent.left == child)
}
func isLeaf(n *node) bool {
return n.left == nil && n.right == nil
}
func (b *BinarySearchTree) PreOrderNoRecur() []*node {
res := make([]*node, 0)
if b.root == nil {
return res
}
stack := make([]*node, 0)
stack = append(stack, b.root)
for len(stack) > 0 {
current := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, current)
if current.right != nil {
stack = append(stack, current.right)
}
if current.left != nil {
stack = append(stack, current.left)
}
}
return res
}
func (b *BinarySearchTree) InOrderNoRecur() []*node {
res := make([]*node, 0)
stack := make([]*node, 0)
current := b.root
for {
if current != nil {
stack = append(stack, current)
current = current.left
} else if len(stack) == 0 {
return res
} else {
current = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, current)
current = current.right
}
}
}
func (b *BinarySearchTree) PreOrder() []*node {
datas := make([]*node, 0)
preOrder(b.root, &datas)
return datas
}
func preOrder(node *node, datas *[]*node) {
if node == nil {
return
}
*datas = append(*datas, node)
preOrder(node.left, datas)
preOrder(node.right, datas)
}
func (b *BinarySearchTree) InOrder() []*node {
datas := make([]*node, 0)
inOrder(b.root, &datas)
return datas
}
func inOrder(node *node, datas *[]*node) {
if node == nil {
return
}
inOrder(node.left, datas)
*datas = append(*datas, node)
inOrder(node.right, datas)
}
func (b *BinarySearchTree) PostOrder() []*node {
datas := make([]*node, 0)
postOrder(b.root, &datas)
return datas
}
func postOrder(node *node, datas *[]*node) {
if node == nil {
return
}
postOrder(node.left, datas)
postOrder(node.right, datas)
*datas = append(*datas, node)
}
func (b *BinarySearchTree) LevelOrder() []*node {
datas := make([]*node, 0)
levelOrder(b.root, &datas)
return datas
}
func levelOrder(n *node, datas *[]*node) {
if n == nil {
return
}
queue := list.New()
queue.PushBack(n)
for queue.Len() > 0 {
e := queue.Remove(queue.Front()).(*node)
*datas = append(*datas, e)
if e.left != nil {
queue.PushBack(e.left)
}
if e.right != nil {
queue.PushBack(e.right)
}
}
}
func (b *BinarySearchTree) Remove(data model.Comparable) {
if b.root == nil {
return
}
b.root = b.remove(b.root, data)
}
func (b *BinarySearchTree) remove(n *node, data model.Comparable) *node {
if n == nil {
return nil
}
// Find the node to delete
if data.CompareTo(n.data) < 0 {
n.left = b.remove(n.left, data)
return n
} else if data.CompareTo(n.data) > 0 {
n.right = b.remove(n.right, data)
return n
} else {
// Perform the deletion
b.length--
return doRemove(n)
}
}
func doRemove(n *node) *node {
// The left subtree is empty
// Delete the current node and move the right subtree up as the root
// Similar to removeMin
if n.left == nil {
rightNode := n.right
n.right = nil
return rightNode
}
// The right subtree is empty
// Delete the current node and move the left subtree up as the root
// Similar to removeMax
if n.right == nil {
leftNode := n.left
n.left = nil
return leftNode
}
// Both the left and right subtrees are non-empty
// First find the successor of the current node, i.e. the minimum node in the right subtree, to replace this node
successor := min(n.right)
successor.right = removeMin(n.right)
successor.left = n.left
// Delete the current node
n.left = nil
n.right = nil
return successor
}
func (b *BinarySearchTree) Max() *node {
if b.root == nil {
return nil
}
return max(b.root)
}
func max(n *node) *node {
if n.right == nil {
return n
}
return max(n.right)
}
func (b *BinarySearchTree) Min() *node {
if b.root == nil {
return nil
}
return min(b.root)
}
func min(n *node) *node {
if n.left == nil {
return n
}
return min(n.left)
}
func (b *BinarySearchTree) RemoveMax() *node {
if b.root == nil {
return nil
}
e := b.Max()
b.root = removeMax(b.root)
b.length--
return e
}
func removeMax(n *node) *node {
if n == nil {
return nil
}
// If the right subtree is empty, the current node is the maximum node
// Delete the current node and move the left subtree up as the root
if n.right == nil {
leftNode := n.left
n.left = nil
return leftNode
}
n.right = removeMax(n.right)
return n
}
func (b *BinarySearchTree) RemoveMin() *node {
if b.root == nil {
return nil
}
e := b.Min()
b.root = removeMin(b.root)
b.length--
return e
}
func removeMin(n *node) *node {
if n == nil {
return nil
}
// If the left subtree is empty, the current node is the minimum node
// Delete the current node and move the right subtree up as the root
if n.left == nil {
rightNode := n.right
n.right = nil
return rightNode
}
n.left = removeMin(n.left)
return n
}
3.3.3.1. Test
func TestBST(t *testing.T) {
bst := NewBinarySearchTree()
e1 := model.NewElement(1)
e2 := model.NewElement(2)
e3 := model.NewElement(3)
e4 := model.NewElement(4)
e5 := model.NewElement(5)
bst.Add(e3)
bst.Add(e2)
bst.Add(e4)
bst.Add(e1)
bst.Add(e5)
fmt.Println("Initial data: ", bst)
fmt.Println("Level-order traversal: ", bst.LevelOrder())
fmt.Println("Preorder traversal: ", bst.PreOrder())
fmt.Println("Preorder traversal (iterative): ", bst.PreOrderNoRecur())
fmt.Println("Inorder traversal: ", bst.InOrder())
fmt.Println("Inorder traversal (iterative): ", bst.InOrderNoRecur())
fmt.Println("Postorder traversal: ", bst.PostOrder())
fmt.Println("Postorder traversal (iterative): ", bst.PostOrderNoRecur())
fmt.Println("Minimum node: ", bst.Min())
fmt.Println("Maximum node: ", bst.Max())
fmt.Println("Delete minimum node: ", bst.RemoveMin())
fmt.Println("After deleting the minimum node: ", bst)
bst.Remove(e3)
fmt.Println("After deleting the root node: ", bst)
}3.4. Balanced Binary Search Tree 【AVL Tree】
In the worst case, a binary search tree can degenerate into a linked list, giving O(N) efficiency, so AVL trees are introduced. AVL adds one condition on top of BST: the absolute value of the balance factor <= 1. The balance factor is defined as the difference between the heights of the left and right subtrees.
- Example
The tree above is not balanced. The number on the left of each node is its height, and the number above is its balance factor. It is clear that some balance factors are > 1.
3.4.1. Data Structure
- Same as binary search tree
3.4.2. API
type IAVLTree interface {
// Print the binary tree
String() string
// Number of nodes in the binary tree
Length() int
// Whether the binary tree is empty
IsEmpty() bool
// Add an element to the binary tree
Add(data model.Comparable)
// Whether the binary tree contains an element
Contains(data model.Comparable) bool
// Preorder traversal
PreOrder() []*node
// Inorder traversal
InOrder() []*node
// Postorder traversal
PostOrder() []*node
// Level-order traversal
LevelOrder() []*node
// Maximum value in the binary tree
Max() *node
// Minimum value in the binary tree
Min() *node
// Delete an element from the binary tree
Remove(data model.Comparable)
}3.4.3. Implementation
type node struct {
data model.Comparable
left *node
right *node
height int
}
func (n *node) String() string {
return fmt.Sprintf("%v", n.data)
}
func newNode(value model.Comparable) *node {
return &node{
data: value,
height: 1,
}
}
type AVLTree struct {
root *node
length int
}
func NewAVLTree() *AVLTree {
return &AVLTree{}
}
func (a *AVLTree) String() string {
s := fmt.Sprintf("length=%v, data={", a.Length())
if a.root == nil {
s += "}"
return s
}
line := make([]model.Comparable, 0)
allLines := make([][]model.Comparable, 0)
queue := list.New()
queue.PushBack(a.root)
currentLineLast := a.root
var nextLineLast *node
for queue.Len() > 0 {
n := queue.Remove(queue.Front()).(*node)
line = append(line, n.data)
if n.left != nil {
queue.PushBack(n.left)
nextLineLast = n.left
}
if n.right != nil {
queue.PushBack(n.right)
nextLineLast = n.right
}
if n == currentLineLast {
currentLineLast = nextLineLast
allLines = append(allLines, line)
line = make([]model.Comparable, 0)
}
}
for _, l := range allLines {
s += fmt.Sprintf("%v\n", l)
}
s += "}"
return s
}
func (a *AVLTree) Length() int {
return a.length
}
func (a *AVLTree) IsEmpty() bool {
return a.root == nil
}
// Whether this is a binary search tree
func IsBST(n *node) bool {
datas := make([]*node, 0)
inOrder(n, &datas)
for i := 0; i < len(datas)-1; i++ {
if datas[i].data.CompareTo(datas[i+1].data) > 0 {
return false
}
}
return true
}
// Whether this is an AVL tree
func IsBalanced(n *node) bool {
if n == nil {
return true
}
return GetAbsBalanceFactor(n) <= 1 && IsBalanced(n.left) && IsBalanced(n.right)
}
// Get the height of a node
func GetHeight(n *node) int {
if n == nil {
return 0
}
//return n.height
// Or
return 1 + util.Max(GetHeight(n.left), GetHeight(n.right))
}
// Get the height difference between the left and right subtrees
// Return a negative value if the left subtree is shorter
// Return a positive value if the right subtree is shorter
func GetBalanceFactor(n *node) int {
if n == nil {
return 0
}
return GetHeight(n.left) - GetHeight(n.right)
}
// Get the absolute height difference between the left and right subtrees
func GetAbsBalanceFactor(n *node) int {
return util.Abs(GetBalanceFactor(n))
}
func (a *AVLTree) Add(data model.Comparable) {
a.root = add(a.root, data)
a.length++
}
func add(n *node, data model.Comparable) *node {
if n == nil {
return newNode(data)
}
if data.CompareTo(n.data) <= 0 {
// The following code is only for easier understanding
//if n.left == nil {
// n.left = newNode(data)
// return n
//}
n.left = add(n.left, data)
} else {
//if n.right == nil {
// n.right = newNode(data)
// return n
//}
n.right = add(n.right, data)
}
n.height = 1 + util.Max(GetHeight(n.left), GetHeight(n.right))
balanceFactor := GetBalanceFactor(n)
// Maintain balance
// LL
if balanceFactor > 1 && GetBalanceFactor(n.left) >= 0 {
return rightRotate(n)
}
// RR
if balanceFactor < -1 && GetBalanceFactor(n.right) <= 0 {
return leftRotate(n)
}
// LR
if balanceFactor > 1 && GetBalanceFactor(n.left) < 0 {
n.left = leftRotate(n.left)
return rightRotate(n)
}
// RL
if balanceFactor < -1 && GetBalanceFactor(n.right) > 0 {
n.right = rightRotate(n.right)
return leftRotate(n)
}
return n
}
// Left-rotate node y and return x, the new root after rotation
// y x
// / \ / \
// T1 x left rotate (y) y z
// / \ - - - - - - - -> / \ / \
// T2 z T1 T2 T3 T4
// / \
func leftRotate(y *node) *node {
x := y.right
T2 := x.left
// Left-rotation process
x.left = y
y.right = T2
// Update height
y.height = util.Max(GetHeight(y.left), GetHeight(y.right)) + 1
x.height = util.Max(GetHeight(x.left), GetHeight(x.right)) + 1
return x
}
// Right-rotate node y and return x, the new root after rotation
// y x
// / \ / \
// x T4 right rotate (y) z y
// / \ - - - - - - - -> / \ / \
// z T3 T1 T2 T3 T4
// / \
func rightRotate(y *node) *node {
x := y.left
T3 := x.right
// Right-rotation process
x.right = y
y.left = T3
// Update height
y.height = util.Max(GetHeight(y.left), GetHeight(y.right)) + 1
x.height = util.Max(GetHeight(x.left), GetHeight(x.right)) + 1
return x
}
func (a *AVLTree) Contains(data model.Comparable) bool {
return contains(a.root, data)
}
func contains(node *node, data model.Comparable) bool {
if node == nil {
return false
}
if data.CompareTo(node.data) < 0 {
return contains(node.left, data)
} else if data.CompareTo(node.data) > 0 {
return contains(node.right, data)
} else {
return true
}
}
func (a *AVLTree) PreOrder() []*node {
datas := make([]*node, 0)
preOrder(a.root, &datas)
return datas
}
func preOrder(node *node, datas *[]*node) {
if node == nil {
return
}
*datas = append(*datas, node)
preOrder(node.left, datas)
preOrder(node.right, datas)
}
func (a *AVLTree) InOrder() []*node {
datas := make([]*node, 0)
inOrder(a.root, &datas)
return datas
}
func inOrder(node *node, datas *[]*node) {
if node == nil {
return
}
inOrder(node.left, datas)
*datas = append(*datas, node)
inOrder(node.right, datas)
}
func (a *AVLTree) PostOrder() []*node {
datas := make([]*node, 0)
postOrder(a.root, &datas)
return datas
}
func postOrder(node *node, datas *[]*node) {
if node == nil {
return
}
postOrder(node.left, datas)
postOrder(node.right, datas)
*datas = append(*datas, node)
}
func (a *AVLTree) LevelOrder() []*node {
datas := make([]*node, 0)
levelOrder(a.root, &datas)
return datas
}
func levelOrder(n *node, datas *[]*node) {
if n == nil {
return
}
queue := list.New()
queue.PushBack(n)
for queue.Len() > 0 {
e := queue.Remove(queue.Front()).(*node)
*datas = append(*datas, e)
if e.left != nil {
queue.PushBack(e.left)
}
if e.right != nil {
queue.PushBack(e.right)
}
}
}
func (a *AVLTree) Remove(data model.Comparable) {
if a.root == nil {
return
}
a.root = a.remove(a.root, data)
}
func (a *AVLTree) remove(n *node, data model.Comparable) *node {
if n == nil {
return nil
}
var retNode *node
// Find the node to delete
if data.CompareTo(n.data) < 0 {
n.left = a.remove(n.left, data)
retNode = n
} else if data.CompareTo(n.data) > 0 {
n.right = a.remove(n.right, data)
retNode = n
} else {
// Perform the deletion
a.length--
retNode = a.doRemove(n)
}
if retNode == nil {
return nil
}
retNode.height = 1 + util.Max(GetHeight(retNode.left), GetHeight(retNode.right))
balanceFactor := GetBalanceFactor(retNode)
// Maintain balance
// LL
if balanceFactor > 1 && GetBalanceFactor(retNode.left) >= 0 {
return rightRotate(retNode)
}
// RR
if balanceFactor < -1 && GetBalanceFactor(retNode.right) <= 0 {
return leftRotate(retNode)
}
// LR
if balanceFactor > 1 && GetBalanceFactor(retNode.left) < 0 {
retNode.left = leftRotate(retNode.left)
return rightRotate(retNode)
}
// RL
if balanceFactor < -1 && GetBalanceFactor(retNode.right) > 0 {
retNode.right = rightRotate(retNode.right)
return leftRotate(retNode)
}
return retNode
}
func (a *AVLTree) doRemove(n *node) *node {
// The left subtree is empty
// Delete the current node and move the right subtree up as the root
// Similar to removeMin
if n.left == nil {
rightNode := n.right
n.right = nil
return rightNode
}
// The right subtree is empty
// Delete the current node and move the left subtree up as the root
// Similar to removeMax
if n.right == nil {
leftNode := n.left
n.left = nil
return leftNode
}
// Both the left and right subtrees are non-empty
// First find the successor of the current node, i.e. the minimum node in the right subtree, to replace this node
successor := min(n.right)
//successor.right = removeMin(n.right)
// a.remove deletes the successor and decrements length once; offset it here so the whole deletion decrements length only once.
a.length++
successor.right = a.remove(n.right, successor.data)
successor.left = n.left
// Delete the current node
n.left = nil
n.right = nil
return successor
}
func (a *AVLTree) Max() *node {
if a.root == nil {
return nil
}
return max(a.root)
}
func max(n *node) *node {
if n.right == nil {
return n
}
return max(n.right)
}
func (a *AVLTree) Min() *node {
if a.root == nil {
return nil
}
return min(a.root)
}
func min(n *node) *node {
if n.left == nil {
return n
}
return min(n.left)
}3.4.3.1. Test
func TestAVLBST(t *testing.T) {
bst := NewAVLTree()
e1 := model.NewElement(1)
e2 := model.NewElement(2)
e3 := model.NewElement(3)
e4 := model.NewElement(4)
e5 := model.NewElement(5)
bst.Add(e3)
bst.Add(e2)
bst.Add(e4)
bst.Add(e1)
bst.Add(e5)
fmt.Println("Initial data: ", bst)
fmt.Println("Is it a binary search tree? ", IsBST(bst.root))
fmt.Println("Is it an AVL tree? ", IsBalanced(bst.root))
fmt.Println("Level-order traversal: ", bst.LevelOrder())
fmt.Println("Preorder traversal: ", bst.PreOrder())
fmt.Println("Inorder traversal: ", bst.InOrder())
fmt.Println("Postorder traversal: ", bst.PostOrder())
fmt.Println("Minimum node: ", bst.Min())
fmt.Println("Maximum node: ", bst.Max())
bst.Remove(e3)
fmt.Println("After deleting the root node: ", bst)
fmt.Println("Is it an AVL tree? ", IsBalanced(bst.root))
}3.5. Red-Black Tree 【RB Tree】
4. Trie / Prefix Tree 【Trie Tree】
Implement a Trie (Prefix Tree)
4.1. Data Structure
- map
4.2. API
type ITrie interface {
// Print the trie
String() string
// Number of words in the trie
Length() int
// Whether the trie is empty
IsEmpty() bool
// Add a word to the trie
Add(word string)
// Whether the trie contains a word; time complexity is O(m), where m is the maximum string length
Contains(word string) bool
// Whether the trie contains a prefix
IsPrefix(word string) bool
}4.3. Implementation
type node struct {
isWord bool
next map[rune]*node
}
func newNode(isWord bool) *node {
return &node{isWord: isWord, next: make(map[rune]*node)}
}
type Trie struct {
root *node
length int
}
func NewTrie() *Trie {
return &Trie{
root: newNode(false),
length: 0,
}
}
func (t *Trie) String() string {
panic("implement me")
}
func (t *Trie) Length() int {
return t.length
}
func (t *Trie) IsEmpty() bool {
return t.length == 0
}
func (t *Trie) Add(word string) {
current := t.root
runes := []rune(word)
for i := 0; i < len(runes); i++ {
ch := runes[i]
_, ok := current.next[ch]
if !ok {
current.next[ch] = newNode(false)
}
current = current.next[ch]
}
if !current.isWord {
current.isWord = true
t.length++
}
}
func (t *Trie) Contains(word string) bool {
current := t.root
runes := []rune(word)
for i := 0; i < len(runes); i++ {
ch := runes[i]
next, ok := current.next[ch]
if !ok {
return false
}
current = next
}
return current.isWord
}
func (t *Trie) IsPrefix(word string) bool {
current := t.root
runes := []rune(word)
for i := 0; i < len(runes); i++ {
ch := runes[i]
next, ok := current.next[ch]
if !ok {
return false
}
current = next
}
return true
}4.3.1. Test
func TestTrie(t *testing.T) {
trie := NewTrie()
trie.Add("panda")
fmt.Println("Contains panda? ", trie.Contains("panda"))
fmt.Println("Contains pan? ", trie.Contains("pan"))
fmt.Println("Has prefix pan? ", trie.IsPrefix("pan"))
trie.Add("pan")
fmt.Println("Contains pan? ", trie.Contains("pan"))
}5. Huffman Tree
5.1. What It Is
- Can implement Huffman coding: a foundation of modern compression algorithms
5.2. Huffman Coding Process
Take ABBBCCCCCCCCDDDDDDEE as an example.
- First calculate the frequency of each letter
| A | B | C | D | E |
|---|---|---|---|---|
| 1 | 3 | 8 | 6 | 2 |
-
Build the Huffman tree
-
Build the Huffman code
- If left is 0 and right is 1, the Huffman codes are:
A B C D E 1110 110 0 10 1111 - The encoded result of
ABBBCCCCCCCCDDDDDDEEis:11101101101100000000010101010101011111111
Discussion
Sign in with GitHub to comment. Discussions are stored as GitHub Issues.View on GitHub