二叉排序树

川长思鸟来 2022-02-24 07:48 235阅读 0赞

二叉排序树BST，又叫二叉搜索树  
或者是一棵空树，或者是具有下列性质的二叉树：  
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；  
（3）左、右子树也分别为二叉排序树；

二分查找，时间log2n  
有前序遍历，根、左、右的顺序访问遍历每个结点  
中序遍历，左根右顺序  
后序遍历，左右根顺序  
依据根的位置命名。

## 旋转 ##

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

左旋，就是把节点变成左孩子节点，原来的右孩子节点变成父节点  
以节点和左孩子连线为轴，旋转右孩子到另一侧  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21pbmd3dWxpcG8_size_16_color_FFFFFF_t_70]  
右旋，就是把节点变成右孩子节点，原来的左孩子节点变成父节点  
以节点和左孩子连线为轴，旋转右孩子到另一侧  
![在这里插入图片描述][20190515150802408.png]  
左旋 和 右旋 是相对的两个概念，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。

优化方式有  
Size Balanced Tree(SBT)  
AVL树  
红黑树  
Treap(Tree+Heap)  
这些均可以使查找树的高度为O(log(n))

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21pbmd3dWxpcG8_size_16_color_FFFFFF_t_70]: /images/20220224/c2744ba61803448f8246bf8d4b40b0fa.png
[20190515150802408.png]: /images/20220224/75312da1d7b84b0eac5aeaabcd76e80a.png