Đi cấu trúc dữ liệu: Cây tìm kiếm nhị phân

Phân tích và triển khai cấu trúc dữ liệu Cây tìm kiếm nhị phân trong Go

Acâylà một đại diện của một cấu trúc phân cấp. Thật dễ dàng để hình dung một cái cây bằng cách nghĩ về một cây phả hệ của gia đình.

Giống như một bảng băm hoặc một đồ thị, là một cấu trúc dữ liệu không tuần tự.

ACây nhị phânlà một cây mà mỗi nút có tối đa 2 nút con.

Acây tìm kiếm nhị phâncó thuộc tính của nút bên trái có giá trị nhỏ hơn giá trị ở nút bên phải.

Đây là những gì chúng tôi sẽ xây dựng trong bài viết này. Đó là một cấu trúc dữ liệu rất hữu ích để lưu trữ và lập chỉ mục dữ liệu cũng như truy xuất dữ liệu hiệu quả.

Thuật ngữ

Nguồn gốc: cấp 0 của cây

Đứa trẻ: mỗi nút của cây không phải là gốc

Nút nội bộ: mỗi nút có ít nhất một nút con

Lá cây: mỗi nút không có nút con

Cây con: tập hợp các nút với một nút nhất định làm gốc

Thông tin sơ bộ

Cấu trúc dữ liệu cây tìm kiếm nhị phân sẽ hiển thị các phương pháp đó:

  • Insert(t)chèn Mục t vào cây
  • Search(t)trả về true nếu Mục t tồn tại trong cây
  • InOrderTraverse()truy cập vào tất cả các nút có di chuyển theo thứ tự
  • PreOrderTraverse()truy cập tất cả các nút có đặt hàng trước đi ngang
  • PostOrderTraverse()truy cập tất cả các nút có duyệt đơn hàng sau
  • Min()trả về Mục có giá trị tối thiểu được lưu trữ trong cây
  • Max()trả về Mục có giá trị tối đa được lưu trữ trong cây
  • Remove(t)loại bỏ Mục t khỏi cây
  • String()in kết xuất CLI có thể đọc được của cây

Tôi sẽ tạo mộtItemBinarySearchTreeloại chung, an toàn đồng thời, có thể tạo cây chứa bất kỳ loại nào bằng cách sử dụnggenny, để tạo một triển khai cây cụ thể kiểu, đóng gói cấu trúc dữ liệu giá trị cụ thể thực tế có chứa dữ liệu.

Tôi định nghĩa mỗi ghi chú là

// Node a single node that composes the tree
type Node struct {
    key   int
    value Item
    left  *Node //left
    right *Node //right
}

Giá trị khóa cho phép sử dụng bất kỳ loại Loại vật phẩm nào và sử dụng một giá trị riêng biệt để tính đúng vị trí. Tôi đã triển khai nó dưới dạng số nguyên, nhưng nó có thể lấy bất kỳ kiểu nào có thể so sánh được.

Việc chèn một mục vào cây yêu cầu sử dụng đệ quy, vì chúng ta cần tìm đúng vị trí cho nó. Quy tắc là, nếu khóa của nút <so với cây nút hiện tại, chúng tôi đặt nó là nút con bên trái, nếu không có nút con bên trái. Nếu không, chúng tôi tính toán lại vị trí bằng cách sử dụng nút con bên trái làm nút cơ sở. Tương tự đối với đứa trẻ bên phải.

Đi ngang là quá trình điều hướng cây và chúng tôi thực hiện 3 cách để thực hiện, vì có 3 cách tiếp cận khác nhau. Lấy cây tìm kiếm nhị phân này:

đây là cách chúng tôi có thể vượt qua nó:

  • theo thứ tự: chúng tôi truy cập tất cả các nút bằng cách đi theo liên kết nhỏ nhất cho đến khi chúng tôi tìm thấy lá ngoài cùng bên trái, sau đó xử lý lá và di chuyển đến các nút khác bằng cách đi vào giá trị khóa nhỏ nhất tiếp theo được liên kết với lá hiện tại. Trong hình trên:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11
  • đặt hàng trước: trước khi đến thăm con, cách tiếp cận này sẽ truy cập vào nút trước. Trong hình trên:8 -> 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 -> 10 -> 9 -> 11
  • đặt hàng sau: chúng ta tìm lá nhỏ nhất (lá ngoài cùng bên trái), sau đó xử lý anh chị em và sau đó là nút cha, sau đó chuyển đến cây con tiếp theo và điều hướng lên cha mẹ. Trong hình trên:1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4 -> 9 -> 11 -> 10 -> 8

