Home › ĐÀO TẠO › cây nhị phân là gì, hoạt Động ra sao? cấu trúc cây nhị phân là gì

Cây nhị phân là gì, hoạt Động ra sao? cấu trúc cây nhị phân là gì

Admin - 19/03/2021 662

Một cây tìm kiếm tìm nhị phân (Binary Search Tree – viết tắt là BST) là 1 trong những cây mà trong những số ấy toàn bộ những nút ít đều sở hữu các điểm lưu ý sau:

Cây con bên trái của một nút ít tất cả khóa (key) bé dại hơn hoặc bằng giá trị khóa của nút ít phụ vương (của cây nhỏ này).

Bạn đang xem: Cây nhị phân là gì, hoạt Động ra sao? cấu trúc cây nhị phân là gì

Cây nhỏ bên nên của một nút gồm khóa lớn hơn hoặc bằng quý giá khóa của nút cha (của cây con này).

Vì cố nói theo một cách khác rằng, một cây tìm kiếm nhị phân (BST) phân chia tất cả các cây nhỏ của nó thành nhị phần: cây bé bên trái cùng cây bé bên cần và có thể được khái niệm nhỏng sau:

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

2. Cấu trúc tài liệu cây

Cây nhị phân là 1 kết cấu dữ liệu đặc biệt quan trọng được thực hiện mang lại mục đích tàng trữ tài liệu.Một cây nhị phân gồm một điều kiện nhất là từng nút ít rất có thể có buổi tối nhiều hai nút ít bé.Một cây nhị phân tận dụng lợi thế của nhì hình dạng kết cấu dữ liệu: một mảng đã sắp đến máy từ bỏ với một list liên kết (Linked List), cho nên vì thế việc tìm và đào bới kiếm đã nhanh hao nlỗi vào mảng sẽ sắp vật dụng từ bỏ với những thao tác ckém cùng xóa cũng sẽ nhanh khô bởi vào Linked List.

2.1 Node

Node vào cây tìm kiếm kiếm nhị phân gồm điểm sáng bình thường là cực hiếm mặt đề nghị bao giờ cũng lớn hơn giá trị phía trái.Một node vào cây search kiếm nhị phân đang bao gồm node trái-buộc phải, key cực hiếm của node đó trong cây.

Xem thêm: Yanbi Sinh Năm Bao Nhiêu - Những Bài Hát Hay Nhất Của Yanbi

class BSNode var key: T? var left: BSNode? var right: BSNode?public var isLeaf: Bool return left == nil &và right == nilthuộc tính này để xác minh node là leaf giỏi còn node nhỏ nữa.

2.2 Bậc của node cây nhị phân search kiếm

bậc của một nút biểu diễn số nhỏ của một nút. Nếu nút ít nơi bắt đầu tất cả bậc là 0, thì nút bé tiếp theo sẽ sở hữu được bậc là một, và nút ít cháu của chính nó sẽ có bậc là 2, …

public func height() -> Int if isLeaf return 0 else return 1 + max(left?.height() ?? 0, right?.height() ?? 0)

3. một số ít vận động cơ bạn dạng bên trên cây nhị phân kiếm tìm kiếm

3.1 Chèn thêm node vào cây

Mỗi lúc 1 phần tử được chèn: trước tiên chúng ta đề nghị xác xác định trí đúng đắn của phần tử này.Bắt đầu tìm tìm tự nút cội, kế tiếp nếu dữ liệu là bé dại hơn cực hiếm khóa (key), thì tra cứu tìm vị trí còn trống sinh hoạt cây nhỏ bên trái cùng cyếu dữ liệu vào đó; nếu như tài liệu là nhỏ dại hơn thì tìm kiếm kiếm địa điểm còn sinh sống sống cây con bên cần cùng ckém tài liệu vào kia.

func insert(element key: T) // init root guard root.key != nil else root.key = key return var current: BSNode = root while current.key != nil if key () childBSNode.key = key current.left = childBSNode break else if key > current.key! if let rightBSNode = current.right current = rightBSNode else let childBSNode = BSNode() childBSNode.key = key current.right = childBSNode break }}

3.2 Duyệt cây nhị phân tìm kiếm

Lúc bạn muốn coi toàn bộ node vào cây nhị phân tra cứu kiếm, họ sẽ tiến hành coi xét cây, nlỗi ví dụ sinh sống bên trên lúc chăm sóc họ sẽ in ra các quý giá cây trường đoản cú bé dại duy nhất mang đến lớn nhất tương ứng: 1, 2, 5, 7, 9, 10.Việc chăm bẵm cây nhị phân tìm tìm đang bước đầu từ ngọn (root) tiếp đến đi sang trái tìm đến giá trị nhỏ độc nhất rồi theo thứ tự đi không còn sang bên yêu cầu.

func traverse() //trivial condition guard let key = self.key else print("no key provided..") return //process the left side if self.left != nil left?.traverse() print("...the value is: (key) - height: (self.height)..") //process the right side if self.right != nil right?.traverse()

3.3 Tìm kiếm bên trên cây nhị phân

Tìm tìm trên cây nhị phân được tiến hành theo 3 bước

ví như giá trị lớn hơn cực hiếm nghỉ ngơi cội thì tìm kiếm mặt yêu cầu.giả dụ gía trị nhỏ dại rộng quý hiếm cội thì kiếm tìm tìm phía trái.nếu như cực hiếm node tiếp theo bằng cực hiếm tra cứu kiếm thì trả về node tương ứng còn ví như ko trả về nil