# 如何实现一个高效的二叉搜索树（BST）？请给出时间复杂度分析。 要求：设计一个二叉搜索树，支持插入、删除和查找操作。要求在平均情况下，这些操作的时间复杂度为O(log n)。同时，考虑树的平衡性，使得树的高度保持在对数级别。

class Node {

int key, height;
Node left, right;

Node(int d) {

key = d;
height = 1;
}
}

class AVLTree {

Node root;

int height(Node N) {

if (N == null)
return 0;
return N.height;
}

int max(int a, int b) {

return (a > b) ? a : b;
}

Node rightRotate(Node y) {

Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
return x;
}

Node leftRotate(Node x) {

Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return y;
}

int getBalance(Node N) {

if (N == null)
return 0;
return height(N.left) - height(N.right);
}

Node insert(Node node, int key) {

if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
return node;
node.height = 1 + max(height(node.left), height(node.right));
int balance = getBalance(node);
if (balance > 1 && key < node.left.key)
return rightRotate(node);
if (balance < -1 && key > node.right.key)
return leftRotate(node);
if (balance > 1 && key > node.left.key) {

node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && key < node.right.key) {

node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}

Node minValueNode(Node node) {

Node current = node;
while (current.left != null)
current = current.left;
return current;
}

Node deleteNode(Node root, int key) {

if (root == null)
return root;
if (key < root.key)
root.left = deleteNode(root.left, key);
else if (key > root.key)
root.right = deleteNode(root.right, key);
else {

if ((root.left == null) || (root.right == null)) {

Node temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;
if (temp == null) {

temp = root;
root = null;
} else
root = temp;
} else {

Node temp = minValueNode(root.right);
root.key = temp.key;
root.right = deleteNode(root.right, temp.key);
}
}
if (root == null)
return root;
root.height = max(height(root.left), height(root.right)) + 1;
int balance = getBalance(root);
if (balance > 1 && getBalance(root.left) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root.left) < 0) {

root.left = leftRotate(root.left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root.right) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root.right) > 0) {

root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}

boolean search(Node root, int key) {

if (root == null)
return false;
if (root.key == key)
return true;
return key < root.key ? search(root.left, key) : search(root.right, key);
}
}


|
3月前
|

77 0
|
3月前
|
Go 数据处理 Docker
elk stack部署自动化日志收集分析平台
elk stack部署自动化日志收集分析平台
60 0
|
3月前
|

MySQL性能优化指南：深入分析重做日志刷新到磁盘的机制
MySQL性能优化指南：深入分析重做日志刷新到磁盘的机制
48 0
|
4月前
|

60 1
|
4月前
|
SQL 存储 安全

101 0
|
4月前
|

276 0
|
4月前
|
SQL Java 数据库连接

69 0
|
1月前
|
SQL NoSQL Java
【七】springboot整合AOP实现日志操作
【七】springboot整合AOP实现日志操作
39 0
|
1月前
|

Hudi Log日志文件格式分析（一）
Hudi Log日志文件格式分析（一）
24 1
|
1月前
|

Hudi Log日志文件写入分析（二）
Hudi Log日志文件写入分析（二）
20 1