CácString, được sử dụng trong các bài kiểm tra để có phản hồi trực quan về các phương pháp, sẽ in ra cây ở trên dưới dạng

------------------------------------------------
                     ---[ 1
              ---[ 2
                     ---[ 3
       ---[ 4
                     ---[ 5
              ---[ 6
                     ---[ 7
---[ 8
              ---[ 9
       ---[ 10
              ---[ 11
------------------------------------------------

Thực hiện

// Package binarysearchtree creates a ItemBinarySearchTree data structure for the Item type
package binarysearchtree

import ( “fmt” “sync”

<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>

)

// Item the type of the binary search tree type Item generic.Type

// Node a single node that composes the tree type Node struct { key int value Item left Node //left right Node //right }

// ItemBinarySearchTree the binary search tree of Items type ItemBinarySearchTree struct { root *Node lock sync.RWMutex }

// Insert inserts the Item t in the tree func (bst *ItemBinarySearchTree) Insert(key int, value Item) { bst.lock.Lock() defer bst.lock.Unlock() n := &Node{key, value, nil, nil} if bst.root == nil { bst.root = n } else { insertNode(bst.root, n) } }

// internal function to find the correct place for a node in a tree func insertNode(node, newNode *Node) { if newNode.key < node.key { if node.left == nil { node.left = newNode } else { insertNode(node.left, newNode) } } else { if node.right == nil { node.right = newNode } else { insertNode(node.right, newNode) } } }

// InOrderTraverse visits all nodes with in-order traversing func (bst *ItemBinarySearchTree) InOrderTraverse(f func(Item)) { bst.lock.RLock() defer bst.lock.RUnlock() inOrderTraverse(bst.root, f) }

// internal recursive function to traverse in order func inOrderTraverse(n *Node, f func(Item)) { if n != nil { inOrderTraverse(n.left, f) f(n.value) inOrderTraverse(n.right, f) } }

// PreOrderTraverse visits all nodes with pre-order traversing func (bst *ItemBinarySearchTree) PreOrderTraverse(f func(Item)) { bst.lock.Lock() defer bst.lock.Unlock() preOrderTraverse(bst.root, f) }

// internal recursive function to traverse pre order func preOrderTraverse(n *Node, f func(Item)) { if n != nil { f(n.value) preOrderTraverse(n.left, f) preOrderTraverse(n.right, f) } }

// PostOrderTraverse visits all nodes with post-order traversing func (bst *ItemBinarySearchTree) PostOrderTraverse(f func(Item)) { bst.lock.Lock() defer bst.lock.Unlock() postOrderTraverse(bst.root, f) }

// internal recursive function to traverse post order func postOrderTraverse(n *Node, f func(Item)) { if n != nil { postOrderTraverse(n.left, f) postOrderTraverse(n.right, f) f(n.value) } }

// Min returns the Item with min value stored in the tree func (bst ItemBinarySearchTree) Min() Item { bst.lock.RLock() defer bst.lock.RUnlock() n := bst.root if n == nil { return nil } for { if n.left == nil { return &n.value } n = n.left } }

// Max returns the Item with max value stored in the tree func (bst ItemBinarySearchTree) Max() Item { bst.lock.RLock() defer bst.lock.RUnlock() n := bst.root if n == nil { return nil } for { if n.right == nil { return &n.value } n = n.right } }

// Search returns true if the Item t exists in the tree func (bst *ItemBinarySearchTree) Search(key int) bool { bst.lock.RLock() defer bst.lock.RUnlock() return search(bst.root, key) }

// internal recursive function to search an item in the tree func search(n *Node, key int) bool { if n == nil { return false } if key < n.key { return search(n.left, key) } if key > n.key { return search(n.right, key) } return true }

// Remove removes the Item with key key from the tree func (bst *ItemBinarySearchTree) Remove(key int) { bst.lock.Lock() defer bst.lock.Unlock() remove(bst.root, key) }

// internal recursive function to remove an item func remove(node Node, key int) Node { if node == nil { return nil } if key < node.key { node.left = remove(node.left, key) return node } if key > node.key { node.right = remove(node.right, key) return node } // key == node.key if node.left == nil && node.right == nil { node = nil return nil } if node.left == nil { node = node.right return node } if node.right == nil { node = node.left return node } leftmostrightside := node.right for { //find smallest value on the right side if leftmostrightside != nil && leftmostrightside.left != nil { leftmostrightside = leftmostrightside.left } else { break } } node.key, node.value = leftmostrightside.key, leftmostrightside.value node.right = remove(node.right, node.key) return node }

// String prints a visual representation of the tree func (bst *ItemBinarySearchTree) String() { bst.lock.Lock() defer bst.lock.Unlock() fmt.Println("------------------------------------------------") stringify(bst.root, 0) fmt.Println("------------------------------------------------") }

// internal recursive function to print a tree func stringify(n *Node, level int) { if n != nil { format := “” for i := 0; i < level; i++ { format += " " } format += “—[ " level++ stringify(n.left, level) fmt.Printf(format+”%d\n", n.key) stringify(n.right, level) } }

Kiểm tra

Các bài kiểm tra mô tả việc sử dụng triển khai trên.

package binarysearchtree

import ( “fmt” “testing” )

var bst ItemBinarySearchTree

func fillTree(bst *ItemBinarySearchTree) { bst.Insert(8, “8”) bst.Insert(4, “4”) bst.Insert(10, “10”) bst.Insert(2, “2”) bst.Insert(6, “6”) bst.Insert(1, “1”) bst.Insert(3, “3”) bst.Insert(5, “5”) bst.Insert(7, “7”) bst.Insert(9, “9”) }

func TestInsert(t *testing.T) { fillTree(&bst) bst.String()

<span style="color:#a6e22e">bst</span>.<span style="color:#a6e22e">Insert</span>(<span style="color:#ae81ff">11</span>, <span style="color:#e6db74">"11"</span>)
<span style="color:#a6e22e">bst</span>.<span style="color:#a6e22e">String</span>()

}

// isSameSlice returns true if the 2 slices are identical func isSameSlice(a, b []string) bool { if a == nil && b == nil { return true } if a == nil || b == nil { return false } if len(a) != len(b) { return false } for i := range a { if a[i] != b[i] { return false } } return true }

func TestInOrderTraverse(t *testing.T) { var result []string bst.InOrderTraverse(func(i Item) { result = append(result, fmt.Sprintf("%s", i)) }) if !isSameSlice(result, []string{“1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9”, “10”, “11”}) { t.Errorf(“Traversal order incorrect, got %v”, result) } }

func TestPreOrderTraverse(t *testing.T) { var result []string bst.PreOrderTraverse(func(i Item) { result = append(result, fmt.Sprintf("%s", i)) }) if !isSameSlice(result, []string{“8”, “4”, “2”, “1”, “3”, “6”, “5”, “7”, “10”, “9”, “11”}) { t.Errorf(“Traversal order incorrect, got %v instead of %v”, result, []string{“8”, “4”, “2”, “1”, “3”, “6”, “5”, “7”, “10”, “9”, “11”}) } }

func TestPostOrderTraverse(t *testing.T) { var result []string bst.PostOrderTraverse(func(i Item) { result = append(result, fmt.Sprintf("%s", i)) }) if !isSameSlice(result, []string{“1”, “3”, “2”, “5”, “7”, “6”, “4”, “9”, “11”, “10”, “8”}) { t.Errorf(“Traversal order incorrect, got %v instead of %v”, result, []string{“1”, “3”, “2”, “5”, “7”, “6”, “4”, “9”, “11”, “10”, “8”}) } }

func TestMin(t testing.T) { if fmt.Sprintf("%s", bst.Min()) != “1” { t.Errorf(“min should be 1”) } }

func TestMax(t testing.T) { if fmt.Sprintf("%s", bst.Max()) != “11” { t.Errorf(“max should be 11”) } }

func TestSearch(t *testing.T) { if !bst.Search(1) || !bst.Search(8) || !bst.Search(11) { t.Errorf(“search not working”) } }

func TestRemove(t testing.T) { bst.Remove(1) if fmt.Sprintf("%s", bst.Min()) != “2” { t.Errorf(“min should be 2”) } }

Tạo cấu trúc dữ liệu cây cụ thể

Bạn có thể sử dụng cách áp dụng chung này để tạo các cây theo loại cụ thể, bằng cách sử dụng

//generate a `IntBinarySearchTree` binary search tree of `int` values
genny -in binarysearchtree.go -out binarysearchtree-int.go gen "Item=int"

//generate a </span>StringBinarySearchTree<span style="color:#e6db74"> binary search tree of </span>string<span style="color:#e6db74"> values genny -in binarysearchtree.go -out binarysearchtree-string.go gen “Item=string”


Các hướng dẫn về go khác: