栈实现后序遍历
1.根入栈,
进入循环,只要栈中有元素就继续
(在循环里不断把右左都压入栈,(提前要弹出一个节点)只要左右不为空,就一直压入栈,那么那个弹出的节点(在两边都不空的情况下)弹出的就是后入的(右子树));
最后头插结果 根
最后头插结果 右 根
最后头插结果 左 右 根
2.递归的后续与先序遍历
思想:把递归整个树想成 添加一个节点
1.根最后(或者先)
集合add根
(遍历到最左边)
补充出口:root为null 返回集合;
看 建树；
(红黑树不是自平衡的二叉搜索树)
红黑树是满足红黑性质的二叉搜索树
因为普通二叉树在频繁的增删改查之后容易出现稀疏树的情况,因此引入了红黑树;
红黑树(没用，了解)
:根节点与Nil节点是黑的
:黑高平衡
没有连续的红色节点
添加:
向上分裂:查找位置过程,发现左右都是红色,说明是3key节点,就要向上分裂,左右红变黑,自己黑变红;
找到位置添加:
修复过程:连续红色节点,或者非左边倾,选择修复:
删除:删除的都是红色节点(不影响黑高平衡),(借节点,父节点兄弟节点)但有可能都是单key节点,为了避免不能分裂,因此在遍历的过程之中要找到借节点的位置,父红变黑,儿黑变红,此时如果left和left都是黑色,就要选择向下分裂,最后借节点
之后再进行修复过程;
是为了每次这样操作都只需要局部修复而不是全局修复;
--
左旋右旋 上下分裂
