二叉搜索树

链表 O(n) => 二分查找树 O(logn)

  1. 左子树的所有节点的 key 都小于根节点
  2. 左子树的所有的节点 key 都大于根节点
  3. 左右子树也是二叉搜索树
  4. key使用来排序的依据

问题：当反复删除时二分查找树会退化成链表
答案：平衡二叉搜索树（AVL，红黑树，2-3-4树）

  • AVL平衡 👉 左右子树的高度差 最大为1
  • 红黑树平衡 👉 黑节点的高度一样 (从任意子节点出发根节点，它的黑节点的高度都是一致的)

红黑树和AVL树的比较
插入：引起树的不平衡，AVL树和红黑树最多两次旋转，两者平衡的时间复杂度都是O(1)；
删除：AVL 需要往上回溯多个节点（root）的平衡，平衡的时间复杂度O(logn)；而红黑树最多只需要3次旋转，时间复杂度O(1);
搜索：AVL 的搜索稳定性要高于红黑树；
结论：如果有大量的插入和删除，红黑树更高；如果删除操作较少，则用AVL树。红黑树统计性能高于AVL树。