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ì
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)
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.
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)
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 }}
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()
public func search(value: T) -> BSNode? var node: BSNode? = self.root while let n = node if value n.key! node = n.right else return node return nil
Chuyên mục: ĐÀO TẠO