bc's club

This is Bc's club

Golang实现经典数据结构

avl树#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package main

import "fmt"

type Node struct {
	key, height int
	left, right *Node
}

func height(node *Node) int {
	if node == nil {
		return -1
	}
	return node.height
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func rotateLeft(node *Node) *Node {
	rightChild := node.right
	node.right = rightChild.left
	rightChild.left = node
	node.height = max(height(node.left), height(node.right)) + 1
	rightChild.height = max(height(rightChild.left), height(rightChild.right)) + 1
	return rightChild
}

func rotateRight(node *Node) *Node {
	leftChild := node.left
	node.left = leftChild.right
	leftChild.right = node
	node.height = max(height(node.left), height(node.right)) + 1
	leftChild.height = max(height(leftChild.left), height(leftChild.right)) + 1
	return leftChild
}

func rotateLeftRight(node *Node) *Node {
	node.left = rotateLeft(node.left)
	return rotateRight(node)
}

func rotateRightLeft(node *Node) *Node {
	node.right = rotateRight(node.right)
	return rotateLeft(node)
}

func balance(node *Node) *Node {
	if height(node.left)-height(node.right) > 1 {
		if height(node.left.left) >= height(node.left.right) {
			node = rotateRight(node)
		} else {
			node = rotateLeftRight(node)
		}
	} else if height(node.right)-height(node.left) > 1 {
		if height(node.right.right) >= height(node.right.left) {
			node = rotateLeft(node)
		} else {
			node = rotateRightLeft(node)
		}
	}
	node.height = max(height(node.left), height(node.right)) + 1
	return node
}

func put(node *Node, key int) *Node {
	if node == nil {
		return &Node{key: key, height: 0}
	}
	if key < node.key {
		node.left = put(node.left, key)
	} else if key > node.key {
		node.right = put(node.right, key)
	} else {
		return node // key already exists
	}
	return balance(node)
}

func findMin(node *Node) *Node {
	if node == nil {
		return nil
	}
	for node.left != nil {
		node = node.left
	}
	return node
}

func deleteMin(node *Node) *Node {
	if node.left == nil {
		return node.right
	}
	node.left = deleteMin(node.left)
	return balance(node)
}

func delete(node *Node, key int) *Node {
	if node == nil {
		return nil
	}
	if key < node.key {
		node.left = delete(node.left, key)
	} else if key > node.key {
		node.right = delete(node.right, key)
	} else {
		if node.left == nil {
			return node.right
		} else if node.right == nil {
			return node.left
		} else {
			successor := findMin(node.right)
			node.key = successor.key
			node.right = deleteMin(node.right)
		}
	}
	return balance(node)
}

func find(node *Node, key int) *Node {
	if node == nil {
		return nil
	}
	if key < node.key {
		return find(node.left, key)
	} else if key > node.key {
		return find(node.right, key)
	} else {
		return node
  }
}

func main() {
	var root *Node
	root = put(root, 10)
	root = put(root, 20)
	root = put(root, 30)
	root = put(root, 40)
	root = put(root, 50)
	root = delete(root, 30)
  fmt.Println(find(root, 10))
	fmt.Println(find(root, 20))
	fmt.Println(find(root, 30))	
	fmt.Println(find(root, 40))
	fmt.Println(find(root, 50))
}

LRU#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import (
    "container/list"
    "sync"
)

type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    list     *list.List
    mutex    sync.Mutex
}

type CacheItem struct {
    key   int
    value int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

func (this *LRUCache) Get(key int) int {
    this.mutex.Lock()
    defer this.mutex.Unlock()

    if ele, ok := this.cache[key]; ok {
        this.list.MoveToFront(ele)
        return ele.Value.(*CacheItem).value
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    this.mutex.Lock()
    defer this.mutex.Unlock()

    if ele, ok := this.cache[key]; ok {
        this.list.MoveToFront(ele)
        ele.Value.(*CacheItem).value = value
    } else {
        ele := this.list.PushFront(&CacheItem{key, value})
        this.cache[key] = ele
        if len(this.cache) > this.capacity {
            ele := this.list.Back()
            this.list.Remove(ele)
            delete(this.cache, ele.Value.(*CacheItem).key)
        }
    }
}

红黑树#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package main

import "fmt"

const (
	red   = true
	black = false
)

type RBTree struct {
	root *Node
}

type Node struct {
	key, value  int
	color       bool
	left, right *Node
}

func (t *RBTree) put(key, value int) {
	t.root = t.root.put(key, value)
	t.root.color = black
}

func (n *Node) put(key, value int) *Node {
	if n == nil {
		return &Node{key: key, value: value, color: red}
	}
	if key < n.key {
		n.left = n.left.put(key, value)
	} else if key > n.key {
		n.right = n.right.put(key, value)
	} else {
		n.value = value
	}
	if n.right.isRed() && !n.left.isRed() {
		n = n.rotateLeft()
	}
	if n.left.isRed() && n.left.left.isRed() {
		n = n.rotateRight()
	}
	if n.left.isRed() && n.right.isRed() {
		n.flipColors()
	}
	return n
}

func (t *RBTree) get(key int) (int, bool) {
	n := t.root
	for n != nil {
		if key < n.key {
			n = n.left
		} else if key > n.key {
			n = n.right
		} else {
			return n.value, true
		}
	}
	return 0, false
}

func (n *Node) isRed() bool {
	if n == nil {
		return false
	}
	return n.color == red
}

func (n *Node) rotateLeft() *Node {
	x := n.right
	n.right = x.left
	x.left = n
	x.color = n.color
	n.color = red
	return x
}

func (n *Node) rotateRight() *Node {
	x := n.left
	n.left = x.right
	x.right = n
	x.color = n.color
	n.color = red
	return x
}

func (n *Node) flipColors() {
	n.color = red
	n.left.color = black
	n.right.color = black
}

func main() {
	tree := &RBTree{}
	tree.put(3, 3)
	tree.put(2, 2)
	tree.put(1, 1)
	fmt.Println(tree.get(1))
	fmt.Println(tree.get(2))
	fmt.Println(tree.get(3))
}