golang Golang http代理
./proxy <br/> ssh -R 9000:localhost:8888 broala @ sensor <br/> corelight-client configuration update --network.management.proxy.server http:// localhost:9000
proxy.go
package main
import (
"crypto/tls"
"flag"
"io"
"log"
"net"
"net/http"
"time"
)
func handleTunneling(w http.ResponseWriter, r *http.Request) {
log.Printf("Tunneling to %s", r.Host)
dest_conn, err := net.DialTimeout("tcp", r.Host, 10*time.Second)
if err != nil {
http.Error(w, err.Error(), http.StatusServiceUnavailable)
return
}
w.WriteHeader(http.StatusOK)
hijacker, ok := w.(http.Hijacker)
if !ok {
http.Error(w, "Hijacking not supported", http.StatusInternalServerError)
return
}
client_conn, _, err := hijacker.Hijack()
if err != nil {
http.Error(w, err.Error(), http.StatusServiceUnavailable)
}
go transfer(dest_conn, client_conn)
go transfer(client_conn, dest_conn)
}
func transfer(destination io.WriteCloser, source io.ReadCloser) {
defer destination.Close()
defer source.Close()
io.Copy(destination, source)
}
func handleHTTP(w http.ResponseWriter, req *http.Request) {
resp, err := http.DefaultTransport.RoundTrip(req)
if err != nil {
http.Error(w, err.Error(), http.StatusServiceUnavailable)
return
}
defer resp.Body.Close()
copyHeader(w.Header(), resp.Header)
w.WriteHeader(resp.StatusCode)
io.Copy(w, resp.Body)
}
func copyHeader(dst, src http.Header) {
for k, vv := range src {
for _, v := range vv {
dst.Add(k, v)
}
}
}
func main() {
var pemPath string
flag.StringVar(&pemPath, "pem", "server.pem", "path to pem file")
var keyPath string
flag.StringVar(&keyPath, "key", "server.key", "path to key file")
var proto string
flag.StringVar(&proto, "proto", "http", "Proxy protocol (http or https)")
flag.Parse()
if proto != "http" && proto != "https" {
log.Fatal("Protocol must be either http or https")
}
server := &http.Server{
Addr: ":8888",
Handler: http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
if r.Method == http.MethodConnect {
handleTunneling(w, r)
} else {
handleHTTP(w, r)
}
}),
// Disable HTTP/2.
TLSNextProto: make(map[string]func(*http.Server, *tls.Conn, http.Handler)),
}
if proto == "http" {
log.Fatal(server.ListenAndServe())
} else {
log.Fatal(server.ListenAndServeTLS(pemPath, keyPath))
}
}
golang 01背包问题
bag01.go
// BagNormalLess solve bag normal problem
func BagNormalLess(weight []int, value []int, maxWeight int) int {
if maxWeight <= 0 || len(weight) != len(value) {
return 0
}
M := make([]int, maxWeight+1)
min := weight[0]
for _, w := range weight {
if w < min {
min = w
}
}
for i := 0; i < len(weight); i++ {
for w := maxWeight; w >= min; w-- {
if weight[i] <= w && value[i]+M[w-weight[i]] >= M[w] {
M[w] = value[i] + M[w-weight[i]]
}
}
}
return M[maxWeight]
}
golang 并查集
set.go
// Node used in findSet
type Node struct {
rank int
p *Node
key rune
}
// MakeSet make x a Node as a set
func MakeSet(x *Node) {
x.rank = 0
x.p = x
}
// Union different sets
func Union(x, y *Node) {
link(FindSet(x), FindSet(y))
}
func link(x, y *Node) {
if x.rank > y.rank {
y.p = x
} else {
x.p = y
if x.rank == y.rank {
y.rank++
}
}
}
// FindSet return the set belong
func FindSet(x *Node) *Node{
if x != x.p {
x.p = FindSet(x.p)
}
return x.p
}
golang 乙树(待调试)
btree.go
// BNode for BTree
type BNode struct {
n int // number of keys
keys []rune
leaf bool // leaf or not
c []*BNode // children (n+1)
}
// BTree is b tree
type BTree struct {
root *BNode
t int
}
func diskRead(x *BNode, c *BNode) {}
func diskWrite(x *BNode) {}
// CreateNode return a node
func (b *BTree) CreateNode() *BNode {
return &BNode{
n: 0,
keys: make([]rune, 2*b.t-1),
leaf: true,
c: make([]*BNode, 2*b.t),
}
}
// CreateTree returns a BTree
func CreateTree(t int) BTree {
b := BTree{}
b.t = t
b.root = b.CreateNode()
return b
}
// Search for keys
func (b *BTree) Search(x *BNode, k rune) (*BNode, rune) {
i := 0
for i = 0; i < x.n && k > x.keys[i]; i++ {
}
if i < x.n && k == x.keys[i] {
return x, x.keys[i]
} else if x.leaf {
return nil, 0
}
diskRead(x, x.c[i])
return b.Search(x.c[i], k)
}
func (b *BTree) splitChild(x *BNode, i int) {
y := x.c[i]
z := b.CreateNode()
copy(z.keys, y.keys[b.t:y.n])
if !y.leaf {
copy(z.c, y.c[b.t:y.n+1])
}
z.n = b.t - 1
y.n = b.t - 1
x.n++
copy(x.c[i+2:x.n+1], x.c[i+1:x.n])
x.c[i+1] = z
copy(x.keys[i+1:x.n], x.keys[i:x.n-1])
x.keys[i] = y.keys[y.n]
diskWrite(y)
diskWrite(z)
diskWrite(x)
}
// Insert a node
func (b *BTree) Insert(k rune) {
r := b.root
if r.n == 2*b.t-1 {
s := b.CreateNode()
b.root = s
s.c[0] = r
s.leaf = false
b.splitChild(s, 0)
b.insertNotFull(s, k)
} else {
b.insertNotFull(r, k)
}
}
func (b *BTree) insertNotFull(x *BNode, k rune) {
i := x.n - 1
if x.leaf {
for i >= 0 && k < x.keys[i] {
x.keys[i+1] = x.keys[i]
i--
}
x.keys[i+1] = k
x.n++
diskWrite(x)
} else {
for i >= 0 && k < x.keys[i] {
i--
}
i++
diskRead(x, x.c[i])
if x.c[i].n == 2*b.t-1 {
b.splitChild(x, i)
if k > x.keys[i] {
i++
}
}
b.insertNotFull(x.c[i], k)
}
}
// Delete a node
func (b *BTree) Delete(x *BNode, k rune){
i := 0
for ; i < x.n; i++ {
if x.keys[i] >= k {
break
}
}
if i < x.n && x.keys[i] == k {
if x.leaf {
copy(x.keys[i:], x.keys[i+1:])
x.n--
} else if x.c[i].n >= b.t {
x.keys[i] = x.c[i].keys[x.c[i].n-1]
b.Delete(x.c[i], x.keys[i])
} else if x.c[i+1].n >= b.t {
x.keys[i] = x.c[i+1].keys[0]
b.Delete(x.c[i+1], x.keys[i])
} else {
x.c[i].keys[x.c[i].n] = x.keys[i]
x.c[i].n++
copy(x.c[i].keys[x.c[i].n:], x.c[i+1].keys[:x.c[i+1].n])
x.c[i].n += x.c[i+1].n
copy(x.c[i].c[x.n+1:], x.c[i+1].c[:x.c[i+1].n+1])
copy(x.keys[i:], x.keys[i+1:])
copy(x.c[i+1:], x.c[i+2:])
x.n--
b.Delete(x.c[i], k)
}
} else if i < x.n && x.keys[i] > k && !x.leaf {
if x.c[i].n < b.t {
x.c[i].keys[x.c[i].n] = x.keys[i]
x.c[i].n++
if x.c[i+1].n >= b.t {
x.keys[i] = x.c[i+1].keys[0]
x.c[i].c[x.c[i].n++] = x.c[i+1].c[0]
b.Delete(x.c[i+1], x.keys[i])
b.Delete(x.c[i], k)
} else {
copy(x.c[i].keys[x.c[i].n:], x.c[i+1].keys[:x.c[i+1].n])
x.c[i].n += x.c[i+1].n
copy(x.c[i].c[x.n+1:], x.c[i+1].c[:x.c[i+1].n+1])
copy(x.keys[i:], x.keys[i+1:])
copy(x.c[i+1:], x.c[i+2:])
x.n--
}
}
b.Delete(x.c[i], k)
}
if x.n == 0 && x == b.root {
b.root = x.c[0]
}
}
func (b *BTree) inOrder(s *BNode) []rune {
A := make([]rune, 0, 4)
if s != nil {
for i, key := range s.keys {
if i < s.n {
A = append(A, b.inOrder(s.c[i])...)
A = append(A, key)
}
}
A = append(A, b.inOrder(s.c[s.n])...)
}
return A
}
golang 哈夫曼编码
huffman.go
// Node for code tree
type Node struct {
value rune
freq int
left, right *Node
}
// CodeTree is tree for code
type CodeTree struct {
root *Node
}
// Heap represents heap data strcuture
type Heap struct {
A []*Node
heapSize int
}
func parent(i int) int {
return i / 2
}
func left(i int) int {
return 2 * i
}
func right(i int) int {
return 2*i + 1
}
func (h *Heap) minHeapify(i int) {
l, r, smallest := left(i), right(i), 0
if l < h.heapSize && h.A[l].freq < h.A[i].freq {
smallest = l
} else {
smallest = i
}
if r < h.heapSize && h.A[r].freq < h.A[smallest].freq {
smallest = r
}
if smallest != i {
h.A[i], h.A[smallest] = h.A[smallest], h.A[i]
h.minHeapify(smallest)
}
}
// BuildMinHeap O(n)
func BuildMinHeap(A []*Node) Heap {
h := Heap{}
h.A, h.heapSize = A, len(A)
for i := h.heapSize / 2; i >= 0; i-- {
h.minHeapify(i)
}
return h
}
// minimum priority queue
// method:
// Minimum
// ExtractMin
// DecreaseKey
// InsertMin
// Minimum O(1)
func (h *Heap) Minimum() *Node {
return h.A[0]
}
// ExtractMin O(lgn)
func (h *Heap) ExtractMin() *Node {
if h.heapSize < 1 {
return nil
}
min := h.A[0]
h.A[0] = h.A[h.heapSize-1]
h.heapSize--
h.minHeapify(0)
return min
}
// DecreaseKey O(lgn)
func (h *Heap) DecreaseKey(i int, freq int) error {
h.A[i].freq = freq
for i > 0 && h.A[parent(i)].freq > h.A[i].freq {
h.A[i], h.A[parent(i)] = h.A[parent(i)], h.A[i]
i = parent(i)
}
return nil
}
// InsertMin O(lgn)
func (h *Heap) InsertMin(x *Node) {
h.heapSize++
h.A[h.heapSize-1] = x
h.A[h.heapSize-1].freq--
h.DecreaseKey(h.heapSize-1, x.freq+1)
}
// Huffman produce a code Tree
func Huffman(c []*Node) CodeTree{
n := len(c)
q := BuildMinHeap(c)
for i:= 0; i < n - 1; i++ {
z := Node{}
z.left = q.ExtractMin()
z.right = q.ExtractMin()
z.freq = z.left.freq + z.right.freq
q.InsertMin(&z)
}
codeTree := CodeTree{root: (q.ExtractMin())}
return codeTree
}
golang 活动安排
场地活动安排问题
activity.go
// GreedyActivitySelector O(n)
// f is sorted
func GreedyActivitySelector(s, f []int) []int{
n := len(s)
A := []int{0}
k := 0
for m := 1; m < n; m++ {
if s[m] >= f[k] {
A = append(A, m)
k = m
}
}
return A
}
golang 红黑统计树
红黑树的变种,可以快速找到顺序统计量
stattree.go
type color bool
const (
black color = true
red color = false
)
// StatNode of tree
type StatNode struct {
key int
color color
size int
left, right *StatNode
p *StatNode
}
// StatTree is black and red tree
type StatTree struct {
null *StatNode
root *StatNode
}
// CreateStatTree create a tree
func CreateStatTree(A []int) StatTree {
r := StatTree{
null: &StatNode{color: black, size: 0},
}
r.root = r.null
for _, a := range A {
r.Insert(&StatNode{key: a})
}
return r
}
// InOrder performs inorder walk
func (r *StatTree) InOrder(x *StatNode) []int {
var A []int
if x != r.null {
A = append(A, r.InOrder(x.left)...)
A = append(A, x.key)
A = append(A, r.InOrder(x.right)...)
}
return A
}
// PreOrder performs preorder walk
func (r *StatTree) PreOrder(x *StatNode) []int {
var A []int
if x != r.null {
A = append(A, x.key)
A = append(A, r.InOrder(x.left)...)
A = append(A, r.InOrder(x.right)...)
}
return A
}
// PostOrder performs postorder walk
func (r *StatTree) PostOrder(x *StatNode) []int {
var A []int
if x != r.null {
A = append(A, r.InOrder(x.left)...)
A = append(A, r.InOrder(x.right)...)
A = append(A, x.key)
}
return A
}
// Search for a key
func (r *StatTree) Search(x *StatNode, k int) *StatNode {
if x == r.null || k == x.key {
return x
} else if k < x.key {
return r.Search(x.left, k)
} else {
return r.Search(x.right, k)
}
}
// QuickSearch for a key
func (r *StatTree) QuickSearch(x *StatNode, k int) *StatNode {
for x != r.null && k != x.key {
if k < x.key {
x = x.left
} else {
x = x.right
}
}
return x
}
// Min minimum StatNode
func (r *StatTree) Min(x *StatNode) *StatNode {
for x.left != r.null {
x = x.left
}
return x
}
// Max maximum StatNode
func (r *StatTree) Max(x *StatNode) *StatNode {
for x.right != r.null {
x = x.right
}
return x
}
// Successor previous StatNode
func (r *StatTree) Successor(x *StatNode) *StatNode {
if x.right != r.null {
return r.Min(x.right)
}
y := x.p
for y != r.null && x == y.right {
x, y = y, y.p
}
return y
}
// Preccessor post StatNode
func (r *StatTree) Preccessor(x *StatNode) *StatNode {
if x.left != r.null {
return r.Max(x.left)
}
y := x.p
for y != r.null && x == y.left {
x, y = y, y.p
}
return y
}
func (r *StatTree) leftRotate(x *StatNode) {
y := x.right
x.right = y.left
if y.left != r.null {
y.left.p = x
}
y.p = x.p
if x.p == r.null {
r.root = y
} else if x == x.p.left {
x.p.left = y
} else {
x.p.right = y
}
y.left = x
x.p = y
y.size = x.size
x.size = x.left.size + x.right.size + 1
}
func (r *StatTree) rightRotate(x *StatNode) {
y := x.left
x.left = y.right
if y.right != r.null {
y.left.p = x
}
y.p = x.p
if x.p == r.null {
r.root = y
} else if x == x.p.left {
x.p.left = y
} else {
x.p.right = y
}
y.right = x
x.p = y
y.size = x.size
x.size = x.left.size + x.right.size + 1
}
func (r *StatTree) insertFixUp(z *StatNode) {
for z.p.color == red {
if z.p == z.p.p.left {
y := z.p.p.right
if y.color == red {
z.p.color, y.color, z.p.p.color = black, black, red
z = z.p.p
} else {
if z == z.p.right {
z = z.p
r.leftRotate(z)
}
z.p.color, z.p.p.color = black, red
r.rightRotate(z.p.p)
}
} else {
y := z.p.p.left
if y.color == red {
z.p.color, y.color, z.p.p.color = black, black, red
z = z.p.p
} else {
if z == z.p.left {
z = z.p
r.rightRotate(z)
}
z.p.color, z.p.p.color = black, red
r.leftRotate(z.p.p)
}
}
}
r.root.color = black
}
// Insert a StatNode
func (r *StatTree) Insert(z *StatNode) {
y, x := r.null, r.root
for x != r.null {
y = x
if z.key < x.key {
x = x.left
} else {
x = x.right
}
}
z.p = y
if y == r.null {
r.root = z
} else if z.key < y.key {
y.left = z
} else {
y.right = z
}
z.left = r.null
z.right = r.null
z.color = red
z.size = 1
x = z.p
for x != r.null {
x.size++
x = x.p
}
r.insertFixUp(z)
}
func (r *StatTree) transplant(u, v *StatNode) {
if u.p == r.null {
r.root = v
} else if u == u.p.left {
u.p.left = v
} else {
u.p.right = v
}
v.p = u.p
}
func (r *StatTree) deleteFixUp(x *StatNode) {
for x != r.root && x.color == black {
if x == x.p.left {
w := x.p.right
if w.color == red {
w.color = black
x.p.color = red
r.leftRotate(x.p)
w = x.p.right
}
if w.left.color == black && w.right.color == black {
w.color = red
x = x.p
} else if w.right.color == black {
w.left.color = black
w.color = red
r.rightRotate(w)
w = x.p.right
}
w.color = x.p.color
x.p.color = black
w.right.color = black
r.leftRotate(x.p)
x = r.root
} else {
w := x.p.left
if w.color == red {
w.color = black
x.p.color = red
r.rightRotate(x.p)
w = x.p.left
}
if w.right.color == black && w.left.color == black {
w.color = red
x = x.p
} else if w.left.color == black {
w.right.color = black
w.color = red
r.leftRotate(w)
w = x.p.left
}
w.color = x.p.color
x.p.color = black
w.left.color = black
r.rightRotate(x.p)
x = r.root
}
}
x.color = black
}
// Delete a StatNode
func (r *StatTree) Delete(z *StatNode) {
y, yColor := z, z.color
x := z
if z.left == r.null {
x = z.right
r.transplant(z, z.right)
} else if z.right == r.null {
x = z.left
r.transplant(z, z.left)
} else {
y = r.Min(z.right)
yColor = y.color
x = y.right
if y.p == z {
x.p = y
} else {
r.transplant(y, y.right)
y.right = z.right
y.right.p = y
}
r.transplant(z, y)
y.left = z.left
y.left.p = y
y.color = z.color
y.size = z.size
}
t := x.p
for t != r.null {
t.size--
t = t.p
}
if yColor == black {
r.deleteFixUp(x)
}
}
// Select the StatNode which is ith node
func (r *StatTree) Select(x *StatNode, i int) *StatNode {
s := x.left.size + 1
if i == s {
return x
} else if i < s {
return r.Select(x.left, i)
} else {
return r.Select(x.right, i-s)
}
}
// Rank the x node
func (r *StatTree) Rank(x *StatNode) int {
s := x.left.size + 1
y := x
for y != r.root {
if y == y.p.right {
s += y.p.left.size + 1
}
y = y.p
}
return s
}
func (r *StatTree) isSizeRight(s *StatNode) bool {
if s == r.null {
return true
}
if s.left.size + s.right.size + 1 != s.size {
return false
}
return r.isSizeRight(s.left) && r.isSizeRight(s.right)
}
golang 红黑树
rbtree.go
type color bool
const (
black color = true
red color = false
)
// RBNode of tree
type RBNode struct {
key int
color color
left, right *RBNode
p *RBNode
}
// RBTree is black and red tree
type RBTree struct {
null *RBNode
root *RBNode
}
// CreateRBTree create a tree
func CreateRBTree(A []int) RBTree {
r := RBTree{
null: &RBNode{color: black},
}
r.root = r.null
for _, a := range A {
r.Insert(&RBNode{key: a})
}
return r
}
// InOrder performs inorder walk
func (r *RBTree) InOrder(x *RBNode) []int {
var A []int
if x != r.null {
A = append(A, r.InOrder(x.left)...)
A = append(A, x.key)
A = append(A, r.InOrder(x.right)...)
}
return A
}
// PreOrder performs preorder walk
func (r *RBTree) PreOrder(x *RBNode) []int {
var A []int
if x != r.null {
A = append(A, x.key)
A = append(A, r.InOrder(x.left)...)
A = append(A, r.InOrder(x.right)...)
}
return A
}
// PostOrder performs postorder walk
func (r *RBTree) PostOrder(x *RBNode) []int {
var A []int
if x != r.null {
A = append(A, r.InOrder(x.left)...)
A = append(A, r.InOrder(x.right)...)
A = append(A, x.key)
}
return A
}
// Search for a key
func (r *RBTree) Search(x *RBNode, k int) *RBNode {
if x == r.null || k == x.key {
return x
} else if k < x.key {
return r.Search(x.left, k)
} else {
return r.Search(x.right, k)
}
}
// QuickSearch for a key
func (r *RBTree) QuickSearch(x *RBNode, k int) *RBNode {
for x != r.null && k != x.key {
if k < x.key {
x = x.left
} else {
x = x.right
}
}
return x
}
// Min minimum RBNode
func (r *RBTree) Min(x *RBNode) *RBNode {
for x.left != r.null {
x = x.left
}
return x
}
// Max maximum RBNode
func (r *RBTree) Max(x *RBNode) *RBNode {
for x.right != r.null {
x = x.right
}
return x
}
// Successor previous RBNode
func (r *RBTree) Successor(x *RBNode) *RBNode {
if x.right != r.null {
return r.Min(x.right)
}
y := x.p
for y != r.null && x == y.right {
x, y = y, y.p
}
return y
}
// Preccessor post RBNode
func (r *RBTree) Preccessor(x *RBNode) *RBNode {
if x.left != r.null {
return r.Max(x.left)
}
y := x.p
for y != r.null && x == y.left {
x, y = y, y.p
}
return y
}
func (r *RBTree) leftRotate(x *RBNode) {
y := x.right
x.right = y.left
if y.left != r.null {
y.left.p = x
}
y.p = x.p
if x.p == r.null {
r.root = y
} else if x == x.p.left {
x.p.left = y
} else {
x.p.right = y
}
y.left = x
x.p = y
}
func (r *RBTree) rightRotate(x *RBNode) {
y := x.left
x.left = y.right
if y.right != r.null {
y.left.p = x
}
y.p = x.p
if x.p == r.null {
r.root = y
} else if x == x.p.left {
x.p.left = y
} else {
x.p.right = y
}
y.right = x
x.p = y
}
func (r *RBTree) insertFixUp(z *RBNode) {
for z.p.color == red {
if z.p == z.p.p.left {
y := z.p.p.right
if y.color == red {
z.p.color, y.color, z.p.p.color = black, black, red
z = z.p.p
} else {
if z == z.p.right {
z = z.p
r.leftRotate(z)
}
z.p.color, z.p.p.color = black, red
r.rightRotate(z.p.p)
}
} else {
y := z.p.p.left
if y.color == red {
z.p.color, y.color, z.p.p.color = black, black, red
z = z.p.p
} else {
if z == z.p.left {
z = z.p
r.rightRotate(z)
}
z.p.color, z.p.p.color = black, red
r.leftRotate(z.p.p)
}
}
}
r.root.color = black
}
// Insert a RBNode
func (r *RBTree) Insert(z *RBNode) {
y, x := r.null, r.root
for x != r.null {
y = x
if z.key < x.key {
x = x.left
} else {
x = x.right
}
}
z.p = y
if y == r.null {
r.root = z
} else if z.key < y.key {
y.left = z
} else {
y.right = z
}
z.left = r.null
z.right = r.null
z.color = red
r.insertFixUp(z)
}
func (r *RBTree) transplant(u, v *RBNode) {
if u.p == r.null {
r.root = v
} else if u == u.p.left {
u.p.left = v
} else {
u.p.right = v
}
v.p = u.p
}
func (r *RBTree) deleteFixUp(x *RBNode) {
for x != r.root && x.color == black {
if x == x.p.left {
w := x.p.right
if w.color == red {
w.color = black
x.p.color = red
r.leftRotate(x.p)
w = x.p.right
}
if w.left.color == black && w.right.color == black {
w.color = red
x = x.p
} else if w.right.color == black {
w.left.color = black
w.color = red
r.rightRotate(w)
w = x.p.right
}
w.color = x.p.color
x.p.color = black
w.right.color = black
r.leftRotate(x.p)
x = r.root
} else {
w := x.p.left
if w.color == red {
w.color = black
x.p.color = red
r.rightRotate(x.p)
w = x.p.left
}
if w.right.color == black && w.left.color == black {
w.color = red
x = x.p
} else if w.left.color == black {
w.right.color = black
w.color = red
r.leftRotate(w)
w = x.p.left
}
w.color = x.p.color
x.p.color = black
w.left.color = black
r.rightRotate(x.p)
x = r.root
}
}
x.color = black
}
// Delete a RBNode
func (r *RBTree) Delete(z *RBNode) {
y, yColor := z, z.color
x := z
if z.left == r.null {
x = z.right
r.transplant(z, z.right)
} else if z.right == r.null {
x = z.left
r.transplant(z, z.left)
} else {
y = r.Min(z.right)
yColor = y.color
x = y.right
if y.p == z {
x.p = y
} else {
r.transplant(y, y.right)
y.right = z.right
y.right.p = y
}
r.transplant(z, y)
y.left = z.left
y.left.p = y
y.color = z.color
}
if yColor == black {
r.deleteFixUp(x)
}
}
golang 二叉搜索平衡树
avltree.go
import "math"
type height int
// AVLNode of tree
type AVLNode struct {
key int
h height
left, right *AVLNode
p *AVLNode
}
// AVLTree is AVL tree
type AVLTree struct {
null *AVLNode
root *AVLNode
}
// CreateAVLTree create a tree
func CreateAVLTree(A []int) AVLTree {
r := AVLTree{
null: &AVLNode{},
}
r.root = r.null
for _, a := range A {
r.Insert(&AVLNode{key: a})
}
return r
}
// InOrder performs inorder walk
func (r *AVLTree) InOrder(x *AVLNode) []int {
var A []int
if x != r.null {
A = append(A, r.InOrder(x.left)...)
A = append(A, x.key)
A = append(A, r.InOrder(x.right)...)
}
return A
}
// PreOrder performs preorder walk
func (r *AVLTree) PreOrder(x *AVLNode) []int {
var A []int
if x != r.null {
A = append(A, x.key)
A = append(A, r.InOrder(x.left)...)
A = append(A, r.InOrder(x.right)...)
}
return A
}
// PostOrder performs postorder walk
func (r *AVLTree) PostOrder(x *AVLNode) []int {
var A []int
if x != r.null {
A = append(A, r.InOrder(x.left)...)
A = append(A, r.InOrder(x.right)...)
A = append(A, x.key)
}
return A
}
// Search for a key
func (r *AVLTree) Search(x *AVLNode, k int) *AVLNode {
if x == r.null || k == x.key {
return x
} else if k < x.key {
return r.Search(x.left, k)
} else {
return r.Search(x.right, k)
}
}
// QuickSearch for a key
func (r *AVLTree) QuickSearch(x *AVLNode, k int) *AVLNode {
for x != r.null && k != x.key {
if k < x.key {
x = x.left
} else {
x = x.right
}
}
return x
}
// Min minimum AVLNode
func (r *AVLTree) Min(x *AVLNode) *AVLNode {
for x.left != r.null {
x = x.left
}
return x
}
// Max maximum AVLNode
func (r *AVLTree) Max(x *AVLNode) *AVLNode {
for x.right != r.null {
x = x.right
}
return x
}
// Successor previous AVLNode
func (r *AVLTree) Successor(x *AVLNode) *AVLNode {
if x.right != r.null {
return r.Min(x.right)
}
y := x.p
for y != r.null && x == y.right {
x, y = y, y.p
}
return y
}
// Preccessor post AVLNode
func (r *AVLTree) Preccessor(x *AVLNode) *AVLNode {
if x.left != r.null {
return r.Max(x.left)
}
y := x.p
for y != r.null && x == y.left {
x, y = y, y.p
}
return y
}
func (r *AVLTree) leftRotate(x *AVLNode) {
y := x.right
x.right = y.left
if y.left != r.null {
y.left.p = x
}
y.p = x.p
if x.p == r.null {
r.root = y
} else if x == x.p.left {
x.p.left = y
} else {
x.p.right = y
}
y.left = x
x.p = y
x.h = max(x.left.h, x.right.h) + 1
y.h = max(y.left.h, y.right.h) + 1
}
func (r *AVLTree) rightRotate(x *AVLNode) {
y := x.left
x.left = y.right
if y.right != r.null {
y.left.p = x
}
y.p = x.p
if x.p == r.null {
r.root = y
} else if x == x.p.left {
x.p.left = y
} else {
x.p.right = y
}
y.right = x
x.p = y
x.h = max(x.left.h, x.right.h) + 1
y.h = max(y.left.h, y.right.h) + 1
}
func max(T ...height) height {
max := height(0)
for _, t := range T {
if t > max {
max = t
}
}
return max
}
func (r *AVLTree) balance(z *AVLNode) {
for z != r.null {
if z.left.h > z.right.h+1 {
if z.left.right.h > z.left.left.h {
r.leftRotate(z.left)
}
r.rightRotate(z)
z = z.p
} else if z.right.h > z.left.h+1 {
if z.right.left.h > z.right.right.h {
r.rightRotate(z.right)
}
r.leftRotate(z)
z = z.p
} else {
z.h = max(z.left.h, z.right.h) + 1
}
z = z.p
}
}
// Insert a AVLNode
func (r *AVLTree) Insert(z *AVLNode) {
y, x := r.null, r.root
for x != r.null {
y = x
if z.key < x.key {
x = x.left
} else {
x = x.right
}
}
z.p = y
if y == r.null {
r.root = z
} else if z.key < y.key {
y.left = z
} else {
y.right = z
}
z.left = r.null
z.right = r.null
z.h = 1
r.balance(z.p)
}
func (r *AVLTree) transplant(u, v *AVLNode) {
if u.p == r.null {
r.root = v
} else if u == u.p.left {
u.p.left = v
} else {
u.p.right = v
}
v.p = u.p
}
// Delete a AVLNode
func (r *AVLTree) Delete(z *AVLNode) {
y, x := z, z
if z.left == r.null {
x = z.right
r.transplant(z, z.right)
} else if z.right == r.null {
x = z.left
r.transplant(z, z.left)
} else {
y = r.Min(z.right)
x := y.right
if y.p == z {
x.p = y
} else {
r.transplant(y, y.right)
y.right = z.right
y.right.p = y
}
r.transplant(z, y)
y.left = z.left
y.left.p = y
}
r.balance(x.p)
}
func (r *AVLTree) isBalance(n *AVLNode) bool {
if n == r.null {
return true
}
if math.Abs(float64(n.left.h-n.right.h)) >= 2 {
return false
}
return r.isBalance(n.left) && r.isBalance(n.right)
}
golang 二叉搜索树以及最大最小优先队列
searchTree.go
import "fmt"
// Node for SearchTree
type Node struct {
key int
left, right *Node
p *Node
}
// SearchTree represents a tree
type SearchTree struct {
root *Node
}
// CreateSearchTree init a tree
func CreateSearchTree(A []int) SearchTree {
s := SearchTree{}
for _, a := range A {
s.Insert(&Node{key: a})
}
return s
}
// InOrder O(n)
func (s *SearchTree) InOrder(x *Node) []int {
var A []int
if x != nil {
A = append(A, s.InOrder(x.left)...)
A = append(A, x.key)
A = append(A, s.InOrder(x.right)...)
}
return A
}
// PreOrder O(n)
func (s *SearchTree) PreOrder(x *Node) []int {
var A []int
if x != nil {
A = append(A, x.key)
A = append(A, s.InOrder(x.left)...)
A = append(A, s.InOrder(x.right)...)
}
return A
}
// PostOrder O(n)
func (s *SearchTree) PostOrder(x *Node) []int {
var A []int
if x != nil {
A = append(A, s.InOrder(x.left)...)
A = append(A, s.InOrder(x.right)...)
A = append(A, x.key)
}
return A
}
// Search rescursive search
func (s *SearchTree) Search(x *Node, k int) *Node {
if x == nil || k == x.key {
return x
} else if k < x.key {
return s.Search(x.left, k)
}
return s.Search(x.right, k)
}
// QuickSearch not rescursive search
func (s *SearchTree) QuickSearch(x *Node, k int) *Node {
for x != nil && k != x.key {
if k < x.key {
x = x.left
} else {
x = x.right
}
}
return x
}
// Min rescursive
func (s *SearchTree) Min(x *Node) *Node {
if x.left == nil {
return x
}
return s.Min(x.left)
}
// QuickMin minimum Node
func (s *SearchTree) QuickMin(x *Node) *Node {
for x.left != nil {
x = x.left
}
return x
}
// Max rescursive
func (s *SearchTree) Max(x *Node) *Node {
if x.right == nil {
return x
}
return s.Max(x.right)
}
// QuickMax maximum Node
func (s *SearchTree) QuickMax(x *Node) *Node {
for x.right != nil {
x = x.right
}
return x
}
// Successor previous Node O(h)
func (s *SearchTree) Successor(x *Node) *Node {
if x.right != nil {
return s.Min(x.right)
}
y := x.p
for y != nil && x == y.right {
x, y = y, y.p
}
return y
}
// Preccessor latter Node O(h)
func (s *SearchTree) Preccessor(x *Node) *Node {
if x.left != nil {
return s.Max(x.left)
}
y := x.p
for y != nil && x == y.left {
x, y = y, y.p
}
return y
}
// Insert O(lgn)
func (s *SearchTree) Insert(z *Node) {
x := s.root
y := x
for x != nil {
y = x
if z.key < x.key {
x = x.left
} else {
x = x.right
}
}
z.p = y
if y == nil {
s.root = z
} else if z.key < y.key {
y.left = z
} else {
y.right = z
}
}
func (s *SearchTree) transplant(u, v *Node) {
if u.p == nil {
s.root = v
} else if u == u.p.left {
u.p.left = v
} else {
u.p.right = v
}
if v != nil {
v.p = u.p
}
}
// Delete O(h)
func (s *SearchTree) Delete(z *Node) {
if z.left == nil {
s.transplant(z, z.right)
} else if z.right == nil {
s.transplant(z, z.left)
} else {
y := s.Min(z.right)
if y.p != z {
s.transplant(y, y.right)
y.right = z.right
y.right.p = y
}
s.transplant(z, y)
y.left = z.left
y.left.p = y
}
}
// maximum priority queue
// method:
// InsertMax
// Maximum
// ExtractMax
// InsertMax O(h)
func (s *SearchTree) InsertMax(x int) {
s.Insert(&Node{key: x})
}
// Maximum O(h)
func (s *SearchTree) Maximum() int {
max := s.Max(s.root)
if max != nil {
return max.key
}
return -1
}
// ExtractMax O(h)
func (s *SearchTree) ExtractMax() (int, error) {
if s.root == nil {
return 0, fmt.Errorf("Heap overflow")
}
max := s.Max(s.root)
s.Delete(max)
return max.key, nil
}
// minimum priority queue
// method:
// Minimum
// ExtractMin
// InsertMin
// InsertMin O(h)
func (s *SearchTree) InsertMin(x int) {
s.Insert(&Node{key: x})
}
// Minimum O(h)
func (s *SearchTree) Minimum() int {
min := s.Min(s.root)
if min != nil {
return min.key
}
return -1
}
// ExtractMin O(h)
func (s *SearchTree) ExtractMin() (int, error) {
if s.root == nil {
return 0, fmt.Errorf("Heap overflow")
}
min := s.Min(s.root)
s.Delete(min)
return min.key, nil
}