顧名思義，二叉搜索樹是一棵二叉樹，每個節點就是一個對象，這個對象包含屬性left、right和parent。left指向節點的左孩子，right指向節點的右孩子，parent指向節點的父節點（雙親）。如果某個孩子節點和父節點不存在，則相應的屬性為null。根節點是樹中唯一父節點指針為null的節點。

二叉搜索樹中的關鍵字滿足以下性質：

假設x是二叉搜索樹中的一個節點，如果y是x的左子樹中的一個節點，那么y.key ≤ x.key；如果y是x右子樹中的一個節點，那么y.key ≥ x.key。

兩棵二叉搜索樹的示意圖如下：

二叉搜索樹支持查詢、求最大值、最小值以及追加和刪除等操作，其基于java的簡單實現如下：

/*** 數據結構-二叉搜索樹*/
public class BinarySearchTree {/*** 樹的根節點*/private Node root;/*** 根據關鍵字搜索節點** @param key 關鍵字* @return key所在的節點*/public Node search(int key) {Node node = root;while (node != null && key != node.key) {// 如果key小于當前節點的key，則往左孩子節點找，否則往右孩子節點找if (key < node.key) {node = node.left;} else {node = node.right;}}return node;}/*** 獲取key最小的節點** @return key最小的節點*/public Node min() {return min(root);}/*** 獲取以node為根的子樹中key最小的節點** @param node 子樹根節點* @return 子樹中key最小的節點*/public Node min(Node node) {while (node.left != null) {node = node.left;}return node;}/*** 獲取key最大的節點** @return key最大的節點*/public Node max() {return max(root);}/*** 獲取以node為根的子樹中key最大的節點** @param node 子樹根節點* @return 子樹中key最大的節點*/public Node max(Node node) {while (node.right != null) {node = node.right;}return node;}/*** 向樹中添加節點** @param key 插入節點的key*/public void add(int key) {Node node = root;Node temp = null;// 尋找合適的節點添加新節點while (node != null) {temp = node;if (key < node.key) {node = node.left;} else {node = node.right;}}Node newNode = new Node();newNode.parent = temp;newNode.key = key;if (temp == null) { // 該樹上還沒有節點root = newNode;} else if (key < temp.key) {temp.left = newNode;} else {temp.right = newNode;}}/*** 刪除以key為關鍵字的節點** @param key 關鍵字*/public void delete(int key) {Node node = search(key);if (node.left == null) {transplant(node, node.right);} else if (node.right == null) {transplant(node, node.left);} else {Node min = min(node.right);if (!min.parent.equals(node)) {transplant(min, min.right);min.right = node.right;min.right.parent = min;} transplant(node, min);min.left = node.left;min.left.parent = min;}}/*** 用node2為跟的子樹替換node1為根的子樹** @param node1 子樹1* @param node2 子樹2*/private void transplant(Node node1, Node node2) {// node1是根節點if (node1.parent == null) {root = node2;} else if (node1 == node1.parent.left) { // 如果node1是左孩子node1.parent.left = node2;} else { // 如果node1是右孩子node1.parent.right = node2;}if (node2 != null) {node2.parent = node1.parent;}}public Node getRoot() {return root;}/*** 樹上的節點*/public static class Node {/*** 節點關鍵字*/private int key;/*** 節點的左孩子*/private Node left;/*** 節點的右孩子*/private Node right;/*** 節點的父節點*/private Node parent;public int getKey() {return key;}public Node getLeft() {return left;}public Node getRight() {return right;}public Node getParent() {return parent;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Node node = (Node) o;return key == node.key && Objects.equals(left, node.left)&& Objects.equals(right, node.right) && Objects.equals(parent, node.parent);}@Overridepublic int hashCode() {return Objects.hash(key, left, right, parent);}}
}