Cây nhị phân là gì
Một cây tìm kiếm nhị phân (Binary Search Tree – viết tắt là BST) là một cây mà trong những số ấy tất cả những nút đều sở hữu các Đặc điểm sau:
Cây con phía trái của một nút có khóa (key) nhỏ tuổi hơn hoặc bằng cực hiếm khóa của nút ít cha (của cây con này).quý khách vẫn xem: Cây nhị phân là gì
Cây bé bên buộc phải của một nút ít bao gồm khóa to hơn hoặc bởi 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ì
Vì gắng nói theo một cách khác rằng, một cây search kiếm nhị phân (BST) phân chia toàn bộ các cây con của nó thành hai phần: cây bé phía trái cùng cây con mặt bắt buộc với hoàn toàn có thể được quan niệm nlỗi sau:
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
2. Cấu trúc dữ liệu cây
Cây nhị phân là 1 trong cấu trúc tài liệu quan trọng được sử dụng đến mục đích tàng trữ tài liệu.Một cây nhị phân gồm một ĐK đặc biệt là từng nút ít có thể gồm buổi tối nhiều nhị nút ít nhỏ.Một cây nhị phân tận dụng ưu thế của nhị giao diện cấu tạo dữ liệu: một mảng sẽ sắp đến sản phẩm công nghệ từ với một danh sách links (Linked List), vì thế việc đào bới tìm kiếm kiếm đã nhanh hao nhỏng vào mảng đã sắp đến đồ vật tự với những thao tác ckém với xóa cũng biến thành nkhô nóng bởi vào Linked List.
2.1 Node
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 nhằm xác minh node là leaf hay còn node bé nữa.
Xem thêm: Các Loại Chuối Mốc Là Chuối Gì, Chuối Móc Là Chuối Gì
2.2 Bậc của node cây nhị phân search kiếm
bậc của một nút ít màn biểu diễn số nhỏ của một nút. Nếu nút ít gốc gồm bậc là 0, thì nút ít bé tiếp sau sẽ có bậc là 1, cùng nút ít con cháu của chính nó sẽ có được bậc là 2, …
public func height() -> Int if isLeaf return 0 else return 1 + max(left?.height() ?? 0, right?.height() ?? 0)
3. 1 số hoạt độ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 Khi một trong những phần tử được chèn: trước tiên bọn họ yêu cầu xác xác định trí đúng mực của thành phần này.Bắt đầu tìm kiếm từ bỏ nút ít cội, sau đó trường hợp tài liệu là nhỏ dại hơn quý giá khóa (key), thì tìm tìm vị trí còn trống làm việc cây bé phía bên trái và ckém dữ liệu vào đó; nếu như dữ liệu là nhỏ dại hơn nữa thì search tìm vị trí còn sinh sống sinh sống cây con bên đề nghị với cnhát tài liệu vào đó.Xem thêm: Bạn Thường Làm Gì Vào Cuối Tuần Tiếng Anh (5 Mẫu), Bạn Làm Gì Vào Cuối Tuần Bằng Tiếng Anh
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 kiếm tìm kiếm
Khi bạn có nhu cầu xem tất cả node vào cây nhị phân tìm kiếm kiếm, họ sẽ thực hiện chăm chú cây, như ví dụ sinh hoạt trên lúc coi ngó họ sẽ in ra những quý giá cây tự nhỏ dại nhất cho lớn số 1 tương ứng: 1, 2, 5, 7, 9, 10.Việc duyệt cây nhị phân search tìm đang bước đầu tự ngọn (root) sau đó đi lịch sự trái tìm tới cực hiếm nhỏ dại độc nhất vô nhị rồi theo lần lượt đi hết lịch sự bên nên.
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 tìm bên trên cây nhị phân
Tìm kiếm trên cây nhị phân được thực hiện theo 3 bướcnếu quý giá to hơn quý giá ở gốc thì tìm kiếm kiếm bên đề nghị.ví như gía trị nhỏ rộng giá trị nơi bắt đầu thì search kiếm phía trái.nếu giá trị node tiếp sau bởi giá trị tìm kiếm thì trả về node tương xứng còn nếu ko trả về nil
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