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