BST(Binary Search Tree)二叉搜索树
BBST (Balance Binary Search Tree) 平衡二叉搜索树
1，首先看一下什么是BST？
直观上看，左边的节点小于右边的节点，就是BST，定义就是任意节点均不大于其右子树中的节点，不小于其左子树中的节点
2，什么是BBST平衡二叉树？
N个节点构成的二叉树，树高为log2N，称为理想平衡
N个节点构成的二叉树，树高渐进地接近log2N，称为适度平衡
适度平衡的BST称为BBST（通俗讲，就是左右子树差值不要超过1）
3，两棵结构不同的树，但中序遍历的结果相同，这就是BST转换成BBST的基础。（旋转的理论依据）
4，两棵结构不同的树，但中序遍历的结果相同，这个歧义性带来的好处和坏处？
中序遍历的歧义性坏处：中序遍历的歧义性，在中缀表达式的求值计算，就不得不想办法，辨析不同操作符之间的优先级。
对于BST 中序遍历的歧义性，是必不可少的。因为它能实现不同的树形结构，相同的中序遍历顺序。这是等价变化的前提。
**歧义性带来的好处等价Bst：**对于任意的bst，它们的中序遍历相同，但结构不同，称它们为等价的bst。
等价bst之间的关系和转换方式：左旋，右旋
上下可变：祖先和孙子节点可换位置。
左右不乱：中序遍历不能乱，左右孩子不能乱。
左旋：
右旋：
原文链接：https://mp.weixin.qq.com/s/hIoBvnSbhduMNuU2jUGZyg
作者：一起写程序
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/1926/viewspace-2797965/ ，如需转载，请注明出处，否则将追究法律责任。
