[DSA] Binary Search Trees
Giới thiệu
Tree gồm có:
- Root: là node cao nhất trong B-Tree. vd: node A là root.
- Child: là 1 node liên kết trực tiếp với một node khác khi di chuyển từ root. vd: B, C, D là child của A.
- Parent: node phía trước child. vd: B là parent của E, F.
- Siblings: tập hợp các node có cùng parent: vd: E, F là siblings vì cùng có parent là B.
- Leaf: là 1 node ko có children. vd: E, F, G, I là leaf.
- Edge: là sự liên kết giữa node này với node khác.
Trees là kiểu dữ liệu phi tuyến tính (non-linear), khác với kiểu dữ liệu: linked list, array, queue, stack là kiểu dữ liệu tuyến tính (linear).
Các loại trees:
- Trees
- Binary trees
- Mỗi parent có nhiều nhất 2 node con.
- Binary Search trees:
- Mỗi parent có nhiều nhất 2 node con.
- Node nhỏ hơn parent nằm bên trái.
- Node lớn hơn parent nằm bên phải.
Khởi tạo
class NodeBinaryTree {
value;
left: NodeBinaryTree | null;
right: NodeBinaryTree | null;
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
root: NodeBinaryTree | null;
constructor() {
this.root = null;
}
insert(value) {}
find(value) {}
}
Khởi tạo các method
insert
insert(value) {
const newNode = new NodeBinaryTree(value);
if (!this.root) {
this.root = newNode;
return this;
}
let currentParent = this.root;
while (true) {
if (value < currentParent.value) {
if (currentParent.left) {
currentParent = currentParent.left;
} else {
currentParent.left = newNode;
return this;
}
} else if (value > currentParent.value) {
if (currentParent.right) {
currentParent = currentParent.right;
} else {
currentParent.right = newNode;
return this;
}
} else {
return undefined;
}
}
}
find
find(value) {
if (!this.root) return undefined;
let currentParent = this.root;
while (currentParent) {
if (value === currentParent.value) {
break;
} else if (value < currentParent?.value) {
currentParent = currentParent.left;
} else {
currentParent = currentParent.right;
}
}
return currentParent;
}
Độ phức tạp
| Method | Big O |
|---|---|
| Insertion | O(log n) |
| Searching | O(log n) |
All rights reserved
Bình luận