二叉搜索树BST

二叉搜索树

二叉树

1. 定义：也是一种动态数据结构 ；

一个节点也是二叉树、null也是二叉树

二分搜索树

• 特点：每个节点的值
• 小于其右子树的所有结点的值；
• 大于其左子树所有结点的值；
• 储存的元素必须有可比较性；意思是说不能存放重复数据

Set AND Map(可以理解为一种定义好的数据结构)

Set–集合：不能有重复元素

因为二分搜索树不能存放重复元素，所以是非常好的实现“集合”的底层数据结构；

二分搜索树的遍历

都是从根结点出发，最后回到根结点

1. 前序遍历

2. ```java
   System.out.println(node.)
   traverse(node.right);
   traverse(node.left);

     
   
   3. 中序遍历
   
     - ```java
       traverse(node.left);
       System.out.println(node.)
       traverse(node.right);

• （得到的结果是从小到大排列的）

4. 后续遍历（eg:为二分搜索树释放内存）

• traverse(node.right);
  traverse(node.left);
  System.out.println(node.)
  

二分搜索树BST的顺序性特性：

• 求最大值和最小值
• 求floor和ceil
• 求Rank和select（维护SIZE）
• 改进后支持重复元素（进入左子树或者加一个COUNT）