Lære Comparing Trees and Hash Tables | Advanced Data Structures

Stryg for at vise menuen

Trees in Go

A tree is a hierarchical data structure made up of nodes, where each node can have zero or more child nodes. In Go, trees are often implemented using structs and pointers to represent relationships between nodes.

Key Characteristics

Each node contains a value and references to child nodes;
There is a single root node at the top of the tree;
Nodes with no children are called leaves;
Trees can be specialized, such as binary trees (each node has up to two children), AVL trees, or B-trees.

Strengths

Efficiently represent hierarchical relationships, such as file systems or organizational charts;
Enable fast searching, insertion, and deletion in balanced trees (like AVL or red-black trees);
Support ordered traversal, which allows you to process data in sorted order;
Facilitate range queries and prefix-based searches (as in trie or B-tree structures).

Weaknesses

Require careful implementation to maintain balance and performance, especially for self-balancing trees;
Can use more memory than linear data structures due to pointers and node overhead;
Traversal and manipulation can be complex compared to arrays or slices;
Not ideal for constant-time lookups when keys are not ordered or when data does not benefit from hierarchical relationships.

In Go, you typically define a tree node as a struct containing a value field and pointers to child nodes. Trees are a powerful choice for problems that require hierarchical organization or ordered data processing.

main.go


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
            
package main

import (
	"fmt"
)

type Node struct {
	value int
	left  *Node
	right *Node
}

// Insert adds a new node to the tree
func (n *Node) Insert(val int) {
	if val < n.value {
		if n.left == nil {
			n.left = &Node{value: val}
		} else {
			n.left.Insert(val)
		}
	} else {
		if n.right == nil {
			n.right = &Node{value: val}
		} else {
			n.right.Insert(val)
		}
	}
}

// InOrder prints the tree values in order
func (n *Node) InOrder() {
	if n == nil {
		return
	}
	n.left.InOrder()
	fmt.Printf("%d ", n.value)
	n.right.InOrder()
}

func main() {
	root := &Node{value: 10}
	root.Insert(5)
	root.Insert(15)
	root.Insert(7)
	root.Insert(3)

	fmt.Print("In-order traversal: ")
	root.InOrder()
	fmt.Println()
}

Hash Tables in Go

A hash table is a data structure that stores key-value pairs for fast lookup, insertion, and deletion. In Go, the built-in map type implements a hash table, making it easy to associate values with unique keys.

Key Characteristics

Keys must be of a type that is comparable (such as strings, integers, or structs without slice, map, or function fields);
Values can be of any type;
Operations like lookup, insert, and delete typically run in constant time (O(1)), assuming a good hash function and low collision rate;
Hash tables use a hash function to convert keys into array indices.

Strengths

Fast access: Retrieve, insert, or delete values using keys in near-constant time;
Flexible keys: Use various types as keys, including custom structs (if all fields are comparable);
Built-in support: Go’s map makes hash tables easy to use without extra libraries.

Weaknesses

Unordered storage: Keys in a hash table are not stored in any specific order;
Memory overhead: Hash tables use extra space for internal structures and to reduce collisions;
Potential collisions: Keys that hash to the same index require extra handling, which can slow operations if not managed well;
No guaranteed worst-case time: In rare cases, performance can degrade if many collisions occur.

Hash tables are a practical choice in Go for most use cases where you need fast, flexible key-based access and don’t require ordered data.

main.go


              123456789101112131415161718192021222324252627282930313233
            
package main

import (
	"fmt"
)

func main() {
	// Create a map to represent a hash table storing employee IDs and names
	employees := make(map[int]string)

	// Add key-value pairs to the hash table
	employees[1001] = "Alice"
	employees[1002] = "Bob"
	employees[1003] = "Charlie"

	// Retrieve a value by key
	name := employees[1002]
	fmt.Println("Employee 1002:", name)

	// Check if a key exists
	id := 1004
	if val, exists := employees[id]; exists {
		fmt.Println("Employee", id, ":", val)
	} else {
		fmt.Println("Employee", id, "not found")
	}

	// Iterate over all key-value pairs
	fmt.Println("All employees:")
	for id, name := range employees {
		fmt.Println("ID:", id, "Name:", name)
	}
}

When to Use Trees vs Hash Tables

Choosing between trees and hash tables depends on your data and the operations you need to perform. Use these guidelines to select the right structure:

Choose a tree when you need to keep data sorted or require range queries;
Use a tree if you need to traverse elements in order (such as finding the smallest or largest item);
Prefer trees if you may need to dynamically balance data or support complex queries like "all values between X and Y";
Select a hash table when you need fast lookups, insertions, and deletions by key, and order does not matter;
Use a hash table if keys are unique and you rarely need to process items in any specific sequence;
Hash tables are ideal when you need to check for the existence of a value quickly or store a large set of unique items.

Summary:

Use a tree for ordered data, range queries, and in-order traversal;
Use a hash table for fast, unordered access by key and quick existence checks.

Example:

Storing user records sorted by signup date: use a tree.
Caching user sessions by unique ID: use a hash table.

Var alt klart?

Tak for dine kommentarer!

Sektion 3. Kapitel 3

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Sektion 3. Kapitel 3