Date
Oct. 7th, 2024
 
2024年 9月 5日

Post: iOS 面试题: Binary search tree

Today is the A Memorial Day

iOS 面试题: Binary search tree

Published 12:10 Oct 14, 2015.

Created by @ezra. Categorized in #Programming, and tagged as #iOS.

Source format: Markdown

Table of Content

最近遇到和看到的一些面试题。

Binary search tree 二叉搜索树主要由四个方法: * search: 时间复杂度为O(h),h为树的高度 * traversal: 时间复杂度为O(n),n为树的总结点数。 * insert: 时间复杂度为O(h),h为树的高度。 * delete: 最坏情况下,时间复杂度为O(h)+指针的移动开销。

可以看到,二叉搜索树的dictionary operation的时间复杂度与树的高度h相关。所以需要尽可能的降低树的高度,由此引出平衡二叉树Balanced binary tree。它要求左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这样就可以将搜索树的高度尽量减小。常用算法有 红黑树AVLTreap伸展树等。

Pinned Message
HOTODOGO
The Founder and CEO of Infeca Technology.
Developer, Designer, Blogger.
Big fan of Apple, Love of colour.
Feel free to contact me.
反曲点科技创始人和首席执行官。
开发、设计与写作皆为所长。
热爱苹果、钟情色彩。
随时恭候 垂询